用條件查找給定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); 
    } 
}