algorithm - 将具有给定 popcount 的位串映射到整数

Question

我有一个返回给定长度 N 和给定 popcount k 的位串的过程，即每个位串恰好有 k 个和N - k 零。我需要计算每个位串返回的频率。目前，我使用关联的 base2 整数来递增 2^N 维数组中的计数器。然而，这对于较大的 N 变得不切实际，因为数组太大了。为了做得更好，我想利用我事先知道 popcount k 的事实，所以我只需要一个维度数组 M = N choose k 来存储计数。为此，我需要一个程序将给定的位串转换为唯一的整数，例如对于示例 N=3，k=2，以下映射就足够了:

011 → 1
110 → 2
101 → 3

请注意，我不需要反向映射，尽管它应该存在。这样的映射可能是什么？这是(相关的)已知问题吗？

Answer 1

正如 SaiBot 所建议的，您可以使用哈希集将唯一的位串映射到一个值。否则，您可以查找“排名排列”作为对 (n,k) 零和一的所有排列进行编号的方法。