generate all possible combinations of array values in C

Question

I have an array of N values from 0 to k (0 <= k <= N), I need to generate all possible combinations of N values

void generate(int n, int k) {
   int q = -1;
   char res = '|';
   int r; 
   int j;
   for (j = 1; j <= n; j++) {
       q = j / (k + 1);
       r = j % (k + 1);
       printf("%d %c", r, res);
    }
}
int main() {
   int n = 2;
   int k = 2;
   int i, nbr_comb; 
   nbr_comb = pow((k + 1), n); number of combinations

   for (i = 0; i < nbr_comb; i++) {
       generate(n, i);
       printf("\n");
   }
   return (EXIT_SUCCESS);
}

for this test (N=2 K=2) I had those combinations

0 |0 |
1 |0 |
1 |2 |
1 |2 |
1 |2 |
1 |2 |
1 |2 |
1 |2 |
1 |2 |

you see that it begins to generate but it fixed at a point, I can't find why ! ?

Expected Examples: for n=2 k=2 n=3 k=2

0 0            0 0 0
0 1            0 0 1  
0 2            0 0 2
1 0            1 0 0
1 1            1 0 1 
1 2            1 0 2
2 0            1 1 0 
2 1            1 1 1
2 2            1 1 2
               1 2 0
               1 2 1 
               1 2 2
               2 0 0
               .....

Possible duplicate of [Algorithm to return all combinations of k elements from n](http://stackoverflow.com/questions/127704/algorithm-to-return-all-combinations-of-k-elements-from-n) — Random Davis, Dec 01 '16 at 21:09
I did read this, it's not combinations it's permutations, it doesn't accept duplicate k values in N, in my case I need all possible combinations even those with duplicate value like (0|0|1 - 2|1|2 ...) — devhicham, Dec 01 '16 at 21:15
What's wrong with https://rosettacode.org/wiki/Combinations_with_repetitions#C ? — deamentiaemundi, Dec 01 '16 at 21:34
This code just pick choices it doen't generate all possibilities — devhicham, Dec 01 '16 at 21:39
I don't think I fully understood what N and K stands for, but the expected result would be 000, 001, 002, 010,... 222. Right? — h4x0r, Dec 01 '16 at 22:06
I tried with different values of N and k it alaways begin to generate then been fixed at a point — devhicham, Dec 02 '16 at 13:02
Please add a section to your question depicting what your expected results are for N=2, k=2 and N=3, k=2. Based on your OP, I would think your expected results for N=2 (number of elements = 2) would be a list of 2 numbers per line, but your comments indicate the expected results would be 3 numbers per line. — lyst, Dec 02 '16 at 15:45
There are quite a few ways to generate all n-tuples. The best reference I can think of right away is TAOCP 7.2.1 — Yan Zhou, Dec 02 '16 at 18:36

score 1 · Accepted Answer · answered Dec 02 '16 at 18:32

This is how your loops unfurl at n=2, k=2:

for (i=0; i<nbr_comb; i++)
  i=0:  generate(2,0) -->   j=1:  1 mod 1 = 0
                            j=2:  2 mod 1 = 0
  i=1:  generate(2,1) -->   j=1:  1 mod 2 = 1
                            j=2:  2 mod 2 = 0
  i=2:  generate(2,2) -->   j=1:  1 mod 3 = 1
                            j=2:  2 mod 3 = 2
  i=3:  generate(2,3) -->   j=1:  1 mod 4 = 1
                            j=2:  2 mod 4 = 2
  i=4:  generate(2,4) -->   j=1:  1 mod 5 = 1
                            j=2:  2 mod 5 = 2
  i=5:  generate(2,5) -->   j=1:  1 mod 6 = 1
                            j=2:  2 mod 6 = 2
  i=6:  generate(2,6) -->   j=1:  1 mod 7 = 1
                            j=2:  2 mod 7 = 2
  i=7:  generate(2,7) -->   j=1:  1 mod 8 = 1
                            j=2:  2 mod 8 = 2
  i=8:  generate(2,8) -->   j=1:  1 mod 9 = 1
                            j=2:  2 mod 9 = 2

As you can see, your j for-loop in generate() just keeps calling modulo on j, the result of which will always be j once argument k is greater than j.

What you need is a nested for-loop that will take the current combination (range [0..(k+1)^n]) and the current array index (range [0..n-1]) into consideration when it decides which value to print from the set of [0..k].

If you think of the output as rows and columns, then in the right-most column, the value should change on each row, iterating from 0..k. In next column, the value should change every (k+1)th row. In next column, the value should change every (k+1)^2 row.

For example, when n = 3 and k = 2, then for the first 9 rows, the right-most column should look like 0,1,2,0,1,2,0,1,2. The middle column should look like 0,0,0,1,1,1,2,2,2. The left-most column should look like 0,0,0,0,0,0,0,0,0.

Thus, you end up with something like this:

   int n = 2;
   int k = 2;
   int row, col; 
   int cell;
   int rdiv;
   int nbr_comb = pow(k+1, n);

   for (row=0; row < nbr_comb; row++) 
   {
       for (col=n-1; col>=0; col--)
       {
           rdiv = pow(k+1, col);
           cell = (row/rdiv) % (k+1);
           printf("%d |", cell);
       }
       printf("\n");
   }

generate all possible combinations of array values in C

1 Answers1