Generate all possible array combinations in C - Optimal Graph Colouring

Question

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]

I guess I don't understand. How is `[1,1,2]` same as `[2,2,1]`? — noMAD, May 08 '13 at 15:05
[1,1,2] is the same of [2,2,1] because the values of numbers doesn't matter, just the fact that they're different. So, [1,1,2] is also the same thing of [400,400,3] or [0,0,9], for example. — Alexandre Paiva, May 08 '13 at 15:15
So `[3, 3, 3]` is the same as `[0, 0, 0]` and shouldn't be in your output? — Useless, May 08 '13 at 18:06
Just as `[3,3,2]` is the same as `[3,3,1]` is the same as `[1,1,2]` is the same as `[2,2,1]`. I suspect that no color (`0`) turns out to be the same as any color (`1`-`3`) in the given example. — StarPilot, May 08 '13 at 18:19
And for that matter, `[0,0,1]` is the same as `[0,0,2]` and `[0,0,3]` making for a remarkably short list of arrangements. Especially if `[0,1,0]` is also the same as `[0,0,1]` is the same as `[1,0,0]` (and we now know that `[1,0,0]` is the same as `[0,1,1]` and `[1,2,2]` and `[2,3,3]` and `[3,2,2]`. In other words, does ordering matter in this case or not? — StarPilot, May 08 '13 at 18:27

Rafael Baptista · Accepted Answer · 2013-05-08T21:58:41.940

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

   }
}

Oh, thanks! But actually, this helps my code a little but doesn't solve my problem. It's just using a fixed color for the first array position, but is still generating, for example, [0,3,3] and [0,2,2] and [0,1,1], which is the same thing. — Alexandre Paiva, May 08 '13 at 21:30
Now, this is exactly what i'm looking for, thanks! This reduces by 10 times the execution time of my code. You helped my a lot! — Alexandre Paiva, May 09 '13 at 18:01

Generate all possible array combinations in C - Optimal Graph Colouring

1 Answers1

Linked