Алгоритм возврата комбинаций k элементов в определенном круге
Он предназначен для раскраски диска с n круглыми коронками и m секторами, используя k различных цветов (названия цветов можно переключать по номерам). Для того, чтобы картина дисков была немного разнообразна, но различия должны быть размытыми, картина должна соответствовать следующим правилам:
1- каждый сектор в каждой короне имеет только один цвет
2- не может быть двух секторов с одинаковыми настройками цвета
2-два соседних сектора могут отличаться по цвету только от одной из своих коронок
С диска с n=2, m=9 e K=3 мы можем получить этот список
[
[ "red"; "red" ],
[ "red"; "green" ],
[ "red"; "blue" ],
[ "green"; "blue" ],
[ "blue"; "blue" ],
[ "blue"; "green" ],
[ "green"; "green" ],
[ "green"; "red" ],
[ "blue"; "red" ] ]
Как вы можете видеть, последний сектор объединяется с первым в предложенных условиях...
Из дисков ниже, оба с n = 3, m = 8 и k = 2, только один слева окрашен в соответствии с правилами. Как и тот, что справа, это не "черно-бело-черный" шаблон, который повторяется, так как соседние секторы отличаются большей частью короны (сектор выше отличается от соседних соседей) более внутренним.
введите описание изображения здесь
Я пробовал некоторые алгоритмы, такие как использование простых комбинаций, но это не работает, потому что это круг, поэтому последний набор цветов должен совпадать с первым.
1 ответ
Насколько я понимаю, этот вопрос требует алгоритма для генерации циклического k-го кода Грея длины n. (Я предполагаю, что намерение состоит в том, чтобы m всегда было точно k n, чтобы в круге присутствовали все возможные цветовые последовательности. См. Ниже примечание о том, как бороться с нахождением более коротких последовательностей Грея.)
Код Грея - это система кодирования, в которой последовательные коды имеют расстояние Хэмминга 1; то есть они отличаются только одной позицией. Хотя самый обычный код Грея является двоичным, концепция и алгоритм могут быть легко расширены до базы k для любого k.
Классический двоичный код Грея формируется из двоичного числа путем кумулятивного XOR-преобразования цифр "слева направо" (т. Е. Сначала старшего разряда). Следующий алгоритм, скопированный без изменений из Википедии, заменяет XOR на "сумма по модулю k "; это также работает, если k равно 2, потому что XOR является точно суммой своих аргументов по модулю 2. [Примечания 1 и 2]
Я добавил программу-драйвер, которая распечатывает k n различных последовательностей для любой n- длины последовательности k цветов, повторяя первую строку, чтобы прояснить, что она циклическая.
На самом деле, легко доказать, что последняя последовательность отличается только в одной позиции от первой последовательности, так как результат применения алгоритма к k n − 1, который является числом base- k, полностью состоящим из цифры k -1, имеет 0 в каждой позиции, кроме первой позиции.
// The following was copied without modification from
// https://en.wikipedia.org/w/index.php?title=Gray_code&oldid=869851753#n-ary_Gray_code
// inputs: base, digits, value
// output: Gray
// Convert a value to a Gray code with the given base and digits.
// Iterating through a sequence of values would result in a sequence
// of Gray codes in which only one digit changes at a time.
void toGray(unsigned base, unsigned digits, unsigned value, unsigned gray[digits])
{
unsigned baseN[digits]; // Stores the ordinary base-N number, one digit per entry
unsigned i; // The loop variable
// Put the normal baseN number into the baseN array. For base 10, 109
// would be stored as [9,0,1]
for (i = 0; i < digits; i++) {
baseN[i] = value % base;
value = value / base;
}
// Convert the normal baseN number into the Gray code equivalent. Note that
// the loop starts at the most significant digit and goes down.
unsigned shift = 0;
while (i--) {
// The Gray digit gets shifted down by the sum of the higher
// digits.
gray[i] = (baseN[i] + shift) % base;
shift = shift + base - gray[i]; // Subtract from base so shift is positive
}
}
/* Here is a simple driver program to demonstrate the sequence */
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
int main(int argc, char* argv[]) {
if (argc < 3) {
fprintf(stderr, "Usage: %s N colour...\n", argv[0]);
argv = (char*[]){"3", "red", "green", "blue"};
}
unsigned n = atoi(argv[1]);
unsigned k = argc - 2;
argv += 2;
int maxlen = 1;
for (unsigned i = 0; i < k; ++i) if (strlen(argv[i]) > maxlen) maxlen = strlen(argv[i]);
maxlen += 1;
unsigned gray[n];
unsigned count = 1; for (unsigned i = n; i; --i) count *= k;
for (unsigned v = 0; v <= count; ++v) {
toGray(k, n, v, gray);
for (unsigned i = 0; i < n; ++i) printf("%-*s", maxlen, argv[gray[i]]);
putchar('\n');
}
return 0;
}
Вот несколько примеров выполнения этого кода:
./graynk 3 cyan yellow magenta ./graynk 2 red green blue ./graynk 3 black white
cyan cyan cyan red red black black black
yellow cyan cyan green red white black black
magenta cyan cyan blue red white white black
magenta yellow cyan blue green black white black
cyan yellow cyan red green black white white
yellow yellow cyan green green white white white
yellow magenta cyan green blue white black white
magenta magenta cyan blue blue black black white
cyan magenta cyan red blue black black black
cyan magenta yellow red red
yellow magenta yellow
magenta magenta yellow
magenta cyan yellow
cyan cyan yellow
yellow cyan yellow
yellow yellow yellow
magenta yellow yellow
cyan yellow yellow
cyan yellow magenta
yellow yellow magenta
magenta yellow magenta
magenta magenta magenta
cyan magenta magenta
yellow magenta magenta
yellow cyan magenta
magenta cyan magenta
cyan cyan magenta
cyan cyan cyan
Теперь коротко рассмотрим случай, когда желательно получить неполную последовательность Грея длиной m < k n. Здесь я предполагаю, что k > 2, потому что для k = 2 не все значения m имеют решения. (В частности, если k равно 2, а m нечетно, решения не существует; это можно доказать с помощью простого аргумента четности.)
Сначала предположим, что m ≥ 2 k n − 1.
Я назову элемент в последовательности Грея финальным, если он отличается как от своего предшественника, так и от своего предшественника только в конечном положении. Видно, что конечные элементы появляются в сериях длиной k − 2, разделенных парами неконечных элементов. Последний элемент может быть удален, потому что его предшественник и его преемник также должны отличаться друг от друга только своей конечной позицией. Есть 2 k n − 1 не конечных элементов, и если m ≥ 2 k n − 1, мы можем удалить k n - m конечных элементов и при этом иметь последовательность Грея. Эта подпоследовательность может быть сгенерирована с помощью фильтра, который передает:
- не финальные элементы
- первые m -2 k n − 1 конечных элементов
Второй случай - это значения m, которые являются четными и меньшими, чем k '× k n-1, где k ' является наибольшим четным числом, не превышающим k. (То есть k 'равно k, если k четно, и k -1, если k нечетно.) В этом случае мы можем использовать подпоследовательность отраженного кода Грея. В частности, мы используем последовательность Грея для числа со смешанным основанием, веса цифр которого k 'для позиции старшего разряда и k для всех других цифр. Начнем с последовательностей:
- G n, последовательность, сгенерированная вышеуказанным алгоритмом
- & Gcirc; n, обратная последовательность, сгенерированная вышеуказанным алгоритмом
Теперь мы определим последовательность S следующим образом:
- S = G0 G n −1⟩ & 1 & Gcirc; n − 1⟩… ⟨k ' & Gcirc; n − 1⟩ (где ⟨x G⟩ означает G с
xприурочен к каждому элементу).
Должно быть понятно, что i-й элемент от начала S и i-й элемент от конца S отличаются только своей первой цифрой. Следовательно, мы можем использовать S для получения последовательности Грея длины 2 i для любого i вплоть до k '/ 2.
Наконец, если нам нужна последовательность длиной m, где m нечетно и меньше k '× k n − 1, мы можем использовать вышеупомянутую конструкцию, оставляя второй элемент в последовательности.
Заметки
Код помещает старшую цифру в последнюю позицию в массиве, так что "число" сначала печатается младшей цифрой. Это ничего не меняет, хотя в ретроспективе мне было бы лучше печатать последовательности задом наперед.
История редактирования Википедии показывает, что цитируемый код является предметом спора. На случай, если он снова исчезнет, я поместил в комментарии в коде URL с меткой времени (то есть постоянный).