C# Finding all possible combinations of numbers

Question

I'm struggling in the making of algorithm that "shuffles" a set of numbers in such way that they are sorted in ascending order starting from 0 ,the next number must not exceed the previous one + 1, they must also have a length of 15 and every single number from the set of numbers must be included. For example if we have the numbers :

0, 1

the desired output is :

0,0,0,0,0,0,0,0,0,0,0,0,0,0,1 (yes those are 14 zeros)

0,0,0,0,0,0,0,0,0,0,0,0,0,1,1

..

0,1,1,1,1,1,1,1,1,1,1,1,1,1,1

same goes if the numbers were

0, 1, 2

0,0,0,0,0,0,0,0,0,0,0,0,0,1,2 (every number must be included)

I tried the following and I failed miserably :

Version 1

private static List<List<int>> GetNumbers(int lastNumber)
    {
        if (lastNumber == 0)
        {
            return new List<List<int>> { new List<int> { 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 } };
        }
        int[] setOfNumbers = new int[lastNumber + 1];
        List<List<int>> possibleRoutes = new List<List<int>>().ToList();
        for (int i = 0; i <= lastNumber; i++)
        {
            setOfNumbers[i] = i;
        }
        var temp = new List<int>();
        int[] possibleRoute = new int[15];
        for (int j = 0; j < size - lastNumber; j++)
        {
            possibleRoute[j] = 0;
        }
        for (int j = lastNumber; j < possibleRoute.Length; j++)
        {
            for (int k = j; k > 0; k--)
            {
                possibleRoute[k] = lastNumber - 1;
            }
            for (int i = size - 1; i >= j; i--)
            {
                possibleRoute[i] = lastNumber;
            }
            possibleRoutes.Add(possibleRoute.ToList());
            generalCounter++;
        }
        return possibleRoutes;
    }

Version 2

private static List<List<int>> GetNumbers(int lastNumber)
    {
        if (lastNumber == 0)
        {
            return new List<List<int>> {new List<int> {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0}};
        }
        int[] setOfNumbers = new int[lastNumber + 1];
        List<List<int>> possibleRoutes = new List<List<int>>().ToList();
        for (int i = 0; i <= lastNumber; i++)
        {
            setOfNumbers[i] = i;
        }
        var temp = new List<int>();
        int[] possibleRoute = new int[15];
        for (int j = 0; j < size - lastNumber; j++)
        {
            possibleRoute[j] = 0;
        }
        for (int i = 1 ; i <= lastNumber ; i++)
        {
            int newNumber = lastNumber - i;
            for (int k1 = i + 1; k1 <= size; k1++)
            {
                for (int j = possibleRoute.Length - 1; j > k1 - i - 1; j--)
                {
                    possibleRoute[j] = lastNumber;
                }
                for (int k = i; k <= k1 - 1; k++)
                {
                    possibleRoute[k] = newNumber;
                }
                possibleRoutes.Add(possibleRoute.ToList());
                generalCounter++;
            }
        }
        return possibleRoutes;
    }

Answer 1

I misunderstood the problem. Starting this answer over.

Let's state the problem another way.

We have a number of items, fifteen.

We have a number of digits, say 0, 1, 2.

We wish to know what are the combinations of x zeros, y ones and z twos such that x + y + z = 15 and x, y and z are all at least one.

So, reduce it to an easier problem. Suppose there is one zero. Now can you solve the easier problem? The problem is now smaller: the problem is now "generate all the sequences of length 14 that have at least one 1 and one 2". Do you see how to solve the easier problem?

If not, break it down into a still easier problem. Suppose there is one 1. Can you solve the problem now? The problem now is to find all the sequences that have thirteen 2s in them, and there's only one of those.

Now suppose there are two 1s. Can you solve the problem there?

Do you see how to use the solution to the easier problems to solve the harder problems?

Answer 2

A simple strategy which works with a wide variety of problems like this is to list the possibilities in lexicographical order. In pseudocode, you would do something like this:

1. Set V to the first possible sequence, in lexicographical order.

2. Repeat the following:

   • Output V
   • If possible, set V to the next sequence in lexicographical order.
   • If that was not possible, exit the loop.

For many cases, you can solve the second sub-problem ("set V to the next sequence") by searching backwards in V for the right-most "incrementable" value; that is, the right-most value which could be incremented resulting an a possible prefix of a sequence. Once that value has been incremented (by the minimum amount), you find the minimum sequence which starts with that prefix. (Which is a simple generalization of the first sub-problem: "find the minimum sequence".)

In this case, both of these sub-problems are simple.

• A value is incrementable if it is not the largest number in the set and it is the same as the preceding value. It can only be incremented to the next larger value in the set.

• To find the smallest sequence starting with a prefix ending with k, start by finding all the values in the set which are greater than k, and putting them in order at the end of the sequence. Then fill in the rest of the values after the prefix (if any) with k.

For the application of this approach to a different enumeration problem, see https://stackoverflow.com/a/30898130/1566221. It is also the essence of the standard implementation of next_permutation.