In his classical paper Permutation Generation Methods, Computing Surveys 1977, Robert Sedgewick presents his "Algorithm 1" on page 140 like this:
procedure permutations(N);
begin
c:= 1;
loop:
if N > 2 then permutations(N - 1)
endif;
while c < N:
P[B[N, c]] :=: P[N];
c:= c + 1;
repeat
end;
This is neither Algol60 nor Algol68, but Pseudocode. His :=: operator is the swap operator for array elements. The loop-while-repeat construct is taken from D. E. Knuth, Sorting and Searching, The Art of Computer Programming 3.
Please, can anyone help me to translate the algorithm into JavaScript.
Also: that procedure is supposed to generate all permutations of N different elements. Where does Sedgewick intend to yield or output each new permutation to the caller?
The following aspects should be taken into account, starting with some simple ones:
The access to the matrix B is coded as B[N, c], but in JavaScript 2D arrays are accessed with B[N][c].
For assignment :=, we just use = in JavaScript.
The swap operation :=: can be translated to JavaScript by making use of a destructuring assignment. For instance, [a[i], a[j]] = [a[j], a[i]] swaps the values at indices i and j of array a.
if cond then ... endif translates to if (cond) { ... } or just if (cond) ...; if there is just one statement in the if block.
The loop: ... while cond: ... repeat construct can be translated to while(true) { ... if (!(cond)) break; ... }
For local variables like c to be really local in JavaScript, we need to use let or var.
In the paper 1-based positions are used for the arrays, so P[1] is the very first array element, and P[N] the last (if N is the size of the array). But in JavaScript 0-based indexing is used, where the first array element is at P[0] and the last at P[N-1]. The same happens with the B matrix.
The B matrix is not part of the code you have given, but the paper explains on the next page it is actually not needed and code is provided that doesn't depend on it.
It is not nice for a function to have side-effects, so it would be better to pass P as an argument and only mutate a copy of the original array.
The function visits all permutations, but the caller does not get access to these permutations, as you rightly point out:
Where does Sedgewick intend to
yieldoroutputeach new permutation to the caller?
You're right that the function is rather useless as it stands. Sedgewick uses the verb "generate" to just mean that the array P takes on a permutation, but not that this permutation is made available to the caller. He touches on this point on page 143:
The programs above merely generate all permutations of
P[1],...,P[N]; in order to do anything useful, we need to process each permutation in some way. [...]we shall assume a macro called process which is to be invoked each time a new permutation is ready. In the nonrecursive version of Algorithm 1 above, if we put a call to process at the beginning and another call to process after the exchange statement, then process will be executed N! times, once for each permutation.
As you already hinted, in modern JavaScript this is a good candidate for a generator function, which would yield each permutation.
Let's take these aspects step by step.
To write JavaScript code that at least has correct syntax, the first five points need to be taken into account. Point 6 is trivial, so let's also take it on board to arrive at this code in JavaScript:
function permutations(N) {
let c = 1;
while (true) {
if (N > 2) permutations(N - 1);
if (!(c < N)) break;
[P[N], P[B[N][c]]] = [P[B[N][c]], P[N]]; // Swap
c = c + 1;
}
}
We need to review all index references so they become 0-based indexes. Note that the meaning of N doesn't change -- it is the size of the (sub)array:
function permutations(N) {
let c = 0;
const last = N - 1;
while (true) {
if (N > 2) permutations(N - 1);
if (!(c < last)) break;
[P[last], P[B[last][c]]] = [P[B[last][c]], P[last]]; // Swap
c = c + 1;
}
}
BWe cannot run this yet, as B has not been defined. On the next page of the paper, the author explains that we don't really need the matrix B, as B[N, c] is defined as
B[N, c] = { N - c if N is even and c > 2
{ N - 1 otherwise
He explains that we could inject the following code to get rid of any B usage:
if (N even) and (c > 2)
then P[N] :=: P[N-c]
else P[N] :=: P[N-1] endif
I find it more elegant to define a separate index variable which either gets to be N-c or N-1. Using that ALGOL-style pseudo-code:
i := N - (if (N even) and (c > 2) then c else 1);
P[N] :=: P[i]
In JavaScript, where we want to use 0-based indexing, that would become:
function permutations(N) {
let c = 0;
const last = N - 1;
while (true) {
if (N > 2) permutations(N - 1);
if (!(c < last)) break;
let i = last - 1 - (N % 2 === 0 && c > 1 ? c : 0);
[P[last], P[i]] = [P[i], P[last]];
c = c + 1;
}
}
In the above code P is assumed to be global, or at least have a larger scope than the permutations function. The function mutates this array, which is not good practice. We should at least provide P as argument. And if we have that, we can also take a copy of P when it is the first call, so that any recursive calls will mutate the copy, and not the original. We can also give a default value to the N parameter, so the original caller does not have to specify it. None of this is absolutely necessary, but it doesn't require much change to apply better practice:
function permutations(P, N=P.length) {
if (N === P.length) P = [...P]; // Take a copy to avoid mutating the original array
let c = 0;
const last = N - 1;
while (true) {
if (N > 2) permutations(P, N - 1);
if (!(c < last)) break;
let i = last - 1 - (N % 2 === 0 && c > 1 ? c : 0);
[P[last], P[i]] = [P[i], P[last]];
c = c + 1;
}
}
The permutations that are generated in the above versions do not serve any purpose -- the caller cannot access them. A generator function solves this. As each swap results in a new permutation, we can place a yield right after that swap action. We also need to yield the original array, which should be considered a permutation as well. Here is what that becomes:
function* permutations(P, N=P.length) {
if (N === P.length) {
P = [...P]; // Take a copy to avoid mutating the original array
yield P; // The initial array is a permutation
}
let c = 0;
const last = N - 1;
while (true) {
if (N > 2) yield* permutations(P, N - 1);
if (!(c < last)) break;
let i = last - 1 - (N % 2 === 0 && c > 1 ? c : 0);
[P[last], P[i]] = [P[i], P[last]];
yield P; // Each swap results in a new permutation
c = c + 1;
}
}
// Demo
const P = [10, 20, 30, 40];
for (const perm of permutations(P)) {
console.log(...perm);
}Much more can be adapted to make this code more elegant, but at least this is a version that runs in JavaScript and visualises each permutation as it is generated, while staying close to the original algorithm.