Pick a varying number of item combinations from a List

Question

Assume I have a list of integers of any length, for an example I have the list of 1,3,5 and 7.

I would like an algorithm to pick a combination of X elements from the list.

For example, X = 1 would return:

1

3

5

7

x = 2 would return:

1 + 1

1 + 3

1 + 5

1 + 7

3 + 3

3 + 5

3 + 7

5 + 5

5 + 7

7 + 7

var listOfInts = new List<int> { 1, 3, 5, 7 };
var combinedInts = new List<int>();

// x = 1 solution
// This is only picking one item from the list. 
for (int i = 0; i < listOfInts.Count(); i++)
{
    combinedInts.Add(listOfInts[i]);
}

// x = 2 solution
// This is how to pick two. I wrap it around another for loop.
for (int i = 0; i < listOfInts.Count(); i++)
{
    for (int j = i; j < listOfInts.Count(); j++)
    {
        combinedInts.Add(listOfInts[i] + listOfInts[j]);
    }
}

// x = 3 solution
// If I go up another level I have to wrap it around another for loop. This solution won't scale.
for (int i = 0; i < listOfInts.Count(); i++)
{
    for (int j = i; j < listOfInts.Count(); j++)
    {
        for (int k = j; k < listOfInts.Count(); k++)
        {
            combinedInts.Add(listOfInts[i] + listOfInts[j] + listOfInts[k]);
        }
    }
}

This solution doesn't scale as I have to continually wrap around another for loop for each number of element I'm picking. For example X = 7 would need 7-nested for loops. Is there a better way to write this method that doesn't involve nesting for loops?

Answer 1

You can use the following to get combinations of the sequences:

public static class LinqHelper
{
    public static IEnumerable<IEnumerable<T>> Combinations<T>(this IEnumerable<T> elements, int? k = null)
    {
        if (!k.HasValue)
            k = elements.Count();

        return k == 0 ? new[] { new T[0] } :
           elements.SelectMany((e, i) => elements.Skip(i).Combinations(k - 1).Select(c => (new[] { e }).Concat(c)));
    }
}

var list = new List<int> { 1, 3, 5, 7 };

int x = 2; //Change to 3, 4, 5, etc

var result = list.Combinations(x);

Yields:

1 1
1 3
1 5
1 7
3 3
3 5
3 7
5 7
7 7

To get the sum of each one, you'd aggregate the result:

var result = list.Combinations(x).Select(g => g.Aggregate((left, right) => left + right));

Which produces:

2
4
6
8
6
8
10
10
12
14

Answer 2

There is also a purely iterative way to do this. It requires a great deal more thought and complexity, but can be made very efficient. The basic idea is to simulate the same nested loops, but track the iterations of each nested loop as an array of loop counters, which are iterated forward in the same manner as the original nested loop code. Here is a fully working example:

var listOfInts = new List<int> { 1, 3, 5, 7 };
var combinedInts = new List<int>();

var numInts = listOfInts.Count;
var numElements = 5; // number of "nested loops", or ints selected in each combination
var loopCounters = new int[numElements]; // make one loop counter for each "nested loop"
var lastCounter = numElements - 1; // iterate the right-most counter by default

// maintain current sum in a variable for efficiency, since most of the time
// it is changing only by the value of one loop counter change.
var tempSum = listOfInts[0] * numElements;

// we are finished when the left/outer-most counter has looped past number of ints
while (loopCounters[0] < numInts) {
    // you can use this to verify the output is iterating correctly:
    // Console.WriteLine(string.Join(",", loopCounters.Select(x => listOfInts[x])) + ": " + loopCounters.Select(x => listOfInts[x]).Sum() + "; " + tempSum);

    combinedInts.Add(tempSum);

    tempSum -= listOfInts[loopCounters[lastCounter]];
    loopCounters[lastCounter]++;
    if (loopCounters[lastCounter] < numInts) tempSum += listOfInts[loopCounters[lastCounter]];

    // if last element reached in inner-most counter, increment previous counter(s).
    while (lastCounter > 0 && loopCounters[lastCounter] == numInts) {
        lastCounter--;
        tempSum -= listOfInts[loopCounters[lastCounter]];
        loopCounters[lastCounter]++;
        if (loopCounters[lastCounter] < numInts) tempSum += listOfInts[loopCounters[lastCounter]];
    }

    // if a previous counter was advanced, reset all future counters to same
    // starting number to start iteration forward again.
    while (lastCounter < numElements - 1) {
        lastCounter++;
        if (loopCounters[lastCounter] < numInts) tempSum -= listOfInts[loopCounters[lastCounter]];
        loopCounters[lastCounter] = loopCounters[lastCounter - 1];
        if (loopCounters[lastCounter] < numInts) tempSum += listOfInts[loopCounters[lastCounter]];
    }
}

At the end of the iteration, combinedInts should contains a list of all sum combinations, similar to the original code or the other recursive solutions. If you are working with small sets, and small combinations, then this level of efficiency is unnecessary and you should prefer a recursive solution which is easier to reason about correctness. I present this as an alternative way to think about the problem. Cheers!

Answer 3

This works for me:

Func<IEnumerable<int>, int, IEnumerable<IEnumerable<int>>> generate = null;
generate = (xs, n) =>
    (xs == null || !xs.Any())
        ? Enumerable.Empty<IEnumerable<int>>()
        : n == 1
            ? xs.Select(x => new [] { x })
            : xs.SelectMany(x => generate(xs, n - 1).Select(ys => ys.Concat(new [] { x })));

int[] array = { 1, 3, 5, 7, };

var results =
    generate(array, 3)
        .Select(xs => String.Join("+", xs));

With this call I get:

1+1+1, 3+1+1, 5+1+1, 7+1+1, 1+3+1, 3+3+1, 5+3+1, 7+3+1, 1+5+1, 3+5+1, 5+5+1, 7+5+1, 1+7+1, 3+7+1, 5+7+1, 7+7+1, 1+1+3, 3+1+3, 5+1+3, 7+1+3, 1+3+3, 3+3+3, 5+3+3, 7+3+3, 1+5+3, 3+5+3, 5+5+3, 7+5+3, 1+7+3, 3+7+3, 5+7+3, 7+7+3, 1+1+5, 3+1+5, 5+1+5, 7+1+5, 1+3+5, 3+3+5, 5+3+5, 7+3+5, 1+5+5, 3+5+5, 5+5+5, 7+5+5, 1+7+5, 3+7+5, 5+7+5, 7+7+5, 1+1+7, 3+1+7, 5+1+7, 7+1+7, 1+3+7, 3+3+7, 5+3+7, 7+3+7, 1+5+7, 3+5+7, 5+5+7, 7+5+7, 1+7+7, 3+7+7, 5+7+7,7+7+7