发电机组算法实现

Question

什么是幂集算法的良好实现

最近我需要这个算法为我的益智游戏构建一个解算器。通常，解算器应尝试策略（轮次集、可能的轮次功率集），并找到形成解决方案的策略

我发现Wikipedia page所示的朴素实现以及^{}库中的朴素实现不能提供生成子集中项目的稳定顺序

此外，利用集合对自然数集合的双射并遵循二进制表示的朴素方法受到源集合大小的限制

这种限制自然产生于这样一个事实，即所提到的库在内部使用32位整数值来生成子集

Answer 1

可能，Stackoverflow不是共享Gist片段的最佳选择，但相关问题仍然存在，我决定在这里分享我的片段，我坚信它可能对寻找幂集算法实现的人和Stackoverflow社区本身有用

https://gist.github.com/vladignatyev/e76b5fd1c3cdfff7034ce17506fae36e

我的实现可能很难理解。请免费与我分享您对这一开源软件的问题、改进和建议

Usage:
    >>> ps = power_set([1,2,3])
    >>> for ss in ps:
            print(ss)
Output:
    [], 
    [1], 
    [2], 
    [3], 
    [1, 2], 
    [1, 3], 
    [2, 3], 
    [1, 2, 3]

供您参考，我将代码移植到纯Swift 5，不需要依赖项。退房>https://gist.github.com/vladignatyev/7e9399930cb614d6251a4f82b8e75ff1

Answer 2

使用来自itertools recipes的实现：

from itertools import chain, combinations

def powerset(iterable):
    "powerset([1,2,3])  > () (1,) (2,) (3,) (1,2) (1,3) (2,3) (1,2,3)"
    s = list(iterable)
    return chain.from_iterable(combinations(s, r) for r in range(len(s)+1))

print(*powerset([1,2,3])) 

输出：

() (1,) (2,) (3,) (1, 2) (1, 3) (2, 3) (1, 2, 3)

它会生成元组，但您可以随意转换它们。它看起来也比您的解决方案短得多