使用位掩码进行N选K位排列

Question

我正在尝试找到/创建一个位操作算法，用于生成在N位计数掩码中所有K个1位的排列组合，其中K < N。排列数量为(N选择K) = N！/(K！(N-K)！)。 这两个来自Bit Twiddling Hacks的算法很接近。

unsigned int v; // current permutation of bits where bitCount(v) == K
unsigned int w; // next permutation where bitCount(w) == bitCount(v)

unsigned int t = v | (v - 1);
w = (t + 1) | (((~t & -~t) - 1) >> (trailingZeroCount(v) + 1)); 

同样。

unsigned int v; // current permutation of bits where bitCount(v) == K
unsigned int w; // next permutation where bitCount(w) == bitCount(v)

unsigned int t = (v | (v - 1)) + 1;  
w = t | ((((t & -t) / (v & -v)) >> 1) - 1);

这些算法按字典顺序生成排列，但我并不一定需要。然而，我确实需要一个包含位掩码 m 的算法。

unsigned int m; // bitmask from which next permutation is chosen
                // where bitCount(m) == N
unsigned int v; // current permutation of bits where (v & m) == v
                // and bitCount(v) == K
unsigned int w; // next permutation of bits where (w & m) == w
                // and bitCount(w) == bitCount(v)
...

- Warren Whipple

Answer 1

一种选择是使用CPU指令，例如Intel Haswell及更高版本中的PEXT，将您提到的位操作解决方案扩展为掩码。如果没有这样的指令可用，则可能需要循环。我在this answer中提供了两种可能性。

- Falk Hüffner