Can two equivalent JavaScript generators be derived from each other?

Question

I have two JavaScript generator functions for permutations. They both provide Heap's enumeration.

Question: I would like to know whether one implementation can be derived from the other by some rigorous code transformation. In particular, I would like to see, how the yield statement might "travel" from its earlier position to its later one and how the base case could (apparently) "vanish".

The source code is re-edited to be runnable as self-contained code snippets, even though in the literature it is common to see algorithms with "globals".

The question is not about the popular recursive vs. iterative issue. Let us stick to recursive.

The code was inspired by Robert Sedgewick's paper, Permutation Generation Methods (1977), where on page 140 he introduces the following basic recursive algorithm:

To generate all permutations of P[1], ..., P[N], we repeat N times the step: "first generate all permutations of P[1], ..., P[N-1], then exchange P[N] with one of the elements P[1], ..., P[N-1]."

However, that does not truely give Heap's algorithm since during the last iteration of the repeat loop, there is a superfluous exchange. If that is removed, we end up with implementations which seem to be equivalent to the recursive solution given in Wikipedia. In any case, when called for N = 4 it reproduces Heap's enumeration as given in Sedgewick's paper. Please do not dwell on edge cases or negative N. Also, I do not consider it an important feature that implementation 1 produces the original permutation just so, whereas it has to be manually provided for in the other implementation.

Implementation 1:

function permute(N) {
  function swap(x, y) { [ P[x], P[y] ] = [ P[y], P[x] ] }
  function heap(n, i) { return (n % 2) || i }

  var P = []; for (let i = 1; i <= N; i++) P[i] = i;
  var count = 1;
    
  for (p of permutations(N)) console.log(count++, p.slice(1));

  function* permutations(n) {
    // Recursion base case
    if (n == 1) yield P;
    else for (let i = 1; i <= n; i++) {
        yield* permutations(n - 1);
        if (i < n) swap(n, heap(n, i));
    }
  }
}

permute(4);

Implementation 2:

function permute(N) {
  function swap(x, y) { [ P[x], P[y] ] = [ P[y], P[x] ] }
  function heap(n, i) { return (n % 2) || i }

  var P = []; for (let i = 1; i <= N; i++) P[i] = i;
  var count = 1;

  // Need to log the initial permutation explicitly.
  console.log(count++, P.slice(1));
    
  for (p of permutations(N)) console.log(count++, p.slice(1));

  function* permutations(n) {
      for (let i = 1; i <= n; i++) {
        yield* permutations(n - 1);
        if (i < n) { swap(n, heap(n, i)); yield P }
      }
  }
}
   
permute(4);

Note that I simply ignore the element at index 0 of JavaScript arrays by initialising array P suitably and by using the slice() method to log only the subarray starting at index 1. This is done to remain compatible with frequently found pseudocode in Sedgewick and elsewhere.

For clarification: what do I mean by code transformation? Sedgewick himself gives examples. First he starts off with his Algorithm 1 on page 140, which is recursive. He first gives a (rather loose) transformation into a first nonrecursive form on page 142. This one he then transforms three times into some final form which, when given directly, would be hard to consider equivalent to the initial one. But take this as a model only; I am not asking about the recursive vs. iterative issue.

I suspect the wording "Is one of them to be preferred over the other?" is what led this to being closed as opinion-based. I don't think there's any reason for that to be part of the question. — Patrick Roberts
– Patrick Roberts, Commented Jun 15, 2025 at 16:25

trincot · Accepted Answer · 2025-06-18 20:45:45Z

First, about the "missing" base case in implementation 2: when n is 1, it performs one iteration of the for loop, making a recursive call with n being 0, which does nothing (the loop makes no iteration), coming back from that call, and skipping the if as its condition is not true. That's it: so actually nothing is swapped nor yielded when n is 1. If we wanted to make that code more alike to that of implementation 1, we could add the base-case if statement and just not execute the loop in that case.

We could merge the two implementations into one function that gets the desired implementation as second argument:

function permute(N, implementation) { // Second parameter addded
  function swap(x, y) { [ P[x], P[y] ] = [ P[y], P[x] ] }
  function heap(n, i) { return (n % 2) || i }

  var P = []; for (let i = 1; i <= N; i++) P[i] = i;
  var count = 1;
    
  for (p of permutations(N)) console.log(count++, ": ", ...p.slice(1));

  function* permutations(n) {
    // Recursion base case
    if (n == 1) {
        if (implementation === 1) yield P;
    } else for (let i = 1; i <= n; i++) {
        yield* permutations(n - 1);
        if (i < n) {
            swap(n, heap(n, i));
            if (implementation === 2) yield P;
        }
    }
  }
}

permute(4, 1); // Change second argument to run the other version

We know that implementation 1 yields the unchanged array, while implementation 2 doesn't, but both yield the array exactly once after each swap. It is just the place in the code where this yield happens that is different.

In implementation 2 it is quite clear that each swap is followed by a yield of the so mutated array.

In implementation 1 it is less evident, but we can see this invariant in both implementations:

The array is never mutated while going down in the recursion tree. It remains unaltered until the base case is reached. A swap can only happen after returning from a recursive call and before going down the recursion tree again.

In other words, we can be sure that between the moment that a swap is executed and the subsequent visit of the next leaf in the recursion tree (a base case), no mutation happens to the array. So whether that array is yielded at the start of this descent towards the leaf (as in implementation 2), or at the end of the descent (as in implementation 1), it will be the same array that is yielded. And as there is a descent (recursive call) right after every swap, both algorithms are bound to yield the same arrays in the same order.

As both implementations perform an initial descent to a base case that is not preceded by a swap, we have there the exception to the above rule, which explains why implementation 1 has one more yield (the first one) than implementation 2 where this same initial descent does not involve a yield.

I hope this is what you were looking for.

Collectives™ on Stack Overflow

Can two equivalent JavaScript generators be derived from each other?

1 Answer 1

1 Comment

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

1 Comment

Related