Как сгенерировать неповторяющиеся комбинации, меняя только один элемент за раз

Полное условие задачи звучит так: «У вас есть пустое помещение и группа людей снаружи. За один ход вы можете либо позволить одному человеку войти в помещение, либо выпустить из него одного человека. Можете ли вы предложить серию ходов, при которой каждая возможная комбинация людей находится в помещении только один раз».

Нужно время, чтобы понять, чего именно хочет от вас интервьюер. Разобраться в этом помогает простой пример. Скажем, за порогом находятся два человека, Ларри и Сергей. Возможны четыре комбинации их присутствия в комнате, учитывая тот случай, когда в комнате вообще никого нет.

Вот они:

• В помещении никого нет.
• В помещении только Ларри.
• В помещении только Сергей.
• В помещении Ларри и Сергей.

Вопрос заключается в том, можем ли мы начать с того, что в комнате никого нет, а затем пройти указанную последовательность шагов? Мы помним, что только один человек может входить в комнату и покидать ее за один раз, и никакие шаги не могут повторяться даже в течение доли секунд. Так что следовать указанному порядку не удастся, потому что нельзя перейти от «только Ларри» к «только Сергею» за один шаг. Либо Ларри покивает комнату до того, как в нее войдет Сергей, но в этом случае мы повторяем шаг «никого нет», либо Сергей входит до того, как Ларри выходит, и в этом случае в какой-то момент в комнате находятся оба. Решение здесь другое.

1. В помещении никого нет.
2. Пусть Ларри войдет в помещение.
3. Пусть теперь в него войдет Сергей, чтобы получился вариант «Ларри и Сергей».
4. Ларри выходит, и в помещении остается только Сергей.

Это простой случай, а вас просят универсальный вариант, подходящий для любого возможного числа людей N. Каждый человек может входить в помещение или выходить из него, что означает, что число комбинаций с увеличением N возрастает по экспоненте, так что подбирать варианты вручную нереально. Потребуется хороший алгоритм.

Для решения этой задачи есть два обычных пути. Один из них — начать с небольшого числа и наращивать его. Мы уже знаем, как решить эту задачу для двух человек. Добавим третьего участника — Эрика. Как он изменит ситуацию? На базовом уровне это означает, что нам нужно повторить шаги для двух человек дважды, без Эрика и с Эриком. Итак, в помещении никого нет.

• Пусть Ларри войдет в помещение.
• Пусть теперь войдет Сергей, чтобы получился вариант «Ларри и Сергей».
• Ларри выходит, и в помещении остается только Сергей.

Затем появляется Эрик.

• Эрик входит и присоединяется к Сергею.

Мы хотим повторить шаги, теперь уже с Эриком. Но нам надо повторять их в обратном порядке, поскольку мы начинаем там, где шаг № 4, при котором Сергей остается один в помещении, уже сделан. Фактически, мы меняем направленность движений Ларри и Сергея, то есть каждый их вход становится их выходом и наоборот. Все это время Эрик остается в помещении. Вот остальная часть инструкций:

• Ларри вошел к Сергею и Эрику.
• Сергей выходит, оставляя Ларри и Эрика.
• Ларри выходит, оставляя Эрика.

Вот шаблон для алгоритма. Пусть теперь героев четверо. Вы проводите указанные восемь шагов, а затем добавляете шаги с четвертым человеком. При четырех участниках общее количество шагов составляет 16. Число шагов при каждом следующем участнике возрастает вдвое. Если у нас n человек, то необходимо сделать 2n шагов.

В самом широком смысле этот вопрос относится к столкновению аналогового и цифрового процессов. Люди входят и выходят — это аналоговый процесс. Вы не можете мгновенно перенести человека из одного места в другое, как это можно сделать с цифрами. С подобным столкнулись уже в начале информационной эпохи. В те годы, когда возник первый вал цифрового Джаггернаута, Фрэнк Грей был ученым в Bell Labs. Грей разработал многие принципы, лежащие в основе цветных телевизионных передач. Его имя хорошо знают благодаря коду Грея, придуманному им в середине 1940-х годов.

Вначале телевидение было только аналоговым. Электронный луч горизонтального сканирования отклонялся вверх и вниз при помощи магнитного поля, создаваемого все время меняющимся напряжением. Грей хотел перевести аналоговое напряжение в цифровое значение (серию закодированных импульсов). У инженеров того времени было довольно специфическое понимание (скорее близкое к знаниям, почерпнутым из научно-фантастической литературы, а не научным) того, как можно направить электронный луч через маску с отверстиями, представляющими бинарные числа. Разные части маски, соответствующие разным углам отклонения, имели разные шаблоны отверстий. Луч должен был определять необходимое напряжение, выраженное в бинарных числах. Как и многие другие умные идеи, на практике она не работала. Электронные лучи двигались неупорядоченно. Скорее происходящее напоминало стрельбу из водяного пистолета по нашкодившему коту.

Главная проблема заключалась в том, что при переходе луча от одного числа, соответствующего напряжению, к другому возникали ошибочные считывания. Чтобы добиться нормальной работы Грею потребовался числовой код, где при переходе от числа к числу менялась только одна цифра. Такая система теперь называется кодами Грея. Вы можете создать их при любом основании, в том числе и при 10, но самым известным примером этого рода является бинарный код Грея. Он представлен на рисунке ниже.

Цифры в коде Грея не представляют степени 2 или чего-то другого реального. Это всего лишь код. Код 111 означает 5, и вам не следует пытаться извлечь из него что-то еще. Единственная причина существования кода Грея в том, что каждый номер может быть сгенерирован из предыдущего путем изменения всего одной цифры. Чтобы перейти от 5 (111) к 6, вам всего лишь нужно изменить среднюю цифру (и получится 101).

Грей придумал простую процедуру генерирования своих кодов. Начнем с 0 и 1. Они присваиваются обычным числам 0 и 1 (никакого фокуса в этом нет). Затем нолик и единичка идут в обратной последовательности — 1 и 0, и эти варианты добавляются к первым двум. Мы получаем 0, 1 и 1, 0.

Чтобы отличить исходную последовательность от обратной, необходимо слева от каждого кода добавить дополнительную цифру. Используем 0 для исходной последовательности и 1 для обратной версии. Это дает 00, 01, 11, 10.

Это первые четыре кода Грея. Хотите еще? Поставьте эту последовательность в обратном порядке, добавьте ее к первоначальной, и вы получите 00, 01, 11, 10, 10, 11, 01, 00. Затем добавьте нолик к первым четырем кодам и единичку к последним четырем: 000, 001, 011, 010, 110, 111, 101, 100.

Вот почему шестерку можно представить, как 101. Вы сможете без всякого труда понять, что у числа 8 код равен 1100. Схему Грея можно легко расширить до любого значения.

Коды Грея являются цикличными. Представьте, что вам удалось проехать на автомобиле миллион миль. На одометре появилось 999 999, а затем значение меняется на 000 000 (никакого миллионного числа нет). При использовании кодов Грея последнее число также возвращается к первому, но меняется всего на одну цифру. В приведенной выше таблице самое высшее число (100) можно изменить на самое низшее (000), всего лишь поменяв один бит.

Код Грея может быть использован и для решения нашей задачи. Любой инженер, решая эту задачу, должен связать ее с кодами Грея.

Представьте помещение в виде числа из n цифр, где n — количество людей. Каждая цифра соответствует разному человеку. Цифра 1 — человек находится в помещении, цифра 0 — пусто. Вот пример.
Каждое возможное бинарное число из n цифр (их 2n) представляет разную группировку людей. Нам необходимо составить цикл со всеми возможными группировками. Обычный порядок подсчета с бинарными цифрами не работает. А вот коды Грея здесь себя проявят отлично. Надо всего лишь пройти по кодам Грея в порядке их расположения, начав с 0000000000, интерпретировать их как этапы решения задачи. (Например, смена с 0 на 1 справа означает «Ларри вошел».) Решение начинается таким образом.

• 0000000000: помещение является пустым
• 0000000001: вошел Ларри
• 0000000011: Сергей присоединился к Ларри
• 0000000010: Ларри вышел
• 0000000110: Эрик присоединился к Сергею

Это гарантирует, что на каждом шаге меняется только одна цифра и что только один человек входит в помещение или выходит из него.

Код Грея — это отмычка ко многим классическим загадкам, особенно таким, как «Башни Ханоя» и «Китайские кольца». Возможно, вы не бывали ни в Ханое, ни в Китае, но это неважно. К Азии это не имеет никакого отношения. А вот в жизни вы с этими загадками скорее всего встречались. В Башнях Ханоя имеется восемь цилиндрических дисков, надетых на один из трех штырей (внизу самый большой, вверху самый маленький). Игрок должен переместить все восемь дисков на другой штырь. Ограничение: нельзя класть диск на диск меньшего размера. Задача «Башня Ханоя» стала клише для видеоигр жанра «квест» (таких как Mass Effect, Zork Zero и «Звездные войны: рыцари Старой республики»). Все студенты, изучающие компьютерные науки, изучают и коды Грея, поэтому им часто на занятиях дается задание написать код для игры «Башни Ханоя» (который они должны использовать в видеоигре).

Разбор головоломки по книге «Действительно ли Вы достаточно умны, чтобы работать в Google?»