生成幂集算法实现

Question

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

最近我需要这个算法来为我的益智游戏构建求解器。一般来说，求解器应该尝试策略（轮次集，可能的轮次Power Set）并找到形成解决方案的策略。

我发现，Wikipedia page, as well as one from js-combinatorics 库中显示的简单实现不提供生成子集中项目的稳定顺序。

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

由于上述库在内部使用 32 位整数值生成子集这一事实自然会产生这种限制。

Answer 1

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

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)

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

生成幂集算法实现

Generating Power Set algorithm implementation

python

algorithm

combinatorics

powerset