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!

You are basically looking for the [Power Set](http://en.wikipedia.org/wiki/Power_set) of your list (which is mathematically actually a set, if all of its items are unique). — Justin L., Jul 23 '10 at 19:02
See also here: https://stackoverflow.com/questions/7802822/all-possible-combinations-of-a-list-of-values/41642733#41642733 — RenniePet, Jun 20 '17 at 08:07

score 42 · Answer 1 · answered Jul 23 '10 at 15:30

42

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

answered Jul 23 '10 at 15:30

Henri

5,065
23
24

4

Just for clarification, this is my answer, implemented via LINQ. Which, I have to admit, is quite clever. – jdmichal Jul 23 '10 at 15:42
3

Power Of Linq, a moment respect for it. – Rev Jul 12 '14 at 19:01
1

Works, but only for lists with less than 32 elements due to Enumerable.Range's restriction of the 2nd parameter to type "int" – Kyle Ross Mar 11 '21 at 04:52

score 39 · Accepted Answer · edited Oct 18 '20 at 06:13

39

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.

edited Oct 18 '20 at 06:13

Aage

5,932
2
32
57

answered Jul 23 '10 at 15:21

jdmichal

10,984
4
43
42

@Henri's solution is pretty much an implementation of this idea, using LINQ. – Nate Kohl Jul 23 '10 at 15:41
@Nate Kohl Yea I just commented on that. Pretty clever! Gave it a +1. – jdmichal Jul 23 '10 at 15:43
+1 : a nice proof that the number of subsets of a given set of size N is 2^N – Eyal Schneider Jul 23 '10 at 15:55
This is a awesome answer! – Radmation Jul 13 '16 at 21:18

score 13 · Answer 3 · answered Jul 23 '10 at 15:26

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.

For a `List` for example you'd call it as `var newList = CreateSubsets(sourceList.ToArray())` — PeterJ, Jun 11 '19 at 01:51

Getting all possible combinations from a list of numbers

3 Answers3

Linked

Related