用条件查找给定N的所有排列的算法

Question

我正在设计一个程序来打印给定N的所有排列，使得每个数字应该大于下一个数字。

对于实施例 如果N = 3： 输出应123,456,789,134,145,178,189等...

初始设计：

1. 生成所有可能的排列

2. 传递所生成的置换到数字提取功能，检查条件

3. 打印结果

这是一个非常天真的算法。但我不知道实现/初始设计，因为N.

Answer 1

由于N总是小于10，我用递归

调用该函数为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 
     } 
    } 

输出：

123 
124 
... 
678 
679 
689 
789 

Answer 2

的动态大小的只是生成它们在字典序：

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

这里假设你有最多5位对于较大的约束B，尽管继续。一些简单的代码来做到这一点：

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; 

开始w = [1,2,3,...,N];（容易使一个for循环），打印w，拨打上面w作为输入功能，打印的是，和继续。与N = 3和B = 5，答案将是上面的列表（没有...行）。

如果没有绑定B，那么你SOL因为有无穷多个。

一般而言，您正在计算N th elementary symmetric functione_N。

Answer 3

这样做最直接的方法是递归。假设你已经产生了第一个n数字并且产生的最后一个数字是i。你有ñ - ñ剩余的数字产生，他们必须开始与我 + 1或更高。由于最后一位数字不能超过9位，因此下一位数字不能超过10位。（N - n）。这给出了递归的基本规则。像这样的东西（在Java中）应该工作：

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); 
    } 
}