c++ - 根据位数集计算组合

Question

我需要计算在 0<=r<=n 的时间选择 r 的 n 个事物的所有可能组合，一种方法是生成 0 到 2^n-1 之间的数字。但是我需要生成这些数字，以便根据该数字中设置的位数对数字进行排序。对于 n=3:

0         // numbers with 0 bits set

1 2 4     // numbers with 1 bits set

3 5 6     // numbers with 2 bits set

7         // numbers with 3 bits set

我需要知道如何生成数字，以便它们按位集的递增/递减顺序排序？

Answer 1

实现常规算法以生成组合，但还保存一个额外的数组，您可以在其中存储根据 1 位集排序的数字。然后，对于生成的每个组合，将数字替换为位于相应位置的数字减去我描述的排序数组中的一个。