(n选择k)与长度n为k位的位串之间的双射

Question

虽然我知道如何生成大小为1的所有(n bijection k)位串，但是我很难找到一个双射，它得到1和(n Selectk)之间的数字i，并以任意顺序输出这种i-th向量。

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

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

Answer 1

直截了当的方法：

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