c - 在 C 中生成数组值的所有可能组合

Question

我有一个从 0 到 k(0 <= k <= N)的 N 个值的数组，我需要生成 N 个值的所有可能组合

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);
}

对于这个测试 (N=2 K=2) 我有那些组合

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

你看到它开始生成但固定在一个点上，我找不到原因! ？

预期示例: 对于 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
               .....

Answer 1

这就是你的循环在 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

如您所见，generate() 中的 j for-loop 一直在 j 上调用模数，其结果将一旦参数 k 大于 j，始终为 j。

您需要的是一个嵌套的 for 循环，它将采用当前组合 (range [0..(k+1)^n]) 和当前数组索引 (range [0..n-1]) 在决定从 [0..k] 的集合中打印哪个值时考虑。

如果您将输出视为行和列，那么在最右边的列中，值应该在每一行上发生变化，从 0..k 开始迭代。在下一列中，值应该每隔 (k+1)th 行更改一次。在下一列中，该值应每隔 (k+1)^2 行更改一次。

例如，当 n = 3 和 k = 2 时，对于前 9 行，最右边的列应该看起来像 0,1,2,0,1,2,0,1,2 。中间列应类似于 0,0,0,1,1,1,2,2,2。最左边的列应该类似于 0,0,0,0,0,0,0,0,0。

因此，你最终会得到这样的结果:

   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");
   }