Generating Permutations without Recursion

[This page is auto-generated; please prefer to read the article’s PDF Form.]

Generating Permutations without Recursion

Nitin Verma

September 16, 2021

Given an array a of N elements which are all distinct, we want to generate all the N! permutations of its elements.

In an earlier article titled Generating Permutations with Recursion [2], we discussed a few recursive algorithms for this problem. All of those algorithms were based on a common recursive structure, as depicted by the following skeleton method. Please refer to that article for details about this recursive structure (section “Common Recursive Structure”).

#define SWAP(i, j) {int t; t = a[i]; a[i] = a[j]; a[j] = t;}

void generate(int s)
{
  int i;

  if(s == N-1)
  {
    print();
    return;
  }

  for(i = 0; i < N-s; i++)
  {
    /* Setup Block */
    if(i > 0)
      SWAP(s, x);

    generate(s+1);

    /* Cleanup Block */
  }
}

In this article, we will ﬁnd out how we can implement those recursive algorithms without using recursive calls. What makes our task simpler is that all of them follow the above common recursive structure. From the above skeleton, we will design an equivalent non-recursive skeleton, which itself will serve as a common skeleton for writing non-recursive variants of the algorithms.

We will now attempt to convert the above generate() method into its non-recursive equivalent.

[Next]