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:
Generate all possible permutations
Pass the generated permutation to a digit extraction function which checks for the condition
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.
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
d < 10 in the for loop with d < 11 - N.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);
}
}
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.
w = [1,2,3,...,N], then generate the next one in lexicographic order with the function described above, which takes w as an input.B. For example, 1 2 3, 1 2 4, 1 2 5, 1 2 6, 1 2 7, 1 2 8, 1 2 9, 1 2 10, 1 2 11, 1 2 12, 1 2 13, 1 2 14, 1 2 15, 1 2 16, 1 2 17, 1 2 18, 1 2 19, 1 2 20, 1 2 21, 1 2 22, 1 2 23, 1 2 24, 1 2 25, 1 2 26, 1 2 27, 1 2 28, 1 2 29, 1 2 30, 1 2 31, 1 2 32, 1 2 33, 1 2 34, 1 2 35, 1 2 36, 1 2 37, 1 2 38, 1 2 39, 1 2 40, 1 2 41, 1 2 42, 1 2 43, 1 2 44, 1 2 45, 1 2 46, 1 2 47, 1 2 48, 1 2 49, 1 2 50, 1 2 51, 1 2 52, 1 2 53, 1 2 54, 1 2 55, 1 2 56, 1 2 57, 1 2 58, 1 2 59, 1 2 60, 1 2 61, 1 2 62, 1 2 63, 1 2 64, 1 2 65, 1 2 66, 1 2 67, character limit attained