Generating Permutations with Recursion: Common Recursive Structure

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

Common Recursive Structure

Consider a subarray a[s : N − 1] for some s. Let us call its set of N −s elements as set B. Now, to generate all the permutations of elements of this subarray, we can proceed as follows.

Pick some element e from set B and place it at index s of array a, while keeping rest of the elements of B (set B ∖{e}) in subarray a[s + 1 : N − 1]. Now solve the subproblem of permuting the subarray a[s + 1 : N − 1]. After that, repeat the above process by picking some other element from B not already picked and placing it at index s, and permuting the rest of B in subarray a[s + 1 : N − 1]. Repeat this by picking each of the N − s elements of B. This process must generate all the (N − s)! permutations of the subarray a[s : N − 1].

Note that, the subproblem of permuting the smaller subarray a[s + 1 : N − 1] can be solved in a similar way. Repeating this process recursively will eventually give us a subproblem with subarray a[N − 1 : N − 1], which is trivial.

The question yet to be answered is, how to pick elements of B for placing at index s without skipping or repeating any? To appreciate the challenge in this, notice that the subproblem of a[s + 1 : N − 1] will reorder the elements of the subarray while permuting them. The algorithms we discuss have some deﬁned strategy to locate the next element of B to pick, from some index x of the subarray. Such element is then swapped with the existing element at index s to proceed for solving the subproblem of a[s + 1 : N − 1].

Below method depicts the above recursive structure and provides a skeleton in which all of our recursive algorithms will ﬁt. generate(s) is supposed to generate all permutations of the subarray a[s : N − 1]. The initial call is generate(s = 0). print() prints the permutation currently in array a.

#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 */
  }
}

Note that there are N − s iterations (size of set B), each with one recursive call. The very ﬁrst recursive call (in ﬁrst iteration with i = 0) is made without performing any swap — the element initially at index s remains at index s. The “Setup Block” and “Cleanup Block” are general placeholders for any steps the algorithm needs to perform before and after the recursive call respectively. When the base-case of s = N − 1 is reached, a permutation of the complete array a is ready for processing; here we just print it.