25

我想根据数字的起始列表有效地生成唯一的数字组合列表。

示例开始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]

4

8 回答 8

64

只需根据计数的二进制表示计数0并2^n - 1打印数字。a1表示您打印该号码，a0表示您不打印。例子：

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}
于 2010-05-06T08:06:27.827 回答
19

你所问的有一个名字。它被称为电源组。

谷歌搜索“幂集算法”让我找到了这个递归解决方案。

红宝石算法

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) 是所有子集的集合 powerset ( 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幂集(S - {c}) = { (c), (a,c), (b,c), (a,b,c)}

幂集(S) =幂集(S - {e i }) U ({e i } U幂集(S - {e i }))

其中 e i是 S 的一个元素（单例）

伪算法

  1. 传递的集合是空的吗？完成（请注意，{} 的幂集为 {{}}）
  2. 如果没有，取出一个元素
    • 在集合的其余部分上递归调用方法
    • 返回由 Union 组成的集合
      1. 没有元素的集合的幂集（来自递归调用）
      2. 相同的集合（即2.1），但其中的每个元素都与最初取出的元素联合
于 2010-05-06T07:13:10.583 回答
6 
def power(a)
 (0..a.size).map {|x| a.combination(x).to_a}.flatten(1)
end
于 2016-02-03T12:24:53.730 回答
1

来自 OP 的评论（复制编辑）：

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

你所拥有的是一个优化问题。您假设处理此优化问题的正确方法是将其分解为枚举问题（这是您所要求的），然后是过滤问题（大概您知道如何去做）。

您还没有意识到的是，这种解决方案仅适用于 (a) 理论分析，或 (b) 非常小的n. 您要求的枚举是指数 in n，这意味着您最终会得到一些在实践中需要很长时间才能运行的东西。

因此，弄清楚如何提出您的优化问题，编写一个新问题，然后编辑这个问题以指向它。

于 2012-11-07T13:10:40.010 回答
0

此后是一个递归解决方案，类似于已经发布的解决方案。一些断言作为单元测试提供。我没有设法使用“set”Python 类型来表示集合。当尝试像“s.add(set())”这样的表达式时，Python 说“集合对象是不可散列的”。

另请参阅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)
于 2014-01-26T17:44:41.193 回答
0

与 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 中效果不佳。

于 2012-11-07T11:57:03.923 回答
0

计算方案中功率集的递归和迭代解决方案。虽然没有完全测试

(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)))))
于 2013-07-26T16:01:05.017 回答
0

我的同事用 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
于 2020-11-24T19:47:47.923 回答