Translate permutation algorithm by Sedgewick from Pseudocode into JavaScript

The following aspects should be taken into account, starting with some simple ones:

1. The access to the matrix B is coded as B[N, c], but in JavaScript 2D arrays are accessed with B[N][c].

2. For assignment :=, we just use = in JavaScript.

3. 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.

4. if cond then ... endif translates to if (cond) { ... } or just if (cond) ...; if there is just one statement in the if block.

5. The loop: ... while cond: ... repeat construct can be translated to while(true) { ... if (!(cond)) break; ... }

6. For local variables like c to be really local in JavaScript, we need to use let or var.

7. 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.

8. 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.

9. 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.

10. 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 yield or output each 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.

Points 1 to 6: JavaScript syntax and local variable

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;
    }
}

Point 7: 0-based indexing

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;
    }
}

Point 8: eliminate the reference to B

We 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;
    }
}

Point 9. No global variables

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;
    }
}

Point 10. Generator

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.