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]

Kayo

docs.python.org/library/itertools.html#itertools.combinations – Carrollcarronade

This looks homework-y so I will offer questions rather than answers: Do you know how many members the powerset has? (note that your list is incomplete if it's intended to be the powerset) Does that number suggest a way to enumerate them? massive hint: binary – Gadgeteer

possible duplicate of #1671362 – Izzard

No not homework. The example is simplified from 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 is within some other boundaries, eg > x < y – Kayo

Compared with the power set, your example result is missing the empty set, the 5 subsets with 4 elements, the subset with all 5 elements, and the set [2,4,5]. – Pavilion

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

Izzard

I think Paul means: how does "Is the set passed empty? Done" produce the result { {} }? – Jook

Thanks. Yes, power set is the term i was after. I am doing it in C# and found an implementation that seems ok : #344154 – Kayo

Thanks. This is a very workable recursive solution (I'm working in Lisp). Your link explained it well enough. – Nystrom

This function erases the set after it's done. It should be named powerset!, since it's a destructive operation. – Hand

Great solution! – Brigettebrigg

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}

Dehisce

Felicitari for a nice and efficient answer! – Rickie

Answer 3

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

Clostridium

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

map + flatten(1) = flat_map – Moten

Aside from the typo, this is the best answer so far. It seems the edit queue is full, unfortunately. – Hand

Answer 4

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.

Amphiarthrosis

Answer 5

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.

Scabious

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

Abeyta

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)

Manipulate

Answer 8

My colleague created an elegant way to do it in ruby. It uses IVlad's concept on the index set.

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

Steamship