views:

505

answers:

3

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]

+1  A: 

Break the problem down.

How would get all the different one-item lists? Two-item lists?

Can you use your answer to the one-item case in answering the two-item case?

djna
+1  A: 

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

For the haters:

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

  p = set.pop
  subset = powerset(set)  
  subset | subset.map { |x| x | [p] }
end
hobodave
Step 1 is wrong. The powerset of {} is {{}}.
Paul Hankin
I think Paul means: how does "Is the set passed empty? Done" produce the result { {} }?
djna
I'm with @Paul on this. I think @hobodave is defending a sloppily stated pseudo-algorithm. It's sloppy in that it suggests that {()} is an empty set when in fact it's a set containing a list (or possibly another set, but the reference is sloppy in its use of {} and () too) with no elements. The power set of {()} is probably {{},{()}}.
High Performance Mark
Fine. Threw up a _working_ ruby algorithm.
hobodave
Thanks. Yes, power set is the term i was after.I am doing it in C# and found an implementation that seems ok :http://stackoverflow.com/questions/343654/c-data-structure-to-mimic-cs-listlistint
ross
+6  A: 

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}
IVlad
Clever solution.
hobodave