A Simple Algorithm for Generating Combinations: Non-Recursive Equivalent

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

Non-Recursive Equivalent

In the non-recursive equivalent of generate(), we will be simulating the recursive calls by ourselves. To do that, we will ﬁrst make some observations about the generate() method and its execution ﬂow.

First notice that, there can be up to k + 1 active invocations of generate(), with argument r having values from k to 0. Further, for all r > 0, this method is simply a loop: a sequence of iterations for each i in the range s to n − r. To maintain this state i of (up to) k active invocations, we will use an array I of k integers. I[k − r] will hold the value of i for invocation of generate(s,r).

Now note that the method parameter s is used only to initialize i for the ﬁrst iteration. Further, for every recursive invocation, the value of s is speciﬁed as “(i + 1)” by the caller. So, while making the (simulated) recursive call, we will directly initialize ‘i’ of the new invocation using current ‘i’ plus 1, and avoid storing the argument s.

To keep track of the currently executing generate() call (top of the call-stack), we will use an integer r having value equal to argument r of the call. While making a (simulated) recursive call or returning, r will be decremented or incremented by 1 respectively.

These were some of the ideas on which the following non-recursive equivalent of generate() is based. In the while loop below, the beginning of any iteration can be seen as the point when either (a) a fresh generate() call is starting, or (b) a generate() call is resuming and starting a new iteration (the recursive call made by its earlier iteration has just returned). Case (b) implies r > 0.

void generate_nonrecur()
{
  int I[k], r;

  /* prepare to "execute" generate(0, k) */
  I[0] = 0;
  r = k;

  while(r <= k)
  {
    if(r == 0)
    {
      print();

      /* "return" to the caller */
      r = r + 1;
      continue;
    }

    /* for both cases (a) and (b), the ’i’ of the iteration to
       execute is present in I[k-r] */

    if(I[k-r] < n-r+1)
    {
      c[k-r] = a[I[k-r]];

      /* prepare to "execute" generate(i+1, r-1) */
      if(r > 1)
        I[k-(r-1)] = I[k-r] + 1;      /* equivalent of "s = i+1" */

      /* if the new call has r = 0, no need to init its ’i’ */

      I[k-r]++;

      /* make the recursive call */
      r = r - 1;
    }
    else
    {
      /* all iterations have already completed */
      /* "return" to the caller */
      r = r + 1;
    }
  }
}