c++ - 枚举二进制序列

Question

假设我想枚举所有 4 位模式，即从 0 (0000) 到 15 (1111)。一种方法是“真值表”方法:

0000, 0001, 0010, 0011, 0100, 0101, 0110, 0111, ... 1111

这种方法相当于从十进制的 0 计数到 15。

另一种方法是使用格雷码，其中一次仅翻转一位:

0000, 0001, 0011, 0010, 0110, ... 1000

我如何以最小化位总和的顺序系统地枚举所有数字？例如，类似以下内容:

0000, 0001, 0010, 0100, 1000, 0011, 0101, 1001, 0110, 1010, 1001, 0111, 1011, 1101, 1110, 1111

对于 4 位示例。

最终，将其扩展到任何基础都会很好，但二进制情况似乎是最容易实现的。

编辑:我可能应该明确指出该方法必须是生成性的，即我无法计算所有可能的序列然后对它们进行排序；该解决方案必须按照与指定顺序类似的顺序迭代生成序列。

Answer 1

这个有点麻烦的黑客

unsigned next_combination(unsigned x)
{
  unsigned u = x & -x;
  unsigned v = u + x;
  x = v  + (((v ^ x) / u) >> 2);
  return x;
}

将允许您轻松枚举包含相同数量的 1 位(按升序排列)的所有无符号位组合。 (参见https://en.wikipedia.org/wiki/Combinatorial_number_system)

您可以使用此算法依次枚举所有具有 1 个 1 位、2 个 1 位、3 个 1 位等的组合。例如，对于最长 4 位的组合(如您的示例中所示)

#define N 4u

int main()
{
  for (unsigned k = 1; k <= N; ++k)
  {
    for (unsigned subset = (1 << k) - 1; 
         subset < (1 << N); 
         subset = next_combination(subset))
      printf("%X ", subset);

    printf("\n");  
  }
}

http://coliru.stacked-crooked.com/a/0c8327c5e0611eaa

上面的维基百科链接还包含更通用算法的描述，不依赖于任何位操作。