C# All Unique Combinations of List

Question

This question has been asked many times, but every SO post I've seen wants a specific length in values, whereas I just want to know every unique combination regardless of length.

The code below only provides a list where there are exactly 3 entries of combinations (and they are not unique).

List<string> list = new List<string> { "003_PS", "003_DH", "003_HEAT" };
var perms = list.GetPermutations();

public static class Extensions 
{
    public static IEnumerable<IEnumerable<T>> GetPermutations<T>(this IEnumerable<T> items)
    {
        foreach (var item in items)
        {
            var itemAsEnumerable = Enumerable.Repeat(item, 1);
            var subSet = items.Except(itemAsEnumerable);
            if (!subSet.Any())
            {
                yield return itemAsEnumerable;
            }
            else
            {
                foreach (var sub in items.Except(itemAsEnumerable).GetPermutations())
                {
                    yield return itemAsEnumerable.Union(sub);
                }
            }
        }
    }
}

/*
  OUTPUT:
      003_PS,   003_DH,   003_HEAT
      003_PS,   003_HEAT, 003_DH
      003_DH,   003_PS,   003_HEAT
      003_DH,   003_HEAT, 003_PS
      003_HEAT, 003_PS,   003_DH
      003_HEAT, 003_DH,   003_PS
*/

What I'm looking for is this:

/*
OUTPUT:
    003_PS, 003_DH, 003_HEAT
    003_PS, 003_DH
    003_PS, 003_HEAT
    003_PS

    003_DH, 003_HEAT
    003_DH

    003_HEAT
 */

The size is not limited to 3 items and each entry is unique.

What do I need to change in this function? I'm open to a LINQ solution

Any help is appreciated. Thanks!

EDIT: list above was not accurate to output

**EDIT #2: Here's a Javascript version of what I'm looking for. But I don't know what the C# equivalent syntax is:

function getUniqueList(arr){
    if (arr.length === 1) return [arr];
    else {
        subarr = getUniqueList(arr.slice(1));
        return subarr.concat(subarr.map(e => e.concat(arr[0])), [[arr[0]]]);
    }
}

.

Answer 1

OK, you have n items, and you want the 2ⁿ combinations of those items.

FYI, this is called the "power set" when you do it on sets; since sequences can contain duplicates and sets cannot, what you want is not exactly the power set, but it's close enough. The code I am presenting will be in a sense wrong if your sequence contains duplicates, since we'll say that the result for {10, 10} will be {}, {10}, {10}, {10, 10} but if you don't like that, well, remove duplicates before you start, and then you'll be computing the power set.

Computing the sequence of all combinations is straightforward. We reason as follows:

• If there are zero items then there is only one combination: the combination that has zero items.
• If there are n > 0 items then the combinations are all the combinations with the first element, and all the combinations without the first element.

Let's write the code:

using System;
using System.Collections.Generic;
using System.Linq;

static class Extensions
{
    public static IEnumerable<T> Prepend<T>(
        this IEnumerable<T> items,
        T first)
    {
        yield return first;
        foreach(T item in items)
            yield return item;
    }
    public static IEnumerable<IEnumerable<T>> Combinations<T>(
        this IEnumerable<T> items)
    {
        if (!items.Any())
            yield return items;
        else
        {
          var head = items.First();
          var tail = items.Skip(1);
          foreach(var sequence in tail.Combinations()) 
          {
            yield return sequence; // Without first
            yield return sequence.Prepend(head);
          }
       }
    }
}

public class Program
{
    public static void Main()
    {
        var items = new [] { 10, 20, 30 };
        foreach(var sequence in items.Combinations())
            Console.WriteLine($"({string.Join(",", sequence)})");
    }
}

And we get the output

()
(10)
(20)
(10,20)
(30)
(10,30)
(20,30)
(10,20,30)

Note that this code is not efficient if the original sequence is very long.

EXERCISE 1: Do you see why?

EXERCISE 2: Can you make this code efficient in both time and space for long sequences? (Hint: if you can make the head, tail and prepend operations more memory-efficient, that will go a long way.)

EXERCISE 3: You give the same algorithm in JavaScript; can you make the analogies between each part of the JS algorithm and the C# version?

Of course, we assume that the number of items in the original sequence is short. If it's even a hundred, you're going to be waiting a long time to enumerate all those trillions of combinations.

If you want to get all the combinations with a specific number of elements, see my series of articles on algorithms for that: https://ericlippert.com/2014/10/13/producing-combinations-part-one/