生成 int 的排列，其中给定索引处的位为 0

Question

我需要生成 n 位数字的所有 2^(n-1) 种排列，其中索引

i

处的位始终为

0

且

j

是排列数。这是一个简单的表格，说明当

i

从 0 变化到 2 并且 n 为 3 时，因此 j 从 0 变化到 3。结果是一个 3 位数字，因此 n 为 3，可能的排列数为 4。

j   0 1 2 3
i
0   0 2 4 6
1   0 1 4 5
2   0 1 2 3

或二进制：

j    00  01  10  11
i
00  000 010 100 110 // Note the LSB (1s place) bit is never set in this line
01  000 001 100 101 // The 2s place bit is not set in this line
10  000 001 010 011 // The 4s place bit is not set in this line

这是我能想到的最好的：

unsigned result = (j&1)<<(i==0)|(j&2)<<(i!=2);

但是，对于这样一个看似简单的任务，这个解决方案似乎非常麻烦，并且仅适用于上述表格，不适用于 n 或

i

的任意值。

谁能想到一种更通用、更有效的方法来生成第 i 位始终为 0 的 n 位数字的所有排列？

Answer 1

你要求的东西比不起作用的东西“更简单”。对我来说，最好从获得真正有效的东西开始。一旦掌握了这些，您就可以寻求改进和优化。

这里值得的是一个应该可以工作的函数（为了简单起见，省略了边界检查）：

unsigned f(unsigned j, unsigned i)
{
    unsigned mlow = (1 << i) - 1;
    unsigned mhigh = ~mlow << 1;
    return (2*j & mhigh) | (j & mlow);
}