什么算法可以计算给定集合的幂集？

Question

我想要高效地生成一个基于给定数字列表的唯一组合列表。例如，给定起始列表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]出现了。

- ross

---

http://docs.python.org/library/itertools.html#itertools.combinations - kennytm

这看起来像是作业，所以我会提供问题而不是答案：你知道幂集有多少成员吗？（请注意，如果你的列表意图是幂集，则不完整）那个数字是否暗示了一种枚举它们的方法？巨大提示：二进制 - AakashM

可能是 https://dev59.com/xnI-5IYBdhLWcg3wy7wd 的重复问题。 - hobodave

不是作业。这个例子比我实际要做的简单。这些数字是拥有一个名为“Qty”的属性的对象，我想对每种可能的组合进行数量求和，然后选择使用最多对象的组合，其中数量总和在某些其他边界内，例如 > x < y。 - ross

与幂集相比，您的示例结果缺少空集、4个元素的5个子集、包含所有5个元素的子集以及集合[2,4,5]。 - Steve Jessop

Answer 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}

- IVlad

---

恭喜你给出了一个漂亮而高效的答案！ - Mihai Alexandru-Ionut

Answer 2

你所询问的有一个名称，它被称为幂集。

在Google上搜索"幂集算法"会导向这个递归解决方案。

Ruby算法

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)} 是

powerset(S - {c}) = {(), (a), (b), (a,b)}并上

{c} U powerset(S - {c}) = { (c), (a,c), (b,c), (a,b,c)}

powerset(S) = powerset(S - {e_i}) U ({e_i} U powerset(S - {e_i}))

其中e_i是S的元素（一个单独的元素）

伪算法

1. 传递的集合是否为空？完成（请注意，空集的幂集是{{}}）
2. 如果非空，则取出一个元素
   • 对剩余的集合进行递归调用该方法
   • 返回由以下两个部分组成的集合：
     1. 不包含该元素的集合的幂集（来自递归调用）
     2. 这个相同的集合（即2.1），但其中的每个元素都与最初取出的元素结合

- hobodave

---

我认为Paul的意思是： "Is the set passed empty? Done" 如何产生结果{ {} }？ - djna

谢谢。是的，幂集就是我要找的术语。我正在用C#编写它，并找到了一个看起来还不错的实现： https://dev59.com/6UXRa4cB1Zd3GeqPv-8H - ross

谢谢。这是一个非常可行的递归解决方案（我正在使用Lisp）。你的链接已经很好地解释了它。 - SMBiggs

这个函数在完成后会清除集合。它应该被命名为 powerset!，因为它是一种破坏性操作。 - Romário

很棒的解决方案！ - Keith Johnson

Answer 3

def power(a)
 (0..a.size).map {|x| a.combination(x).to_a}.flatten(1)
end

- AfDev

---

修正 - 定义 power(a) (0..a.size).map {|x| a.combination(x).to_a}.flatten(1) end - Eskim0

map + flatten(1) = flat_map - tokland

除了错别字之外，这是目前为止最好的答案。不幸的是，编辑队列已满。 - Romário

Answer 4

根据OP的评论（经过编辑）：

这个例子是我实际操作的简化形式。这些数字是具有“Qty”属性的对象，我想对每种可能的组合求和，然后选择使用最多对象的组合，其中数量总和N在其他边界内，例如x < N < y。

你面临的是一个优化问题。你假设正确的方法是将这个优化问题分解成一个枚举问题（这就是你所问的问题），然后再进行过滤（你可能已经知道如何做了）。

你还没有意识到的是，这种解决方案只适用于（a）理论分析或（b）非常小的n值。你所要求的枚举在n中呈指数增长，这意味着你最终会得到一些在实践中运行时间太长的东西。

因此，找出如何将你的优化问题表述为这样的问题，写一个新的问题，并编辑这个问题以指向它。

- eh9

Answer 5

与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中效果不是很好。

- Kache

Answer 6

使用Scheme语言计算幂集的递归和迭代解决方案。尚未完全测试。

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

- cobie

Answer 7

以下是一种递归解决方案，与已发布的解决方案类似。几个断言被提供作为单元测试。

我无法使用“set” Python类型来表示集合的集合。当尝试表达式“s.add(set())”时，Python会说“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)

- leframibra

Answer 8

我的同事用 Ruby 创建了一种优雅的方法来实现它。它使用了 IVlad 在索引集上的概念。

class Array
   def select_by_index(&block)
   # selects array element by index property
     n = []
     each_with_index do |e, i|
        if block.call(i) 
          n << e
        end  
     end
     n
   end
end

def pow(a)
# power set of a
  max = (1 << a.length)
  (0...max).map { |i| a.select_by_index { |k| (1 << k) & i != 0 }}
end

- Uwe Gotzes