生成C中的所有可能的组合阵列 - 最优图着色问题 [英] Generate all possible array combinations in C - Optimal Graph Colouring

问题描述

我需要生成与所有可能的组合阵列，像这样的问题，我已经在这里找到：

<一个href=\"http://stackoverflow.com/questions/9632677/combinatorics-generate-all-states-array-combinations\">Combinatorics:生成所有＆QUOT;国家＆QUOT; - 阵列组合

我做的优化图形着色的简单的工作，所以，我想生成所有可能的颜色组合（数组重新presents每个节点的颜色）。这code是工作，但也做不必要的工作。 在这种情况下，[1，1，2]是同样的事情[2，2，1]，我并不需要测试，如果这是一个有效的图形再次

我想不出任何东西，但首先我想知道如果有一个简单的code做我想做的。

现在，我的code是这样的：

 无效generatearray（int数组[]，INT ARRAY_SIZE，INT IDX）{    INT I;    如果（IDX == ARRAY_SIZE）{
        的putchar（'\\ n'）;
        对于（i = 0; I＆LT; ARRAY_SIZE;我++）的printf（％i的，数组[我]）;    }
    其他的（I = 0;我LT＆= 3;我++）{
        数组[IDX] =我;
        generatearray（数组，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]
 

解决方案

试试这个：

 无效generatearray（int数组[]，INT ARRAY_SIZE，INT IDX = 0，INT固定= 0）
{
   INT I;   如果（IDX == ARRAY_SIZE）
   {
       的putchar（'\\ n'）;
       对于（i = 0; I＆LT; ARRAY_SIZE;我++）的printf（％i的，数组[我]）;   }其他{       对于（i = 0; I＆LT; = 3;我++）
       {
          如果（固定== I）
          {
             固定++;
             数组[IDX] =我;
             返回generatearray（数组，ARRAY_SIZE，IDX + 1，固定）;
          }
          数组[IDX] =我;
          generatearray（数组，ARRAY_SIZE，IDX + 1，固定）;
       }
   }
}INT ARR [6];
generatearray（ARR，6）;
 

破旧的回答：

 无效generatearray（int数组[]，INT ARRAY_SIZE，INT IDX）{   INT I;   如果（IDX == ARRAY_SIZE）{
       的putchar（'\\ n'）;
       对于（i = 0; I＆LT; ARRAY_SIZE;我++）的printf（％i的，数组[我]）;   }
   否则如果（IDX == 0）{
       数组[IDX] = 0;
       generatearray（数组，ARRAY_SIZE，IDX + 1）;
   }其他{
       对于（i = 0; I＆LT; = 3;我++）{
       数组[IDX] =我;
       generatearray（数组，ARRAY_SIZE，IDX + 1）;
       }   }
}
 

I need to generate arrays with all possible combinations, like this question I've found here:

Combinatorics: generate all "states" - array combinations

I'm doing a simple work of optimal Graph Coloring, so, I'm trying to generate all possible color combinations (the array represents the color for each node). This code is working but, is also doing unnecessary work. In this situation, [1, 1, 2] is the same thing of [2, 2, 1], I don't need to test if this is a valid graph again.

I can't think of anything, but first I would like to know if there's a simple code for doing what I want to.

For now, my code is something like this:

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

}

And it will print:

    [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]

解决方案

Try this:

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

Old broken answer:

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

   }
}

这篇关于生成C中的所有可能的组合阵列 - 最优图着色问题的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！