How to list all possible combinations of a N value set, where each value is from a fixed subset of values using C#?

Question

if there are N values, each value can be drawn from a sub-set of values, say (1,2,3) for example, then how to derive the possible combinations? note that each one will contain N values, not the subsets.

for example, let's say N = 4, the possible outputs could be:

1,1,1,1

1,2,1,3

2,1,1,3

...

@user3185569 the marked duplicate produces a completely different output than the mentioned. — fubo, Aug 31 '16 at 06:19
it is a bit different from the suggested question. my question required N values for the possible solution, not the sub set — Joseph Wu, Aug 31 '16 at 06:21
It's not clear what combinations do you want. What does `...` mean here? — MBo, Aug 31 '16 at 06:35
@JoeWu, you haven't already set an answer as the accepted one... You should check it, unless none of them was useful for your situation — Massimiliano Kraus, Nov 09 '16 at 22:33
thanks for reminding. I've upvoted MBo and yours at that time but didn't realized the 'answer' flag needs to be checked. :) — Joseph Wu, Nov 09 '16 at 23:07

score 2 · Accepted Answer · edited Oct 09 '17 at 08:42

If you have M different values and want to generate N-element combinations, consider these combinations as N-digit numbers in M-ary numeral system. There are M^N such combinations. Pseudocode:

for i = 0 to Power(M, N) - 1 do
    represent i in M-ary system:
      tmp = i
      for k = 0 to N - 1 do
          digit[k] = tmp % M         //integer modulo
          tmp = tmp / M              //integer division

Example: if N = 3, M = 3, there are 27 combinations , and at 11-th step we have
11(dec) = 102 (trinary), combination is (1,0,2) if set is zero-based, or (2,1,3) if it is 1-based

score 1 · Answer 2 · answered Aug 31 '16 at 08:06

This is another solution, using a static utility class:

static class SequencesCalculation
{
    public static List<int[]> Calculate(int[] availableValues, int digitsCount)
    {
        var combIndexes = CalculateRecursive(new List<int[]>(), availableValues.Length, new int[digitsCount], digitsCount - 1);

        var result = combIndexes.Select(x => x.Select(i => availableValues[i]).ToArray()).ToList();

        return result;
    }

    static List<int[]> CalculateRecursive(List<int[]> doneCombinations, int valuesCount, int[] array, int i)
    {
        doneCombinations.Add((int[])array.Clone());

        //base case
        if (array.All(x => x == valuesCount - 1))
            return doneCombinations;

        NextCombination(array, valuesCount, i);

        return CalculateRecursive(doneCombinations, valuesCount, array, i);
    }

    static void NextCombination(int[] array, int valuesCount, int i)
    {
        array[i] = (array[i] + 1) % valuesCount;

        if (i == 0)
            return;

        if (array[i] == 0)
            NextCombination(array, valuesCount, i - 1);
    }
}

I think the @MBo solution is far more elegant than mine. I don't know which is faster. His solution has lot of arithmetic divisions, but mine has much stack allocation forward and backward because of all the recursive method calls.

Anyway, I think that his solution should be checked as the correct answer.

How to list all possible combinations of a N value set, where each value is from a fixed subset of values using C#?

2 Answers2