Все возможные комбинации массивов (параллельное программирование) — оптимальная раскраска графика
Я снова делаю работу по оптимальной окраске графика, поэтому мне нужно сгенерировать все возможные цветовые комбинации (массив представляет цвет для каждого узла) для графика. Мне здесь очень помогли, как вы можете видеть в этом вопросе:
Генерация всех возможных комбинаций массивов в C — Оптимальная раскраска графика
На данный момент мой код:
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[3];
generatearray( arr, 3 );
Выход в этом случае будет:
0 0 0
0 0 1
0 1 0
0 1 1
0 1 2
Если 0 означает синий, а 2 означает красный, в раскраске Графика красный-красный-красный — это то же самое, что сине-синий-синий. Вот что делает мой код: он генерирует все возможные комбинации цветов для графа.
Теперь мне нужно улучшить свой код, но я ничего не мог придумать. Я хочу, чтобы он генерировал массивы только с заданным количеством цветов, потому что я использую pthreads и хочу, чтобы каждый поток имел дело с графиком с несколькими цветами.
Например: с 2 цветами, результат будет:
0 0 1
0 1 0
0 1 1
И с 3 цветами:
1 2 3
Мне не нужно создавать массивы с меньшим количеством цветов, чем набор чисел, так как есть другие потоки, которые делают это.
Кто-нибудь из вас, ребята, может помочь мне с моим кодом? Извините, если я не прояснил себя в любой момент.
Решение
так что вам нужно систематическое перечисление всех сюръективных отображений из множества V (#V = n) вершин в вашем графе в набор k элементы, представляющие k различные цвета вместе с дополнительным ограничением, что карта, ограниченная вершинами с наименьшим индексом среди всех других вершин, связанных с тем же цветом, должна быть строго монотонной (поскольку вас не интересует идентичность соответствующего цвета).
давайте предположим, что количество цветов будет фиксированным. сначала выберите наименьшие показатели представителей цвета, i_1, ..., i_k, по определению, i_1 < ... < i_k,
для любой из оставшихся вершин v, i_j < v < i_(j+1), его цвет может быть свободно выбран из { 1, ..., j },
это может быть реализовано с помощью следующего кода:
/*
* sample values
* K ist to be substituted with the number of colors to use and thus in actual usage scenarios will be a parameter of thread instantiation
*/
const K = 4;
const N = 10;
void
next_pattern ( int *out, int set_up_to, int *mins, int mins_seen ) {
int i;
int choice;
/* in-place updating: only elements 1..set_up_to are valid */
if (set_up_to < N) {
if (set_up_to + 1 == mins[mins_seen+1]) {
out[set_up_to + 1] = mins_seen+1;
next_pattern ( out, set_up_to + 1, mins, mins_seen+1 );
}
else {
for ( choice = 1; choice <= mins_seen; choice++ ) {
out[set_up_to + 1] = choice;
next_pattern ( out, set_up_to + 1, mins, mins_seen );
}
}
}
else {
/* coloring complete */
printf("[");
for (i=1; i <= N; i++) {
printf(" %u ", out[i]);
}
printf("];\n");
}
} /* next_pattern */
void
next_mindist ( int *mins, int issued, int *out ) {
int lo;
/* in-place updating: only elements 1..issued are valid */
if (issued < K) {
for ( lo = mins[issued] + 1; lo < N - issued; lo++ ) {
mins[issued+1] = lo;
next_mindist ( mins, issued+1, out );
}
}
else {
// min mapping complete
next_pattern ( out, 0, mins, 0 );
}
} /* next_mindist */void main ( char **argv, int *argc ) {
/* in-place arrays
* mins: minimum vertex index of color <index>
* out: current mapping vertex -> color (mostly partial during processing)
*/
int *mins = (int *) calloc ( sizeof(int), K + 2 ); /* supporting indices 1 .. K and upper guard to avoid conditional statements */
int *out = (int *) calloc ( sizeof(int), N + 1 ); /* supporting indices 1 .. N */
next_mindist ( mins, 0, out );
}
предостережение:
приведенный выше код компилируется и запускается, и его результаты появиться чтобы быть правильным. конечно его далекая форма формально проверяется … ;-).
Другие решения
Других решений пока нет …