How to generate all possible values in an array where [x] >= [x+1]?

Question

I'm attempting to write an algorithm that takes an array of size n and generating all possible combinations of integer values up to size max where the number in position x is greater than or equal to x+1.

So for an array of size 4 and max of 5:

{0, 0, 0, 0}
{4, 3, 2, 1}
{2, 2, 0, 0}
{5, 5, 5, 5}

Are all acceptable values.

{0, 1, 2, 3}
{0, 3, 0, 0}
{6, 6, 6, 6}

Are invalid.

For an array of size 4 and max of 1 this would be all the possible combinations:

{0, 0, 0, 0}
{1, 0, 0, 0}
{1, 1, 0, 0}
{1, 1, 1, 0}
{1, 1, 1, 1}

I just can't seem to get my head around how to implement it for any value for max. So I'm asking you guys if you could give me a hand :D

Is there a name for these series?

Answer 1

I worked it out, no recursion necessary.

I'm posting the answer for anyone else who's looking for the answer for the question I asked.

public static void next(int[] data)
{
    final int arrayLen = data.length;
    int lowestIndex = 0;
    int lowestValue = data[0];

    for (int i = 1; i < arrayLen; i++)
    {
        if (data[i] < lowestValue)
        {
            lowestValue = data[i];
            lowestIndex = i;
        }
    }

    data[lowestIndex]++;

    for (int j = lowestIndex + 1; j < arrayLen; j++)
    {
        data[j] = 0;
    }
}

It iterates through the entire array and finds the first occurance of the smallest value. That value is incremented by one and resets all values after it to zero.

Answer 2

Where are you having problems? Hint: recursion is your friend (you can use recursion for nested loops where the nesting level is determined only at runtime).

Answer 3

Have a subroutine that takes n and max and returns a set of arrays.

If n > 1, it calls itself recursively with n-1 instead, and for each result the recursive call returned, generates one or more arrays with an additional leftmost element varying between the previous leftmost element and max.

If n is 1, it returns max+1 1-element arrays containing values from 0 to max.