Насколько я понимаю, этот вопрос требует алгоритма для генерации циклического k -ного кода Грея длины n .(Я предполагаю, что намерение состоит в том, чтобы m всегда было точно k n , так что все возможные цветовые последовательности присутствуют вкруг. См. ниже примечание о том, как справляться с поиском более коротких последовательностей Грея.)
Код Грея - это система кодирования, в которой последовательные коды имеют расстояние Хэмминга 1;то есть они отличаются только одной позицией.В то время как самый обычный код Грея является двоичным, концепция и алгоритм могут быть легко расширены до базового k для любого k .
Формируется классический двоичный код Греяиз двоичного числа с помощью кумулятивной XOR цифры от «слева направо» (т.е. старшие цифры в первую очередь).Следующий алгоритм, скопированный без изменений из Wikipedia , заменяет XOR на «sum modulo k»;это также работает, если k равно 2, потому что XOR - это точно сумма по модулю 2 его аргументов.[Примечания 1 и 2]
Я добавил программу драйвера, которая распечатывает k n различных последовательностей для любых n -последовательность k цветов, повторяющая первую строку, чтобы прояснить, что она циклическая.
На самом деле, легко доказать, что последняя последовательность отличается толькоодна позиция из первой последовательности, так как результат применения алгоритма к k n -1, который является основанием- 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
Теперь кратко рассмотрим случай, когда желательно получить неполную последовательность Грея длиной м <<em> k n .Здесь я предполагаю, что k > 2, потому что для k = 2 не все значения m имеют решения.(В частности, если k равно 2 и m нечетно, решения не существует; это можно доказать с помощью простого аргумента четности.)
Сначала предположим, что m ≥ 2 k n − 1 .
Я назову элемент в последовательности Грея final , если он отличается как от своего предшественника, так и от своего предшественника только в конечном положении.Можно видеть, что элементы final появляются в сериях длиной 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 , последовательность, сгенерированная по вышеуказанному алгоритму
- Ĝ n , обратная последовательность, сгенерированная вышеуказанным алгоритмом
Теперь мы определим последовательность S следующим образом:
- S = ⟨0 G n -1 ⟨⟨1 Ĝ n −1 ⟩… ⟨ k ' Ĝ n -1 ⟩ (где ⟨x G ⟩ означает G с
x, добавленным к каждому элементу).
СледуетСледует иметь в виду, что i -й элемент от начала S и i -й элемент от конца S отличаются тольков их первой цифре.Следовательно, мы можем использовать S для получения последовательности Грея длиной 2 i для любого i до k '/ 2.
Наконец, если нам нужна последовательность длиной м , где м нечетно и меньше k '× k n − 1 , мы можем использовать вышеупомянутую конструкцию, оставляя второй элемент в последовательности.
Примечания
Код помещает старшую цифру в последнюю позицию в массиве, так что «число» сначала эффективно печатается младшей цифрой.Это ничего не меняет, хотя в ретроспективе мне лучше было бы печатать последовательности задом наперед.
История редактирования Википедии показывает, что цитируемый код является предметом спора.На случай, если он снова исчезнет, я добавлю в комментарий в коде URL с меткой времени (т.е. постоянный).