长度为n且有k个位为1的比特串与(n取k)之间的双射

Question

长度为n且有k个位为1的比特串与(n取k)之间的双射

algorithmbitstringhammingweightbijection

3

虽然我知道如何生成大小为n，恰好有k个位设置为1的所有（n choose k）位字符串，但我很难找到一个双射，它以介于1和（n choose k）之间的数字i作为输入，并以任意顺序输出那种类型的第i个向量。

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

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

- Memphisd

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Matt Timmermans · Accepted Answer

简单明了的方法：

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