algorithm - (n 选择 k) 和长度为 n 且设置了 k 位的位串之间的双射

Question

虽然我知道如何生成所有 ( nchoose k) 大小n的位串，位串完全k设置为 1，但我正在努力寻找一个双射，它以和 ( choose )i之间的数字作为输入，并在一个任意排序。1nki

显然，可以简单地枚举列表中的所有向量，然后输出列表的i第 - 个条目，但不幸的是，这种方法对我的设置有很高的内存要求。

编辑：它也应该是一种有效的计算，计算每次调用双射的所有向量列表也不是一种选择。

Answer 1

直截了当的方法：

如果i < (n-1 choose k)，则最左边的位为0，并且i递归地确定其余位。否则，最左边的位是1，并且i - (n-1 choose k)递归地确定其余位。在第二种情况下，最多有(n-1 选择 k-1)个i - (n-1 选择 k)的可能值。