CODEWITHSUNDEEP
c#algorithmcombinatorics
marc_s
marc_s

Reputation: 754230

Getting all possible combinations from a list of numbers

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

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!

Upvotes: 21

Views: 27786

Answers (3)

jdmichal
jdmichal

Reputation: 11142

Just increment a binary number and take the elements corresponding to bits that are set.

For instance, 00101101 would mean take the elements at indexes 0, 2, 3, and 5. Since your list is simply 1..n, the element is simply the index + 1.

This will generate in-order permutations. In other words, only {1, 2, 3} will be generated. Not {1, 3, 2} or {2, 1, 3} or {2, 3, 1}, etc.

Upvotes: 39

Henri
Henri

Reputation: 5103

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

Upvotes: 43

Anthony Pegram
Anthony Pegram

Reputation: 126794

This is something I have written in the past to accomplish such a task.

List<T[]> CreateSubsets<T>(T[] originalArray) 
{ 
    List<T[]> subsets = new List<T[]>(); 

    for (int i = 0; i < originalArray.Length; i++) 
    { 
        int subsetCount = subsets.Count; 
        subsets.Add(new T[] { originalArray[i] }); 

        for (int j = 0; j < subsetCount; j++) 
        { 
            T[] newSubset = new T[subsets[j].Length + 1]; 
            subsets[j].CopyTo(newSubset, 0); 
            newSubset[newSubset.Length - 1] = originalArray[i]; 
            subsets.Add(newSubset); 
        } 
    } 

    return subsets; 
}

It's generic, so it will work for ints, longs, strings, Foos, etc.

Upvotes: 13

Related Questions