如何打印數字的所有可能的序列n

Question

我試圖打印所有可能的序列n，我不知道我出錯的地方。

例如：如果我讓n = 3，那麼我必須得到可能的組合。

import java.util.Scanner; 

public class MyPermutations { 

    public static void show(int[] a) { 
     for (int i = 0; i < a.length; i++) 
      System.out.printf("%d", a[i]); 
     System.out.printf("\n"); 
    } 

    public static void swap(int[] a, int i, int j) { 
     int temp = a[i]; 
     a[i] = a[j]; 
     a[j] = temp; 
    } 

    public static boolean hasNext(int[] a) { 
     int N = a.length; 

     // find rightmost element a[k] that is smaller than element to its right 
     int k; 
     for (k = N-2; k >= 0; k--) 
      if (a[k] < a[k+1]) break; 
     if (k == -1) return false; 

     // find rightmost element a[j] that is larger than a[k] 
     int j = N-1; 
     while (a[k] > a[j]) 
      j--; 
     swap(a, j, k); 

     for (int r = N-1, s = k+1; r > s; r--, s++) 
      swap(a, r, s); 

     return true; 
    } 

    public static void perm(int N) { 

     // initialize permutation 

     int[] a = new int[N]; 

     for (int i = 1; i < N; i++) {   
      a[0]=1; 
      a[i] = i+1; 

     } 

     // print permutations 
     show(a); 
     while (hasNext(a)) 
      show(a); 
    } 


    public static void main(String[] args) { 
     Scanner sc = new Scanner(System.in); 
     int N = Integer.parseInt(sc.next()); 
     perm(N); 
    } 
} 

輸入：

3 

我的輸出：

123 132 213 231 312 321 

預期輸出：

111 112 113 121 122 123 131 132 133 
211 212 213 221 222 223 231 232 233 
311 312 313 321 322 323 331 332 333 

Answer 1

如果你看看你的輸出，這個問題是顯而易見的。您沒有考慮同一個號碼的多個實例（即2個2或3個3）。

Answer 2

忘掉swap，重新開始。

認爲它像增加一個數字，除了你只能使用數字1-N。

E.g.對於N = 4，從1111開始。打印它。
遞增到1112，然後1113，然後1114。
下一個增量繼續，因此1121，1122，...，1144。
處理多個隨身攜帶，1211。
依次類推，直到達到4444，就完成了。

---

當然，你可以只通過N^N組合循環，並利用司和餘數爲建設 「數字」 每個組合：

private static void perm(int n) { 
    char[] digits = new char[n]; 
    final int combinations = (int)Math.pow(n, n); 
    for (int i = 0; i < combinations; i++) { 
     for (int num = i, j = n - 1; j >= 0; num /= n, j--) 
      digits[j] = (char)('1' + num % n); 
     System.out.print(digits); 
     System.out.print((i + 1) % (n * n) == 0 ? System.lineSeparator() : " "); 
    } 
} 

輸出

// perm(1) 
1 

// perm(2) 
11 12 21 22 

// perm(3) 
111 112 113 121 122 123 131 132 133 
211 212 213 221 222 223 231 232 233 
311 312 313 321 322 323 331 332 333 

// perm(4) 
1111 1112 1113 1114 1121 1122 1123 1124 1131 1132 1133 1134 1141 1142 1143 1144 
1211 1212 1213 1214 1221 1222 1223 1224 1231 1232 1233 1234 1241 1242 1243 1244 
1311 1312 1313 1314 1321 1322 1323 1324 1331 1332 1333 1334 1341 1342 1343 1344 
1411 1412 1413 1414 1421 1422 1423 1424 1431 1432 1433 1434 1441 1442 1443 1444 
2111 2112 2113 2114 2121 2122 2123 2124 2131 2132 2133 2134 2141 2142 2143 2144 
2211 2212 2213 2214 2221 2222 2223 2224 2231 2232 2233 2234 2241 2242 2243 2244 
2311 2312 2313 2314 2321 2322 2323 2324 2331 2332 2333 2334 2341 2342 2343 2344 
2411 2412 2413 2414 2421 2422 2423 2424 2431 2432 2433 2434 2441 2442 2443 2444 
3111 3112 3113 3114 3121 3122 3123 3124 3131 3132 3133 3134 3141 3142 3143 3144 
3211 3212 3213 3214 3221 3222 3223 3224 3231 3232 3233 3234 3241 3242 3243 3244 
3311 3312 3313 3314 3321 3322 3323 3324 3331 3332 3333 3334 3341 3342 3343 3344 
3411 3412 3413 3414 3421 3422 3423 3424 3431 3432 3433 3434 3441 3442 3443 3444 
4111 4112 4113 4114 4121 4122 4123 4124 4131 4132 4133 4134 4141 4142 4143 4144 
4211 4212 4213 4214 4221 4222 4223 4224 4231 4232 4233 4234 4241 4242 4243 4244 
4311 4312 4313 4314 4321 4322 4323 4324 4331 4332 4333 4334 4341 4342 4343 4344 
4411 4412 4413 4414 4421 4422 4423 4424 4431 4432 4433 4434 4441 4442 4443 4444 

Answer 3

如果你想要所有可能的排列組合，你的代碼就好了，因爲排列是從交換元素而不是重複使用它們。 如果您想構建所有可能的組合（包括aaa，aab等），則僅僅交換元素是不夠的。

public List<String> combinations(List<Character> elements) { 
    List<String> combinations = new ArrayList<>(); 

    if (elements.isEmpty()) { 
     return combinations; 
    } 

    if (elements.size() == 1) { 
     combinations.add(String.valueOf(elements.get(0))); 
     return combinations; 
    } 

    for (int i = 0; i < elements.size(); i++) { 
     int current = elements.get(i); 

     List<String> subCombinations = combinations(elements); 

     StringBuilder builder; 
     for (String s : subCombinations) { 
      builder = new StringBuilder(); 
      builder.append(current).append(s); 

      combinations.add(builder.toString()); 
     } 
    } 

    return combinations; 
}