algorithmpowerset

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

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]

Solution

  • 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 - {ei}) U ({ei} U powerset(S - {ei}))

    where ei 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