5

Possible Duplicate:
Algorithm to return all combinations of k elements from n

Is there any iterative algorithm to generate combinations of N numbers taking 'r' at a time ?

Community
  • 1
  • 1
Mariselvam
  • 1,093
  • 2
  • 15
  • 28
  • can you post an example? – Nikita Rybak Jan 30 '11 at 18:02
  • Consider a set of 10 items: `A B C D E F G H I J`. If r=2, what do you expect? `AB BC CD DE EF FG GH GI IJ` or `AB AC AD AE AF AG AH AI AJ BC BD BE ...` ? – Aif Jan 30 '11 at 23:46
  • This subject has been deal with here: http://stackoverflow.com/questions/127704/algorithm-to-return-all-combinations-of-k-elements-from-n – Dave Jan 30 '11 at 23:46
  • 1
    @BilltheLizard Is this really a duplicate? The question asks for an **iterative** algorithm, which is not required by the other question, nor (I think) dealt with in the answers. – chiastic-security Oct 15 '14 at 20:39
  • 3
    This not a duplicate. It specifically asks for an iterative algorithm. – dev_nut Apr 15 '15 at 18:31
  • This not a duplicate. It specifically asks for an *iterative* algorithm. – erickson Jan 01 '20 at 02:45

1 Answers1

14

Yes there is.

Here is code from the wrong answer Library.

void generate_combos(int n, int k) {
    int com[100];
    for (int i = 0; i < k; i++) com[i] = i;
    while (com[k - 1] < n) {
        for (int i = 0; i < k; i++)
            cout << com[i] << " ";
        cout << endl;

        int t = k - 1;
        while (t != 0 && com[t] == n - k + t) t--;
        com[t]++;
        for (int i = t + 1; i < k; i++) com[i] = com[i - 1] + 1;
    }
}

This generates the combinations in lexicographic order.

Chris Hopman
  • 2,082
  • 12
  • 11