What algorithm can calculate the power set of a given set?

Question

I would like to efficiently generate a unique list of combinations of numbers based on a starting list of numbers.

example start list = [1,2,3,4,5] but the algorithm should work for [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]

Note. I don't want duplicate combinations, although I could live with them, eg in the above example I don't really need the combination [1,3,2] because it already present as [1,2,3]

Answer 1

There is a name for what you're asking. It's called the power set.

Googling for "power set algorithm" led me to this recursive solution.

Ruby Algorithm

def powerset!(set)
   return [set] if set.empty?

   p = set.pop
   subset = powerset!(set)  
   subset | subset.map { |x| x | [p] }
end

Power Set Intuition

If S = (a, b, c) then the powerset(S) is the set of all subsets powerset(S) = {(), (a), (b), (c), (a,b), (a,c), (b,c), (a,b,c)}

The first "trick" is to try to define recursively.

What would be a stop state?

S = () has what powerset(S)?

How get to it?

Reduce set by one element

Consider taking an element out - in the above example, take out {c}

S = (a,b) then powerset(S) = {(), (a), (b), (a,b)}

What is missing?

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

hmmm

Notice any similarities? Look again...

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

take any element out

powerset(S) = {(), (a), (b), (c), (a,b), (a,c), (b,c), (a,b,c)} is

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

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

where e_i is an element of S (a singleton)

Pseudo-algorithm

1. Is the set passed empty? Done (Note that power set of {} is {{}})
2. If not, take an element out
   • recursively call method on the remainder of the set
   • return the set composed of the Union of
     1. the powerset of the set without the element (from the recursive call)
     2. this same set (i.e., 2.1) but with each element therein unioned with the element initially taken out

Answer 2

Just count 0 to 2^n - 1 and print the numbers according to the binary representation of your count. a 1 means you print that number and a 0 means you don't. Example:

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}

Answer 3

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

Answer 4

Same as hobodave's answer, but iterative and faster (in Ruby). It also works with both Array and 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

In my tests, IVlad's method doesn't work so well in Ruby.

Answer 5

From a comment by OP (copy edited):

The example is simplified form of what I am actually doing. The numbers are objects which have a property "Qty", I want to sum the quantities for every possible combination then chose the combination that uses the most objects where the sum of the quantities N is within some other boundaries, e.g. x < N < y.

What you have is an optimization problem. What you have assumed is that the right way to approach this optimization problem is to decompose it into an enumeration problem (which is what you asked) and then a filtration problem (which presumably you know how to do).

What you don't yet realize is that this kind of solution only works either (a) for theoretical analysis, or (b) for very small values of n. The enumeration you're asking for is exponential in n, which means you'd end up with something that would take far too long to run in practice.

Therefore, figure out how to pose your optimization problem as such, write a new question, and edit this one to point to it.

Answer 6

Recursive and iterative solutions to calculate power set in scheme. Not fully tested though

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

Answer 7

Hereafter is a recursive solution, which is similar to already posted ones. A few assertions are providing as kind of unit tests. I didn't managed to use "set" Python type for representing set of sets. Python said that "set objects are unhashable" when trying expression like "s.add(set())".

See also solutions in many programming languages at 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)