Код Грея для всех k подмножеств элементов {1,,n}

Я ищу алгоритм, который выполняет итерацию по всем k подмножествам элементов n набора элементов. Я не хочу генерировать все эти подмножества явно.

Для этого существует простой алгоритм, а именно лексографическая сортировка соответствующих битовых векторов с последующим переходом от текущего подмножества к следующему.

Тем не менее, я ищу алгоритм, который переключает только 2 бита на каждом шаге. Я читал, что такой код называется "кодом Грея", но не нашел алгоритма для своей проблемы.

Есть ли прямая реализация для этого?


gray-code
person mueldgog    schedule 06.05.2015    source источник
comment
Преобразование целого числа в код Грея тривиально, но я недостаточно уверен в том, что вы делаете, чтобы знать, действительно ли это ответ. Не могли бы вы привести пример или что-то в этом роде?   -  person harold    schedule 06.05.2015
comment
Что ж, требование похоже на код Грея, но я не думаю, что технически это код Грея. Коды Грея переключают только один бит, и если вы сделаете два шага в последовательности Грея, вы можете обнаружить, что два бита включаются, а не один включается и один выключается, и у вас не будет одинакового количества битов.   -  person sh1    schedule 06.05.2015

Ответы (1)


arrow_upward
1
arrow_downward

Это не будет полным ответом, но он также не поместится в комментарий.

Отношение к коду Грея, которое вам нужно, — это зеркальное отображение. Каждый раз, когда код Грея устанавливает новый бит, все биты ниже него перемещаются назад с этой точки (до тех пор, пока этот бит не будет очищен или бит выше, что реверсирует).

Чтобы воспроизвести это с вашим лексикографическим порядком, вам нужно инвертировать порядок, в котором вы перебираете оставшиеся биты после каждого обмена.

Возможно, вы сможете реализовать это как итеративное преобразование, принимая ваш обычный порядок и неоднократно меняя порядок оставшихся битов на противоположный каждый раз, когда вы сталкиваетесь с переходом от 1 к 0.

person sh1    schedule 07.05.2015