Generate Combinations of generic list

Question

I need to create a list from another list that contains every combination possible. In researching possible solutions I have found many interesting approaches but all seem to generate results based on the count of records provided. I need the combinations to increase to a max threshold.

i.e. consider the following array

1,2,3,4,5

I need the results to look similar to (threshold is 3 in this example)

1
1,2
1,2,3
1,2,4
1,2,5
1,3,4
2,3,5... etc

In actuality, the data will be IEnumerable. I used a simple int[] to illustrate the desired results.

Answer 1

My solution uses a simple recursive algorithm to create the combinations:

• When we walk through the sequence we can immediately return a sequence that only holds the current value. I have written a simple extension method to create an IEnumerable for a single item.

• Next we recursively generate all combinations for the remaining elements with the threshold reduced by 1 and combine each of them with the current value.

I assume that elements should not be repeated (i.e. { 1, 1 } or { 1, 2, 1 } are not allowed). If you want to allow repeated elements you can remove the remaining variable and replace it with values in the recursive call to GetCombinations.

Please note the use of the yield keyword. This means that the code uses deferred execution. There is no need to store any intermediate results before you actually enumerate the result.

public static IEnumerable<IEnumerable<T>> GetCombinations<T>(IEnumerable<T> values, int threshold)
{
    var remaining = values;

    foreach (T value in values)
    {
        yield return value.Yield();

        if (threshold < 2)
        {
            continue;
        }

        remaining = remaining.Skip(1);

        foreach (var combination in GetCombinations(remaining, threshold - 1))
        {
            yield return value.Yield().Concat(combination);
        }
    }
}

public static IEnumerable<T> Yield<T>(this T item)
{
    yield return item;
}

For the integer array { 1, 2, 3, 4, 5 } the output is:

1
1, 2
1, 2, 3
1, 2, 4
1, 2, 5
1, 3
1, 3, 4
1, 3, 5
1, 4
1, 4, 5
1, 5
2
2, 3
2, 3, 4
2, 3, 5
2, 4
2, 4, 5
2, 5
3
3, 4
3, 4, 5
3, 5
4
4, 5
5

Answer 2

Assuming you already have a solution to find the combinations for a particular count (which you've said you have), let's say of the signature:

public static IEnumerable<IEnumerable<T>> Combinations<T>(
    IList<T> source, int count)

Then you can easily get the combinations for all counts by calling it N times:

public static IEnumerable<IEnumerable<T>> Combinations<T>(IList<T> source)
{
    return Enumerable.Range(0, source.Count)
            .SelectMany(i => Combinations(source, i));
}

Answer 3

Here is one solution:

public static IEnumerable<T[]> Combinations<T>(IEnumerable<T> items, int threshold)
{
    var comboBuilder = new List<T>();
    foreach (var combo in EnumerateCombos(items, comboBuilder, 0, threshold))
    {
        yield return combo;
    }
}
private static IEnumerable<T[]> EnumerateCombos<T>(IEnumerable<T> items, List<T> currentCombo, 
                                                   int startIndex, int threshold)
{
    if (currentCombo.Count >= threshold) { yield break; }

    for (int i = startIndex; i < items.Count(); i++)
    {
        //Skip past the items we've already gone through in the current combo:
        var item = items.Skip(i).First();

        //Create a new combination with the next available item:
        currentCombo.Add(item);
        yield return currentCombo.ToArray();

        //Repeat the process with the rest of the remaining items:
        foreach (var combo in EnumerateCombos(items, currentCombo, i + 1, threshold))
        {
            yield return combo;
        }

        //Recursion cleanup:
        currentCombo.RemoveAt(currentCombo.Count - 1);
    }
}