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

Question

虽然我知道如何生成所有(n 选择 k)大小为 n 且恰好为 k 的位串位设置为 1，我正在努力寻找一个双射，它将 1 和 (n 选择 之间的数字 i 作为输入k) 并以任意顺序输出该类型的第 i 个向量。

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

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

Answer 1

最直接的方式:

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