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?

Solution 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();
    }
}

Solution 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).

Solution 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());

Solution 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:
  /// http://stackoverflow.com/questions/7802822/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;
  }

Solution 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.

Solution 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);
            }
        }
    }

Solution 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();
        }
    }

Solution 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.

Solution 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,

Solution 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);
    }

}

Solution 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]);
    }

}

Solution 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);
    }
}

Solution 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);
}

Solution 14

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

Unique Combinations

Solution 15

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)

Solution 16

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);
}

Solution 17

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

Solution 18

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.

Solution 19

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?