什么算法可以计算给定集合的幂集？
https://stackoverflow.com/questions/2779094
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
Russian题
我想根据起始数字列表有效地生成唯一的数字组合列表。
示例开始 list = [1,2,3,4,5] 但该算法应该适用于 [1,2,3...n]
result =
[1],[2],[3],[4],[5]
[1,2],[1,3],[1,4],[1,5]
[1,2,3],[1,2,4],[1,2,5]
[1,3,4],[1,3,5],[1,4,5]
[2,3],[2,4],[2,5]
[2,3,4],[2,3,5]
[3,4],[3,5]
[3,4,5]
[4,5]
笔记。我不想要重复的组合，尽管我可以接受它们，例如在上面的示例中我并不真正需要组合 [1,3,2] 因为它已经呈现为 [1,2,3]
解决方案
您所问的问题有一个名称。它被称为 电源组.
谷歌搜索“幂集算法”让我找到了这个 递归解法.
红宝石算法
def powerset!(set)
return [set] if set.empty?
p = set.pop
subset = powerset!(set)
subset | subset.map { |x| x | [p] }
end
幂集直觉
如果 S = (a, b, c) 那么 动力组(S) 是所有子集的集合动力装置(S) = {(), (a), (b), (c), (a,b), (a,c), (b,c), (a,b,c)}
第一个“技巧”是尝试 定义 递归地。
什么是停止状态？
S = () 有什么 动力组（S）？
如何 得到 到它？
将集合减少一个元素
考虑取出一个元素 - 在上面的示例中，取出 {c}
S = (a,b) 那么 动力组(S) = {(), (a), (b), (a,b)}
缺什么？
动力组(S) = {(c), (a,c), (b,c), (a,b,c)}
嗯嗯
注意到有什么相似之处吗？再看看...
动力装置(S) = {(), (a), (b), (c), (a,b), (a,c), (b,c), (a,b,c)}
取出任意元素
动力装置(S) = {(), (a), (b), (c), (a,b), (a,c), (b,c), (a,b,c)} 是
动力装置(S - {c}) = {(), (a), (b), (a,b)} 并与
{c} U 动力装置(S - {c}) = { (c), (a,c), (b,c), (a,b,c)}
动力装置(S)= 动力装置(S-{e我}) U ({e我} U 动力装置(S-{e我}))
其中 e我 是 S 的一个元素（单例）
伪算法
- 该集合是否传递为空？完成（请注意，{} 的幂集为 {{}}）
- 如果没有，则取出一个元素
- 对集合的其余部分递归调用方法
- 返回由并集组成的集合
- 没有元素的集合的幂集（来自递归调用）
- 这同一组（即 2.1) 但其中的每个元素都与最初取出的元素合并
其他提示
只是数 0 到 2^n - 1 并根据计数的二进制表示形式打印数字。一种 1 表示您打印该号码和 0 意味着你不。例子：
set is {1, 2, 3, 4, 5}
count from 0 to 31:
count = 00000 => print {}
count = 00001 => print {1} (or 5, the order in which you do it really shouldn't matter)
count = 00010 => print {2}
00011 => print {1, 2}
00100 => print {3}
00101 => print {1, 3}
00110 => print {2, 3}
00111 => print {1, 2, 3}
...
11111 => print {1, 2, 3, 4, 5}
def power(a)
(0..a.size).map {|x| a.combination(x).to_a}.flatten(1)
end
与Hobodave的答案相同，但迭代和更快（在Ruby中）。它也与两者一起使用 Array 和 Set.
def Powerset(set)
ret = set.class[set.class[]]
set.each do |s|
deepcopy = ret.map { |x| set.class.new(x) }
deepcopy.map { |r| r << s }
ret = ret + deepcopy
end
return ret
end
在我的测试中，IVLAD的方法在Ruby中的工作不佳。
从OP的评论（副本编辑）：
该示例是我实际在做的事情的简化形式。数字是具有“数量”的对象
N在其他一些边界内 例如x < N < y.
您拥有的是一个优化问题。您假设的是，解决此优化问题的正确方法是将其分解为枚举问题（这是您所要求的），然后将其分解为过滤问题（大概您知道该怎么做）。
您尚未意识到的是，这种解决方案也只能用于理论分析，或者（b）对于非常小的值 n. 。您要要求的枚举是指数的 n, ，这意味着您最终会花费太长时间在实践中运行的东西。
因此，弄清楚如何构成您的优化问题，编写一个新问题，然后编辑此问题以指向它。
递归和迭代解决方案，以计算方案中设置的功率。虽然未完全测试
(define (power_set set)
(cond
((empty? set) (list '()))
(else
(let ((part_res (power_set (cdr set))))
(append (map (lambda (s) (cons (car set) s)) part_res) part_res)))))
(define (power_set_iter set)
(let loop ((res '(())) (s set))
(if (empty? s)
res
(loop (append (map (lambda (i) (cons (car s) i)) res) res) (cdr s)))))
以下是一种递归解决方案，类似于已经发布的解决方案。一些断言正在提供单位测试。我没有设法使用“集合” python类型来表示一组集。 Python说，尝试像“ S.Add（set（set”）”这样的表达式时，“设置对象是不可用的”。
另请参见许多编程语言的解决方案 http://rosettacode.org/wiki/power_set
def generatePowerSet(s, niceSorting = True):
"""Generate power set of a given set.
The given set, as well as, return set of sets, are implemented
as lists.
"niceSorting" optionnaly sorts the powerset by increasing subset size.
"""
import copy
def setCmp(a,b):
"""Compare two sets (implemented as lists) for nice sorting"""
if len(a) < len(b):
return -1
elif len(a) > len(b):
return 1
else:
if len(a) == 0:
return 0
else:
if a < b:
return -1
elif a > b:
return 1
else:
return 0
# Initialize the power set "ps" of set "s" as an empty set
ps = list()
if len(s) == 0:
ps.append(list())
else:
# Generate "psx": the power set of "sx",
# which is "s" without a chosen element "x"
sx = copy.copy(s)
x = sx.pop()
psx = generatePowerSet(sx, False)
# Include "psx" to "ps"
ps.extend(psx)
# Include to "ps" any set, which contains "x"
# Such included sets are obtained by adding "x" to any subset of "sx"
for y in psx:
yx = copy.copy(y)
yx.append(x)
ps.append(yx)
if niceSorting:
ps.sort(cmp=setCmp)
return ps
assert generatePowerSet([]) == [[]]
assert generatePowerSet(['a']) == [[], ['a']]
assert generatePowerSet(['a', 'b']) == [[], ['a'], ['b'], ['a', 'b']]
assert generatePowerSet(['a', 'b','c']) == [[],
['a'], ['b'], ['c'],
['a', 'b'], ['a', 'c'], ['b', 'c'],
['a', 'b', 'c'] ]
assert generatePowerSet(['a', 'b','c'], False) == [ [],
['a'],
['b'],
['a', 'b'],
['c'],
['a', 'c'],
['b', 'c'],
['a', 'b', 'c'] ]
print generatePowerSet(range(4), True)
