All Possible Combinations of a list of Values

Question

I have a list of integers List<int> in my C# program. However, I know the number of items I have in my list only at runtime.

Let us say, for the sake of simplicity, my list is {1, 2, 3} Now I need to generate all possible combinations as follows.

{1, 2, 3}
{1, 2}
{1, 3}
{2, 3}
{1}
{2}
{3}

Can somebody please help with this?

Tichonn

possible duplicate of Listing all permutations of a string/integer – Serviette

You forgot one of the combinations -- the empty combination. Note that what you are looking for is often called the "power set" of a set. -- that is, it is the set of all the subsets. That might help you as you look for solutions. – Ibbetson

You want all possible subsets not all the combinations combinations. en.wikipedia.org/wiki/Combinations – Accoutre

@naveen this is definitely not a duplicate. Permutation and Combination are two different things. – Parotid

LINQ answer here: https://mcmap.net/q/276921/-getting-all-possible-combinations-from-a-list-of-numbers – Whiteley

Note: This is called the power set of {1,2,3}, also notated 2^{1,2,3}. – Tog

Answer 1

try this:

static void Main(string[] args)
{

    GetCombination(new List<int> { 1, 2, 3 });
}

static void GetCombination(List<int> list)
{
    double count = Math.Pow(2, list.Count);
    for (int i = 1; i <= count - 1; i++)
    {
        string str = Convert.ToString(i, 2).PadLeft(list.Count, '0');
        for (int j = 0; j < str.Length; j++)
        {
            if (str[j] == '1')
            {
                Console.Write(list[j]);
            }
        }
        Console.WriteLine();
    }
}

Jillian

+1 You need to have tried to solve this yourself before you can truly appreciate the genius of this solution. @ojlovecd, Great Job! – Overture

this will be exponentially slow! as N (the number of integers) becomes larger. The OP is looking for the power set of an IEnumerable which has 1 << N number of subsets excluding the empty set. – Afebrile

Why do you convert a number to a binary string? That seems exceeding non-optimal. The number is already stored as binary, you could simply use a bit mask. – Syncarpous

This is an astoundingly simple solution to an age-old combination/permutation problem. The fact that 1) I found this using terms most mid-level programmers would use to describe it, and 2) it solves the broader problem (unique permutation generation) AND the specific problem asked in the question make this a fantastic answer! Nicely done. – Favourable

If you worked with logic gates, you will understand how elegant this solution is. – Samba

This is the right algorithm, but horrible execution. Using Pow and converting an int to string to check a bit are just wrong and should only be done by beginners. I don't know if I should edit this answer, because it would change it substantially. – Islamite

Using an int instead of long limits to 31 initial objects in list at best and will just fail after that. – Gemsbok

Answer 2

Assuming that all items within the initial collection are distinct, we can try using Linq in order to query; let's generalize the solution:

Code:

public static IEnumerable<T[]> Combinations<T>(IEnumerable<T> source) {
  if (null == source)
    throw new ArgumentNullException(nameof(source));

  T[] data = source.ToArray();

  return Enumerable
    .Range(0, 1 << (data.Length))
    .Select(index => data
       .Where((v, i) => (index & (1 << i)) != 0)
       .ToArray());
}

Demo:

  var data = new char[] { 'A', 'B', 'C' };

  var result = Combinations(data);

  foreach (var item in result)
    Console.WriteLine($"[{string.Join(", ", item)}]");

Outcome:

[]
[A]
[B]
[A, B]
[C]
[A, C]
[B, C]
[A, B, C]

If you want to exclude the initial empty array, put .Range(1, (1 << (data.Length)) - 1) instead of .Range(0, 1 << (data.Length))

Algorithm explanation:

Having a collection of collection.Length distinct items we get 2 ** collection.Length combinations (we can compute it as 1 << collection.Length):

    mask - comments
------------------------------------
00..0000 - empty, no items are taken
00..0001 - 1st item taken
00..0010 - 2nd item taken
00..0011 - 1st and 2nd items are taken
00..0100 - 3d item taken
...
11..1111 - all items are taken

To generate all masks we can use direct Enumerable.Range(0, 1 << (data.Length)) Linq query. Now having index mask we should take item from the collection if and only if corresponding bit within index is set to 1:

011001001
 ^^  ^  ^
 take 7, 6, 3, 0-th items from the collection   

The code can be

.Select(index => data.Where((v, i) => (index & (1 << i)) != 0) 

here for each item (v) in the collection data we check if i-th bit is set in the index (mask).

Unwary

This is probably what OP wanted, but these values are no permutations! – Herve

This is without doubt the most simple and elegant solution to the problem asked by Sach. You gotta love Linq! – Rai

While this is combinations, not permutations, it is exactly what I was looking for. Such an elegant, simple, and powerful approach! I regret that I have but 1 upvote to give. – Seeley

This appears to be a work of genius. Can you explain HOW it works??? – Devol

@Bit Racketeer: I've edited the answer (algorithm explanation). All we need to do here is to use bit masks – Unwary

@DmitryBychenko genius! – Devol

Nice but there are a few things that can be improved. Better use ICollection<T> data and skip the unnecessary array. Also, return an IEnumerable<IEnumerable<T>> and avoid the final ToArray(). Combinations get real big real fast – Odisodium

Answer 3

Here are two generic solutions for strongly typed lists that will return all unique combinations of list members (if you can solve this with simpler code, I salute you):

// Recursive
public static List<List<T>> GetAllCombos<T>(List<T> list)
{
  List<List<T>> result = new List<List<T>>();
  // head
  result.Add(new List<T>());
  result.Last().Add(list[0]);
  if (list.Count == 1)
    return result;
  // tail
  List<List<T>> tailCombos = GetAllCombos(list.Skip(1).ToList());
  tailCombos.ForEach(combo =>
  {
    result.Add(new List<T>(combo));
    combo.Add(list[0]);
    result.Add(new List<T>(combo));
  });
  return result;
}

// Iterative, using 'i' as bitmask to choose each combo members
public static List<List<T>> GetAllCombos<T>(List<T> list)
{
  int comboCount = (int) Math.Pow(2, list.Count) - 1;
  List<List<T>> result = new List<List<T>>();
  for (int i = 1; i < comboCount + 1; i++)
  {
    // make each combo here
    result.Add(new List<T>());
    for (int j = 0; j < list.Count; j++)
    {
      if ((i >> j) % 2 != 0)
        result.Last().Add(list[j]);
    }
  }
  return result;
}

// Example usage
List<List<int>> combos = GetAllCombos(new int[] { 1, 2, 3 }.ToList());

Rout

"if you can solve this with simpler code, I salute you". OK, I changed "i < comboCount + 1" into "i <= comboCount" in my answer below. Does that count? :-) – Elisabeth

Please replace Pow with a bit shift, then this answer is way better than the accepted answer. – Islamite

I like the recursive approach more. The method parameter List<T> list can be replaced with a Queue<T>. Just dequeue the first item in the beginning, replace all list[0]s with that, and pass the same queue in the recursive call. – Puberulent

Agreed appreciating recursive functions. With a bit of help from a Yield helper function, suggest the following improvements to the recursive approach: private static IEnumerable<IEnumerable<T>> GetAllCombos<T>(this IEnumerable<T> list) { if (list.Count() == 1) { yield return list; } else { var first = list.First(); yield return first.Yield(); foreach (var combo in GetAllCombos(list.Skip(1))) { yield return combo; yield return combo.Prepend(first); } } } – Dinitrobenzene

Answer 4

This answer uses the same algorithm as ojlovecd and (for his iterative solution) jaolho. The only thing I'm adding is an option to filter the results for a minimum number of items in the combinations. This can be useful, for example, if you are only interested in the combinations that contain at least two items.

Edit: As requested by @user3610374 a filter for the maximum number of items has been added.

Edit 2: As suggested by @stannius the algorithm has been changed to make it more efficient for cases where not all combinations are wanted.

  /// <summary>
  /// Method to create lists containing possible combinations of an input list of items. This is 
  /// basically copied from code by user "jaolho" on this thread:
  /// https://mcmap.net/q/276286/-all-possible-combinations-of-a-list-of-values
  /// </summary>
  /// <typeparam name="T">type of the items on the input list</typeparam>
  /// <param name="inputList">list of items</param>
  /// <param name="minimumItems">minimum number of items wanted in the generated combinations, 
  ///                            if zero the empty combination is included,
  ///                            default is one</param>
  /// <param name="maximumItems">maximum number of items wanted in the generated combinations,
  ///                            default is no maximum limit</param>
  /// <returns>list of lists for possible combinations of the input items</returns>
  public static List<List<T>> ItemCombinations<T>(List<T> inputList, int minimumItems = 1, 
                                                  int maximumItems = int.MaxValue)
  {
     int nonEmptyCombinations = (int)Math.Pow(2, inputList.Count) - 1;
     List<List<T>> listOfLists = new List<List<T>>(nonEmptyCombinations + 1);

     // Optimize generation of empty combination, if empty combination is wanted
     if (minimumItems == 0)
        listOfLists.Add(new List<T>());

     if (minimumItems <= 1 && maximumItems >= inputList.Count)
     {
        // Simple case, generate all possible non-empty combinations
        for (int bitPattern = 1; bitPattern <= nonEmptyCombinations; bitPattern++)
           listOfLists.Add(GenerateCombination(inputList, bitPattern));
     }
     else
     {
        // Not-so-simple case, avoid generating the unwanted combinations
        for (int bitPattern = 1; bitPattern <= nonEmptyCombinations; bitPattern++)
        {
           int bitCount = CountBits(bitPattern);
           if (bitCount >= minimumItems && bitCount <= maximumItems)
              listOfLists.Add(GenerateCombination(inputList, bitPattern));
        }
     }

     return listOfLists;
  }

  /// <summary>
  /// Sub-method of ItemCombinations() method to generate a combination based on a bit pattern.
  /// </summary>
  private static List<T> GenerateCombination<T>(List<T> inputList, int bitPattern)
  {
     List<T> thisCombination = new List<T>(inputList.Count);
     for (int j = 0; j < inputList.Count; j++)
     {
        if ((bitPattern >> j & 1) == 1)
           thisCombination.Add(inputList[j]);
     }
     return thisCombination;
  }

  /// <summary>
  /// Sub-method of ItemCombinations() method to count the bits in a bit pattern. Based on this:
  /// https://graphics.stanford.edu/~seander/bithacks.html#CountBitsSetKernighan
  /// </summary>
  private static int CountBits(int bitPattern)
  {
     int numberBits = 0;
     while (bitPattern != 0)
     {
        numberBits++;
        bitPattern &= bitPattern - 1;
     }
     return numberBits;
  }

Elisabeth

This is perfect but I would recommend to include maxItems as well – Centaury

Wouldn't you want the default for Max value to be the input list count? – Centaury

@user3610374 Hmmm, I suppose so, but using int.MaxValue provides the same result, and can be coded as a default parameter value. – Elisabeth

This is unnecessarily slow if you want anything other than the complete set of all subsets. It generates all the combinations and then throws out the ones that aren't between min and max. You could instead count the set bits of i, and only go through with generating the combination if the bit count is within the range. There are bit counting algorithms available: #109523 – Sorilda

@Sorilda Thanks for the suggestion, I've edited my answer. – Elisabeth

@Elisabeth cool. I'd upvote your updated answer, but I already did yesterday when I used your code to solve my problem. – Sorilda

This won't work if inputList.Count > 30, because nonEmptyCombinations will be > int.MaxValue – Birkle

Answer 5

Here's a generic solution using recursion

public static ICollection<ICollection<T>> Permutations<T>(ICollection<T> list) {
    var result = new List<ICollection<T>>();
    if (list.Count == 1) { // If only one possible permutation
        result.Add(list); // Add it and return it
        return result;
    }
    foreach (var element in list) { // For each element in that list
        var remainingList = new List<T>(list);
        remainingList.Remove(element); // Get a list containing everything except of chosen element
        foreach (var permutation in Permutations<T>(remainingList)) { // Get all possible sub-permutations
            permutation.Add(element); // Add that element
            result.Add(permutation);
        }
    }
    return result;
}

I know this is an old post, but someone might find this helpful.

Koser

This does not do what OP asks. It only returns 6 items each having length of 3. dotnetfiddle.net/A2lNPb – Kicker

I love this. Extremely elegant solution. – Rabbitry

This is a solution for permutations while the OP is asking for combinations – Draftee

Answer 6

Another solution using Linq and recursion...

static void Main(string[] args)
    {
        List<List<long>> result = new List<List<long>>();

        List<long> set = new List<long>() { 1, 2, 3, 4 };

        GetCombination<long>(set, result);

        result.Add(set);

        IOrderedEnumerable<List<long>> sorted = result.OrderByDescending(s => s.Count);

        sorted.ToList().ForEach(l => { l.ForEach(l1 => Console.Write(l1 + " ")); Console.WriteLine(); });
    }

    private static void GetCombination<T>(List<T> set, List<List<T>> result)
    {
        for (int i = 0; i < set.Count; i++)
        {
            List<T> temp = new List<T>(set.Where((s, index) => index != i));

            if (temp.Count > 0 && !result.Where(l => l.Count == temp.Count).Any(l => l.SequenceEqual(temp)))
            {
                result.Add(temp);

                GetCombination<T>(temp, result);
            }
        }
    }

Archuleta

Answer 7

This is an improvement of @ojlovecd answer without using strings.

    static void Main(string[] args)
    {
        GetCombination(new List<int> { 1, 2, 3 });
    }


    private static void GetCombination(List<int> list)
    {
        double count = Math.Pow(2, list.Count);
        for (int i = 1; i <= count - 1; i++)
        {
            for (int j = 0; j < list.Count; j++)
            {
                int b = i & (1 << j);
                if (b > 0)
                {
                    Console.Write(list[j]);
                }
            }
            Console.WriteLine();
        }
    }

Giesser

I would suggest 1. Use unsigned long for up to 63 item lists 2. Use 1 << list.Count instead of Math.Pow to stay in the integer domain. 3. Change the inner for to be for (unsigned long j = 1; j <= count; j <<= 1) and int b = i & j; and test if (b != 0) 4. Change the outer for to be for (int i = 1; i < count; ++i) – Gemsbok

Answer 8

Firstly, given a set of n elements, you compute all combinations of k elements out of it (nCk). You have to change the value of k from 1 to n to meet your requirement.

See this codeproject article for C# code for generating combinations.

In case, you are interested in developing the combination algorithm by yourself, check this SO question where there are a lot of links to the relevant material.

Abc

Answer 9

protected List<List<T>> AllCombos<T>(Func<List<T>, List<T>, bool> comparer, params T[] items)
    {
        List<List<T>> results = new List<List<T>>();
        List<T> workingWith = items.ToList();
        results.Add(workingWith);
        items.ToList().ForEach((x) =>
        {
            results.Add(new List<T>() { x });
        });
        for (int i = 0; i < workingWith.Count(); i++)
        {
            T removed = workingWith[i];
            workingWith.RemoveAt(i);
            List<List<T>> nextResults = AllCombos2(comparer, workingWith.ToArray());
            results.AddRange(nextResults);
            workingWith.Insert(i, removed);
        }
        results = results.Where(x => x.Count > 0).ToList();
        for (int i = 0; i < results.Count; i++)
        {
            List<T> list = results[i];
            if (results.Where(x => comparer(x, list)).Count() > 1)
            {
                results.RemoveAt(i);
            }
        }

        return results;
    }

    protected List<List<T>> AllCombos2<T>(Func<List<T>, List<T>, bool> comparer, params T[] items)
    {
        List<List<T>> results = new List<List<T>>();
        List<T> workingWith = items.ToList();
        if (workingWith.Count > 1)
        {
            results.Add(workingWith);
        }
        for (int i = 0; i < workingWith.Count(); i++)
        {
            T removed = workingWith[i];
            workingWith.RemoveAt(i);
            List<List<T>> nextResults = AllCombos2(comparer, workingWith.ToArray());
            results.AddRange(nextResults);
            workingWith.Insert(i, removed);
        }
        results = results.Where(x => x.Count > 0).ToList();
        for (int i = 0; i < results.Count; i++)
        {
            List<T> list = results[i];
            if (results.Where(x => comparer(x, list)).Count() > 1)
            {
                results.RemoveAt(i);
            }
        }

        return results;
    }

This worked for me, it's slightly more complex and actually takes a comparer callback function, and it's actually 2 functions, the difference being that the AllCombos adds the single item lists explicitly. It is very raw and can definitely be trimmed down but it gets the job done. Any refactoring suggestions are welcome. Thanks,

Lindsylindy

Answer 10

public class CombinationGenerator{
    private readonly Dictionary<int, int> currentIndexesWithLevels = new Dictionary<int, int>();
    private readonly LinkedList<List<int>> _combinationsList = new LinkedList<List<int>>();
    private readonly int _combinationLength;

    public CombinationGenerator(int combinationLength)
    {
        _combinationLength = combinationLength;
    }

    private void InitializeLevelIndexes(List<int> list)
    {
        for (int i = 0; i < _combinationLength; i++)
        {
            currentIndexesWithLevels.Add(i+1, i);
        }
    }

    private void UpdateCurrentIndexesForLevels(int level)
    {
        int index;
        if (level == 1)
        {
            index = currentIndexesWithLevels[level];
            for (int i = level; i < _combinationLength + 1; i++)
            {
                index = index + 1;
                currentIndexesWithLevels[i] = index;
            }
        }
        else
        {
            int previousLevelIndex;
            for (int i = level; i < _combinationLength + 1; i++)
            {
                if (i > level)
                {
                    previousLevelIndex = currentIndexesWithLevels[i - 1];
                    currentIndexesWithLevels[i] = previousLevelIndex + 1;
                }
                else
                {
                    index = currentIndexesWithLevels[level];
                    currentIndexesWithLevels[i] = index + 1;
                }
            }
        }
    }

    public void FindCombinations(List<int> list, int level, Stack<int> stack)
    {
        int currentIndex;
        InitializeLevelIndexes(list);
        while (true)
        {
            currentIndex = currentIndexesWithLevels[level];
            bool levelUp = false;          
            for (int i = currentIndex; i < list.Count; i++)
            {
                if (level < _combinationLength)
                {
                    currentIndex = currentIndexesWithLevels[level];
                    MoveToUpperLevel(ref level, stack, list, currentIndex);
                    levelUp = true;
                    break;
                }
                levelUp = false;
                stack.Push(list[i]);
                if (stack.Count == _combinationLength)
                {
                    AddCombination(stack);
                    stack.Pop();
                }                                                                                 
            }

            if (!levelUp)
            {
                MoveToLowerLevel(ref level, stack, list, ref currentIndex);
                while (currentIndex >= list.Count - 1)
                {
                    if (level == 1)
                    {
                        AdjustStackCountToCurrentLevel(stack, level);
                        currentIndex = currentIndexesWithLevels[level];
                        if (currentIndex >= list.Count - 1)
                        {
                            return;
                        }
                        UpdateCurrentIndexesForLevels(level);
                    }
                    else
                    {
                        MoveToLowerLevel(ref level, stack, list, ref currentIndex);
                    }
              }
          }                               
       }
    }

    private void AddCombination(Stack<int> stack)
    {
        List<int> listNew = new List<int>();
        listNew.AddRange(stack);
        _combinationsList.AddLast(listNew);
    }

    private void MoveToUpperLevel(ref int level, Stack<int> stack, List<int> list, int index)
    {
        stack.Push(list[index]);
        level++;
    }

    private void MoveToLowerLevel(ref int level, Stack<int> stack, List<int> list, ref int currentIndex)
    {
        if (level != 1)
        {
            level--;
        }
        AdjustStackCountToCurrentLevel(stack, level);
        UpdateCurrentIndexesForLevels(level);
        currentIndex = currentIndexesWithLevels[level];
    }

    private void AdjustStackCountToCurrentLevel(Stack<int> stack, int currentLevel)
    {
        while (stack.Count >= currentLevel)
        {
            if (stack.Count != 0)
                stack.Pop();
        }
    }

    public void PrintPermutations()
    {
        int count = _combinationsList.Where(perm => perm.Count() == _combinationLength).Count();
        Console.WriteLine("The number of combinations is " + count);
    }

}

Loquacious

Iterative solution to find combinations – Loquacious

Answer 11

We can use recursion for combination/permutation problems involving string or integers.

public static void Main(string[] args)
{
    IntegerList = new List<int> { 1, 2, 3, 4 };

    PrintAllCombination(default(int), default(int));
}

public static List<int> IntegerList { get; set; }

public static int Length { get { return IntegerList.Count; } }

public static void PrintAllCombination(int position, int prefix)
{
    for (int i = position; i < Length; i++)
    {
        Console.WriteLine(prefix * 10 + IntegerList[i]);
        PrintAllCombination(i + 1, prefix * 10 + IntegerList[i]);
    }

}

Incommodious

Answer 12

What about

static void Main(string[] args)
{
     Combos(new [] { 1, 2, 3 });
}

static void Combos(int[] arr)
{
    for (var i = 0; i <= Math.Pow(2, arr.Length); i++)
    {
        Console.WriteLine();
        var j = i;
        var idx = 0;
        do 
        {
            if ((j & 1) == 1) Console.Write($"{arr[idx]} ");
        } while ((j >>= 1) > 0 && ++idx < arr.Length);
    }
}

Mapping

Answer 13

A slightly more generalised version for Linq using C# 7. Here filtering by items that have two elements.

static void Main(string[] args)
{
    foreach (var vals in Combos(new[] { "0", "1", "2", "3" }).Where(v => v.Skip(1).Any() && !v.Skip(2).Any()))
        Console.WriteLine(string.Join(", ", vals));
}

static IEnumerable<IEnumerable<T>> Combos<T>(T[] arr)
{
    IEnumerable<T> DoQuery(long j, long idx)
    {
        do
        {
            if ((j & 1) == 1) yield return arr[idx];
        } while ((j >>= 1) > 0 && ++idx < arr.Length);
    }
    for (var i = 0; i < Math.Pow(2, arr.Length); i++)
        yield return DoQuery(i, 0);
}

Mapping

Answer 14

Here is how I did it.

public static List<List<int>> GetCombination(List<int> lst, int index, int count)
{
    List<List<int>> combinations = new List<List<int>>();
    List<int> comb;
    if (count == 0 || index == lst.Count)
    {
        return null;
    }
    for (int i = index; i < lst.Count; i++)
    {
        comb = new List<int>();
        comb.Add(lst.ElementAt(i));
        combinations.Add(comb);
        var rest = GetCombination(lst,i + 1, count - 1);
        if (rest != null)
        {
            foreach (var item in rest)
            {
                combinations.Add(comb.Union(item).ToList());
            }
        }
    }
    return combinations;
}

You call it as :

List<int> lst= new List<int>(new int[]{ 1, 2, 3, 4 });
var combinations = GetCombination(lst, 0, lst.Length)

Exemplar

Answer 15

I just run into a situation where I needed to do this, this is what I came up with:

private static List<string> GetCombinations(List<string> elements)
{
    List<string> combinations = new List<string>();
    combinations.AddRange(elements);
    for (int i = 0; i < elements.Count - 1; i++)
    {
        combinations = (from combination in combinations
                        join element in elements on 1 equals 1
                        let value = string.Join(string.Empty, $"{combination}{element}".OrderBy(c => c).Distinct())
                        select value).Distinct().ToList();
    }

    return combinations;
}

It may be not too efficient, and it sure has room for improvement, but gets the job done!

List<string> elements = new List<string> { "1", "2", "3" };
List<string> combinations = GetCombinations(elements);

foreach (string combination in combinations)
{
    System.Console.Write(combination);
}

Bailiwick

Answer 16

This is an improved version based on the answer from ojlovecd using extension methods:

public static class ListExtensions
{
    public static IEnumerable<List<T>> GetCombinations<T>(
        this List<T> valuesToCombine)
    {
        var count = Math.Pow(2, valuesToCombine.Count);
        for(var i = 1; i <= count; i++)
        {
            var itemFlagList = i.ToBinaryString(valuesToCombine.Count())
                .Select(x => x == '1').ToList();

            yield return GetCombinationByFlagList(valuesToCombine, itemFlagList)
                .ToList();
        }
    }
    private static IEnumerable<T> GetCombinationByFlagList<T>(
        List<T> valuesToCombine, List<bool> flagList)
    {
        for (var i = 0; i < valuesToCombine.Count; i++)
        {
            if (!flagList[i]) continue;

            yield return valuesToCombine.ElementAt(i);
        }
    }
}

public static class IntegerExtensions
{
    public static string ToBinaryString(this int value, int length)
    {
        return Convert.ToString(value, 2).ToString().PadLeft(length, '0');
    }
}

Usage:

var numbersList = new List<int>() { 1, 2, 3 };
var combinations = numbersList.GetCombinations();
foreach (var combination in combinations)
{
    System.Console.WriteLine(string.Join(",", combination));
}

Output:

3
2
2,3
1
1,3
1,2
1,2,3

The idea is to basically use some flags to keep track of which items were already added to the combination. So in case of 1, 2 & 3, the following binary strings are generated in order to indicate whether an item should be included or excluded: 001, 010, 011, 100, 101, 110 & 111

Clarisaclarise

Answer 17

I'd like to suggest an approach that I find to be quite intuitive and easy to read. (Note: It is slower than the currently accepted solution.)

It is built on the idea that for each integer in the list, we need to extend the so-far-aggregated resulting combination list with

• all currently existing combinations, each extended with the given integer
• a single "combination" of that integer alone

Here, I am using .Aggregate() with a seed that is an IEnumerable<IEnumerable<int>> containing a single, empty collection entry. That empty entry lets us easily do the two steps above simultaneously. The empty collection entry can be skipped after the resulting combination collection has been aggregated.

It goes like this:

var emptyCollection = Enumerable.Empty<IEnumerable<int>>();
var emptyCombination = Enumerable.Empty<int>();

IEnumerable<int[]> combinations = list
    .Aggregate(emptyCollection.Append(emptyCombination),
        ( acc, next ) => acc.Concat(acc.Select(entry => entry.Append(next))))
    .Skip(1) // skip the initial, empty combination
    .Select(comb => comb.ToArray());

For each entry in the input integer list { 1, 2, 3 }, the accumulation progresses as follows:

next = 1

{ { } }.Concat({ { }.Append(1) })

{ { } }.Concat({ { 1 } })

{ { }, { 1 } } // acc

next = 2

{ { }, { 1 } }.Concat({ { }.Append(2), { 1 }.Append(2) })

{ { }, { 1 } }.Concat({ { 2 }, { 1, 2 } })

{ { }, { 1 }, { 2 }, { 1, 2 } } // acc

next = 3

{ { }, { 1 }, { 2 }, { 1, 2 } }.Concat({ { }.Append(3), { 1 }.Append(3), { 2 }.Append(3), { 1, 2 }.Append(3) })

{ { }, { 1 }, { 2 }, { 1, 2 } }.Concat({ { 3 }, { 1, 3 }, { 2, 3 }, { 1, 2, 3 } })

{ { }, { 1 }, { 2 }, { 1, 2 }, { 3 }, { 1, 3 }, { 2, 3 }, { 1, 2, 3 } } // acc

Skipping the first (empty) entry, we are left with the following collection:

1
2
1 2
3
1 3
2 3
1 2 3

, which can easily be ordered by collection length and collection entry sum for a clearer overview.

Example fiddle here.

Biondo

Answer 18

Some of the solutions here are truly ingenious; especially the ones that use bitmaps.

But I found that in practice these algos

1. aren't easy to modify if a specific range of lengths needed (e.g. all variations of 3 to 5 choices from an input set of 8 elements)
2. can't handle LARGE input lists (and return empty or singleton results instead of throwing exception); and
3. can be tricky to debug.

So I decided to write something not as clever as the other people here.

My more basic approach recognises that the set of Variations(1 to maxLength) is simply a UNION of all fixed-length Variations of each length 1 to maxLength:

i.e

Variations(1 to maxLength) = Variations(1) + Variations(2) + ... + Variations(maxLength)

So you can do a "choose K from N" for each required length (for each K in (1, 2, 3, ..., maxLength)) and then just do a Union of these separate results to yield a List of Lists.

This resulting code intends to be easy to understand and to maintain:

/// <summary>
/// Generates ALL variations of length between minLength and maxLength (inclusive)
/// Relies on Combinatorics library to generate each set of Variations
/// Nuget https://www.nuget.org/packages/Combinatorics/
/// Excellent more general references (without this solution):
/// https://www.codeproject.com/Articles/26050/Permutations-Combinations-and-Variations-using-C-G
/// Self-authored solution.
/// </summary>
/// <typeparam name="T">Any type without any constraints.</typeparam>
/// <param name="sourceList">The source list of elements to be combined.</param>
/// <param name="minLength">The minimum length of variation required.</param>
/// <param name="maxLength">The maximum length of variation required.</param>
/// <returns></returns>
public static List<List<T>> GenerateVariations<T>(this IEnumerable<T> sourceList, int minLength, int maxLength)
{
    List<List<T>> finalUnion = new();
    foreach (int length in Enumerable.Range(minLength, maxLength))
    {
        Variations<T> variations = new Variations<T>(sourceList, length, GenerateOption.WithoutRepetition);
        foreach (var variation in variations)
        {
            var list = variation.ToList<T>();
            finalUnion.Add(list);
        }
    }
    Debug.WriteLine(sourceList.Count() + " source " + typeof(T).Name + " yielded " + finalUnion.Count());
    return finalUnion;
}

Happy to receive comments (good and bad). Maybe there's a more succint way to achieve this in LINQ? Maybe the really smart people here can marry their approach with my more basic one?

Devol

Answer 19

this is a variant of the jaolho's solution, optimized with bitwise operations for better performance

public static List<List<T>> GetAllCombinations<T>(this List<T> list)
{
    int comboCount = (1 << list.Count) - 1;
    List<List<T>> result = new List<List<T>>(comboCount);
    for (int i = 1; i <= comboCount; i++)
    {
        // make each combo here
        List<T> combo = new List<T>();
        for (int j = 0; j < list.Count; j++)
        {
            if ((i & (1 << j)) != 0)
                combo.Add(list[j]);
        }
        result.Add(combo);
    }
    return result;
}

// Example usage
List<List<int>> combos = GetAllCombos(new int[] { 1, 2, 3 }.ToList());

Kipper

Answer 20

Please find very very simple solution without recursion and which dont eat RAM.

Unique Combinations

Loris

Please add some content around the link, rather than just copy/pasting it here. – Tucana