生成功率集算法的实现

Question

Power Set算法的良好实现是什么？

最近，我需要此算法来为我的益智游戏构建求解器。通常，求解器应尝试策略（转数集，可能的转数Power Set）并找到构成解决方案的策略。

[我发现，Wikipedia page所示的简单实现以及js-combinatorics库中的一个实现未提供所生成子集中项目的稳定顺序。

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

此限制自然是由于上述库在内部使用32位整数值生成子集这一事实而发生的。

Answer 1

使用从js-combinatorics开始的实现：

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])) 

它会生成元组-但您可以根据需要进行转换。它看起来也比您的解决方案短得多。

Answer 2

[可能，Stackoverflow并不是共享Gist代码段的最佳选择，但是存在相关问题，我决定在这里共享我的代码段，并坚信对于寻求Power Set算法实现和Stackoverflow社区本身。

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

我的实现可能很难理解。请与我免费分享有关此开源软件的问题，改进和建议！

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

供您参考，我将代码移植到了纯Swift 5，不需要依赖项。签出->

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]

Answer 3

供您参考，我将代码移植到了纯Swift 5，不需要依赖项。签出->

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]