Я возвращаюсь к старой проблеме, над которой я работал некоторое время назад.
Типичный сценарий: «3 бита устанавливаются в 8-битном целом числе», т.е. 00000111.
Все уникальные комбинации с 3 установленными битами могут быть легко созданы (по порядку) с помощью вложенных циклов. Меня интересует комбинация индекса отображения <->, т. Е. «00001011» будет второй комбинацией (или значением «1» в индексе, начинающемся с нуля).
До сих пор я просматривал все комбинации и сохранял их в таблице, делая поиск индекса -> разговор операцией O (1). Другое направление - O (ln (n)) с двойным поиском.
Недостатком, однако, является то, что это явно сказывается на памяти, если мы увеличиваем домен до такой степени, когда это невозможно.
Какой простой способ рассчитать n-ю комбинацию или индекс для данной комбинации? Порядок комбинаций был бы неплох, но не обязателен.
Ответы:
Генерирование n-й комбинации называется алгоритмом «unranking». Обратите внимание, что перестановки и комбинации часто можно приравнять к параметризации проблемы. Не зная точно, в чем заключается проблема, трудно порекомендовать точный правильный подход, и на самом деле для большинства комбинаторных задач обычно существует несколько различных алгоритмов ранжирования / исключения.
Один хороший ресурс - «Комбинаторные алгоритмы» Креера и Стинсона. В этой книге есть много хороших алгоритмов ранжирования и однозначных объяснений. Есть более продвинутые ресурсы, но я бы рекомендовал Kreher в качестве отправной точки. В качестве примера алгоритма отмены рейтинга рассмотрим следующее:
Это перестановка unranking, но, как уже упоминалось выше, во многих случаях вы можете преобразовать unranking комбинацию в эквивалентную задачу перестановки.
источник