Задачи с бинарными последовательностями мне очень нравятся из-за их «эвристичности». Решение часто скрывается в двух шагах, но додуматься не просто.
Следующая задача описывается так — нужно сгенерировать n-разрядный «серый код».
Если вы не знакомы с тем, что такое GrayCode, то вот его краткое описание.
Двоичный код последовательности чисел называемый GreyCode, должен отличаться у соседних чисел всего в одном разряде. При этом последнее и первое числа также должны следовать этому правилу.
Пример серого кода для 2х разрядов: [00, 01, 11, 10].
Как выстроить последовательность для N разрядов? Давайте рассмотрим еще пару примеров кода: добавим gray code для n = 1 и 3.
Чтобы перейти от n = 1 к n = 2, я добавил к [0,1] тот же самый массив, но в обратном порядке, а также установил старший бит. Этот трюк позволил мне соблюсти правило серого кода внутри добавляемой последовательности — т.к. я её получил как бы на предыдущем шаге, а добавление старшего бита обеспечило граничные условия.
Рассмотрим вариант реализации:
Тяжелая артиллерия в виде функций работы с массивами в данном примере не удачный выбор, если требуется хорошее быстродействие. Оператор […] и функции reverse и map создают временные массивы, и каждый раз интерпретатор выполняет их поэлементный перебор по цепочке функций.
В данном случае обычный цикл for будет более эффективен.
