Getting all possible combinations from a list of numbers

Question

I'm looking for an efficient way to achieve this:

• you have a list of numbers 1.....n (typically: 1..5 or 1..7 or so - reasonably small, but can vary from case to case)

• you need all combinations of all lengths for those numbers, e.g. all combinations of just one number ({1}, {2}, .... {n}), then all combinations of two distinct numbers ({1,2}, {1,3}, {1,4} ..... {n-1, n} ), then all combinations fo three of those numbers ({1,2,3}, {1,2,4}) and so forth

Basically, within the group, the order is irrelevant, so {1,2,3} is equivalent to {1,3,2} - it's just a matter of getting all groups of x numbers from that list

Seems like there ought to be a simple algorithm for this - but I have searched in vain so far. Most combinatorics and permutation algorithms seems to a) take order into account (e.g. 123 is not equal to 132), and they always seems to operate on a single string of characters or numbers....

Anyone have a great, nice'n'quick algorithm up their sleeve??

Thanks!

Answer 1

Not my code, but you're looking for the powerset. Google gave me this solution, which seems t work:

public IEnumerable<IEnumerable<T>> GetPowerSet<T>(List<T> list)
{
    return from m in Enumerable.Range(0, 1 << list.Count)
              select
                  from i in Enumerable.Range(0, list.Count)
                  where (m & (1 << i)) != 0
                  select list[i];
}

Source: http://rosettacode.org/wiki/Power_set#C.23