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

Question

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

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

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

Answer 1

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

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