c - 在 C 中生成所有可能的数组组合 - 最佳图形着色

Question

我需要生成包含所有可能组合的数组，就像我在这里找到的这个问题:

Combinatorics: generate all "states" - array combinations

我正在做一项简单的最佳图形着色工作，因此，我正在尝试生成所有可能的颜色组合(数组代表每个节点的颜色)。这段代码有效，但也在做不必要的工作。 在这种情况下，[1, 1, 2] 与 [2, 2, 1] 相同，我不需要再次测试这是否是有效图。

我想不出任何东西，但首先我想知道是否有一个简单的代码来做我想做的事。

现在，我的代码是这样的:

void generatearray(int array[], int array_size, int idx){

    int i;

    if(idx == array_size){
        putchar('\n');
        for(i = 0; i < array_size; i++) printf("%i ", array[i]);

    }
    else for(i = 0; i <= 3; i++){
        array[idx] = i;
        generatearray(array, array_size, idx+1);
    }

}

它会打印:

    [0, 0, 0]
    [0, 0, 1]
    [0, 0, 2]
    [0, 0, 3]
    [0, 1, 0]
    [0, 1, 1]
    ...
    [3, 3, 0]
    [3, 3, 1]
    [3, 3, 2]
    [3, 3, 3]

Answer 1

试试这个:

void generatearray( int array[], int array_size, int idx = 0, int fixed = 0 )
{
   int i;

   if ( idx == array_size )
   {
       putchar('\n');
       for( i = 0; i < array_size; i++ ) printf( "%i ", array[i] );

   } else {

       for( i = 0; i <= 3; i++ )
       {
          if ( fixed == i )
          {
             fixed++;
             array[idx] = i;
             return generatearray( array, array_size, idx + 1, fixed );
          }
          array[idx] = i;
          generatearray( array, array_size, idx + 1, fixed );
       }
   }
}

int arr[6];
generatearray( arr, 6 );

旧的破答案:

void generatearray(int array[], int array_size, int idx){

   int i;

   if(idx == array_size){
       putchar('\n');
       for(i = 0; i < array_size; i++) printf("%i ", array[i]);

   }
   else if ( idx == 0 ) {
       array[idx] = 0;
       generatearray(array, array_size, idx+1);
   } else {
       for(i = 0; i <= 3; i++){
       array[idx] = i;
       generatearray(array, array_size, idx+1);
       }

   }
}