Биекция между (n выбрать k) и цепочками битов длины n с установленным k битами

Question

Хотя я знаю, как сгенерировать все (n выбрать k) битовые строки размером n с точно k битами, установленными в единицу, я изо всех сил пытаюсь найти биекцию, которая получает в качестве входных данных число i между 1 и (n выберите k) и выводит i -ый вектор такого рода в произвольном порядке.

Очевидно, что можно просто перечислить все эти векторы в списке и затем вывести i -й элемент списка, но, к сожалению, такой подход требует высоких требований к памяти для моей настройки.

Редактировать: также это должно быть эффективное вычисление, вычисление списка всех векторов для каждого вызова биекции также не вариант.

Answer 1

Простой способ:

Если i <(n-1 выберите k) </strong>, то самый левый бит равен 0 и i определяет остаток битов рекурсивно.В противном случае самый левый бит равен 1 , а i - (n-1 выберите k) определяет рекурсивный остаток битов.Во втором случае самое большее (n-1 выберите k-1) возможные значения i - (n-1 выберите k) .