int {1,2,3} 集合的组合是：
{},{1},{2},{1,2},{3},{1,3},{2,3},{1,2,3}
常见的解决方案是跟踪索引的代表性位掩码。
从我的 0-7 数字示例中：
000,001,010,011,100,101,110,111
该算法允许迭代解决方案，每次生成器遍历每个位并决定是否插入项目，因此它创建下一个运行时间为 O(n) 的组合。
格雷码：（来自维基百科）反射二进制码（RBC），在弗兰克格雷之后也被称为格雷码，是一种二进制数字系统，其中两个连续的值只有一位不同
如果我们只使用灰色数字，我们会得到这个数字范围：
000,001,011,010,110,111,101,100
结果以不同的顺序相同：
{},{1},{1,2},{2},{2,3},{1,2,3},{1,3},{3}
但在这里我们看到差异只有一项。是否可以使用格雷码范围在 O(1) 中实现生成器。
我知道如果迭代，返回的列表无论如何都会有 O(n) 运行时间。
增量和格雷码解决方案均摊销 O(1)，我相信这与您将获得的一样好。“摊销 O(1)”意味着您偶尔会在一次调用中获得更长的时间，但它们非常罕见，以至于k连续调用的总时间为 O(k)，因此一次调用的平均时间为 O(1) .
这比“预期的 O(1)”更有说服力，因为摊销的执行时间是对足够多的调用的总保证，而如果你非常不幸，预期的执行时间可能会产生意想不到的总时间。（在实践中，差异通常并不重要，但请参见例如针对“预期 O(1)”哈希表查找的 DoS 攻击。）
要了解增量算法为何摊销 O(1)，请查看每次迭代中翻转的位数。每第二次迭代（数字以 0 结尾），恰好翻转一位。每第四次迭代，恰好有两个位被翻转。每第八次迭代，恰好三个位被翻转。等等。很容易证明，在k迭代过程中，最大的2k +log2 k比特总数将被翻转。
对于格雷码算法，每次迭代只翻转一位，但必须找到该位。格雷码增量的简单迭代实现是保持当前选择的奇偶性。由于奇偶校验在每次迭代中都会发生变化，因此无需重新计算；它只是颠倒了。然后算法在两个规则之间交替：
如果奇偶校验为偶数，则翻转低位。
如果奇偶校验位为奇数，则将该位翻转到最低 1 位的左侧。
显然，选项 1 适用于一半的迭代，它显然只检查了一位。对于选项 2，我们需要弄清楚每次迭代检查了多少位。由于每个可能的位组合恰好出现一次，尾随零的数量遵循与整数增量序列相同的频率：每第二次，没有尾随零，每第四次有一个，每八次有两个，等等。
因此，最后，我们检查了两种解决方案中相同数量的低位。然而，格雷码解决方案在每次迭代中只改变集合中的一个元素，而增量解决方案改变了两个的摊销平均值。因此，如果集合修改代价高昂，格雷码算法可能会更好。
您可以将格雷码算法直接应用于集合，而无需传递位串，但它的性能将取决于集合实现的一些细节。奇偶校验继续交替如上（它也是集合模 2 的大小，因此如果您的集合具有 o(1) 大小操作，您可以使用它而不是维护状态）。我们假设您有一些 o(1) 函数将每个可能的集合元素映射到其后继元素（在全域中，而不是选择），这可能类似于位映射到集合元素的方式。那么两种可能的算法动作是：
偶校验：如果集合中的最小元素是宇宙中最小的元素，则删除该元素；否则添加它。
奇偶校验：如果集合中最小元素的后继也存在，则移除它；否则，添加它。
如果您需要在每次迭代时创建一个新集合，而不是修改当前选择集，那么您当然不能做得比 O(n) 更好，因为选择的摊销平均大小为 n/2，并创建一个集合时间不能少于它的大小。