A Simple Algorithm for Generating Combinations: A Recursive Algorithm

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

A Recursive Algorithm

We will use a single array c of k elements to generate each k-combination in it one by one. Let c_i denote the array element c[i] for any index i. For any combination in c, say the elements c₀,c₁,c₂,…,c_k−1 have come from array a’s indices j₀,j₁,j₂,…,j_k−1 respectively. One intuitive idea is to generate each combination in c such that, for that combination, j₀ < j₁ < j₂ < … < j_k−1. That is, for each combination in c, the k elements appear in the same order in array a as they do in c.

Once we decide such ordering of elements in c, the following idea to generate any combination may come naturally to us. Pick c₀ from any of indices 0 to n−k of a; we can’t go further than n − k because we still need to pick (k − 1) elements from higher indices of a. If c₀ was picked from index j₀ of a, c₁ can be picked from any of indices j₀ + 1 to n − (k − 1), say j₁. Further, c₂ can be picked from any of indices j₁ + 1 to n − (k − 2), say j₂. And so on.

To generate every possible combination, this process can be repeated for every possibility of j₀,j₁,j₂,…,j_k−1 in the corresponding ranges.

The following recursive algorithm (implemented in C) is based on the above idea. generate(s,r) (s for “start”, r for “remaining”) generates all r-combinations of elements a[s] to a[n − 1] over indices (k − r) to (k − 1) of c. The initial call has s = 0 and r = k. print() prints the combination currently in c.

#define n 10
int a[] = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9};
int k;
int c[n];

void generate(int s, int r)
{
  int i;

  if(r == 0)
  {
    print();
    return;
  }

  for(i = s; i < n-r+1; i++)
  {
    c[k-r] = a[i];

    generate(i+1, r-1);
  }
}

void print()
{
  int i;

  for(i = 0; i < k; i++)
    printf("%d ", c[i]);

  printf("\n");
}

Consider the case when the elements of array a are in increasing order. We can prove that each combination generated by the above algorithm will have its elements in increasing order too. Further, these generated combinations are mutually ordered as per their lexicographical order. Note that the concept of a k-combination itself does not include any order for its k elements. Above we are referring to its representation in the array c, and any array has an intrinsic order of its elements.