Algorithm to find all permutations of a given N with condition

Question

I am designing a program to print all permutations of a given N such that the each digit should be greater than the next digit.

For Example if N=3: output should be 123,456,789,134,145,178,189 etc...

Initial Design:

1. Generate all possible permutations

2. Pass the generated permutation to a digit extraction function which checks for the condition

3. Print out the result

This is a very naive algorithm. But I do not know the implementation/initial design because of the dynamic size of N.

Answer 1

Since N will always be less than 10, i've used recursion

Call the function as f(3,0,0)

public static void f(int N,int digit,int num)
    {
        if(N > 0 )
        {
            for(int d = digit + 1; d < 11 - N; d++) // earlier d < 10, see comments
            {
                f(N-1,d,num * 10 + d);
            }
        }else {
            System.out.println(num); //add it to a list or whatever
        }
    }

Output:

123
124
...
678
679
689
789

Answer 2

Just generate them in lexicographic order:

123
124
125
...
134
135
...
145
...
234
235
...
245
...
345

This assumes you have digits at most 5. For larger bound B, just keep going. Some simple code to do this is:

nextW = w;
for (int i=n-1; i>=0; --i) {
    // THE LARGEST THE iTH DIGIT CAN BE IS B-(n-i-1)
    // OTHERWISE YOU CANNOT KEEP INCREASING AFTERWARDS
    // WITHOUT USING A NUMBER LARGER THAN B
    if w[i]<B-(n-i-1) {
        // INCREMENT THE RIGHTMOST POSITION YOU CAN
        nextW[i] = w[i]+1;
        // MAKE THE SEQUENCE FROM THERE INCREASE BY 1
        for (int j=i+1; j<N; ++j) {
            nextW[j] = w[i]+j-i+1;
        }
        // VOILA
        return nextW;
    }
}
return NULL;

Start with w = [1,2,3,...,N]; (easy to make with a for loop), print w, call the function above with w as an input, print that, and continue. With N = 3 and B = 5, the answer will be the above list (without the ... lines).

If there is no bound B, then you're SOL because there are infinitely many.

In general, you are computing the Nth elementary symmetric function e_N.

Answer 3

The most straightforward way to do this is with recursion. Suppose you've generated the first n digits and the last digit generated is i. You have N - n digits left to generate and they must start with i + 1 or higher. Since the last digit can be no more than 9, the next digit can be no more than 10 - (N - n). This gives the basic rule for recursion. Something like this (in Java) should work:

void generate(int N) {
    int[] generated = new int[N];
    generate(generated, 0);
}

void generate(int[] generated, int nGenerated) {
    if (nGenerated == generated.length) {
        // print the generated digits
        for (int g : generated) {
            System.out.print(g);
        }
        System.out.println();
        return;
    }
    int max = 10 - (generated.length - nGenerated);
    int min = nGenerated == 0 ? 1 : (generated[nGenerated - 1] + 1);
    for (int i = min; i <= max; ++i) {
        generated[nGenerated] = i;
        generate(generated, nGenerated + 1);
    }
}