字符串的排列...邏輯錯誤？

Question

我正在嘗試生成給定字符串的所有排列組合。

使用

假設字符串ABCD =

1）然後我修復邏輯IM 'A'（類似地每個字符..第一次迭代 - ABCD，第二BACD，第三CABD。 ....）在第一個循環的第一個位置..

2）然後生成字符串通過移動第二個字符，即'b' 在所有的地方..就像abcd，acbd，acdb ...

3）然後我重新放置第三（第四，第五等）字符與 第二字符內並重復所述第二步驟中再次

4）我改變ABCD至BACD（N所以對於每個字符），並重復步驟 2,3 .. 。

現在

應不小於有actually..like 4此生成所有可能的combinations..and也是我用一棵樹設置爲刪除重複項... 但不知何故，它產生較少的排列字符，僅20個排列...

這裏是代碼相同..

import java.util.*; 

public class practice4 { 


    public static void main(String[] args) { 



     TreeSet t = new TreeSet(); 
     String arr[] = new String[100]; 
     int z = -1; 
     StringBuffer s5 = new StringBuffer("abcde"); 


     for (int i = 0; i <= s5.length() - 1; i++) { 

      char ch = s5.charAt(0); 
      s5.setCharAt(0, s5.charAt(i)); 
      s5.setCharAt(i, ch); 

      StringBuffer s3 = new StringBuffer(s5); 

      for (int j = 1; j <= s3.length() - 1; j++) { 

       StringBuffer s2 = new StringBuffer(s3); 
       // System.out.println(s2); 

       z++; 
       arr[z] = s2.toString(); 

       for (int k = 1; k < s3.length() - 1; k++) { 

        char ch2 = s2.charAt(k); 
        s2.setCharAt(k, s2.charAt(k + 1)); 
        s2.setCharAt(k + 1, ch2); 
        // System.out.println(s2); 

        z++; 
        arr[z] = s2.toString(); 

       } 

       if (j >= s3.length() - 1) 
        break; 
       char ch3 = s3.charAt(1); 

       s3.setCharAt(1, s3.charAt(j + 1)); 
       s3.setCharAt(j + 1, ch3); 

      } 

      System.out.println("dooone"); 

      System.out.println(z); 
      for (int x = 0; x <= z; x++) { 

       t.add(arr[x]); 

      } 

     } 

     System.out.println(t.size()); 
     Iterator i55 = t.iterator(); 
     while (i55.hasNext()) { 
      System.out.println(i55.next()); 
     } 
    } 

} 

Answer 1

您可以檢查這些帖子求助：

http://www.programmerinterview.com/index.php/recursion/permutations-of-a-string/

OR

Generating all permutations of a given string

Answer 2

你3個嵌套循環可以生成的最大值n^3串長度爲n的輸入字符串。然而，排列的數量要大得多（n！），所以結果集對於大的n必須是部分的。

此外，你的論點認爲邏輯應該產生所有的排列，因爲每個字符在每個可能的位置是不正確的。每一個元素訪問所有職位並不意味着所有可能的安排都會被訪問。例如，對於n = 3：

123 
213 
321 
312 

所有項目出現在所有位置，但名單仍缺少序列132和231

如果遞歸是可以接受的，請考慮以下解決方案：

public static Collection<String> permutations(String s) { 
    ArrayList<String> l = new ArrayList<String>(); 
    permutations(s.toCharArray(), 0, l); 
    return l; 
    } 

    private static void permutations(char[] chars, int i, ArrayList<String> l) { 
    if (i == chars.length) { 
     l.add(new String(chars)); 
     return; 
    } 

    for (int j = i; j < chars.length; j++) { 
     swap(chars, i, j); 
     permutations(chars, i + 1, l); 
     swap(chars, i, j); 
    } 
    } 

    private static void swap(char[] chars, int i, int j) { 
    char tmp = chars[i]; 
    chars[i] = chars[j]; 
    chars[j] = tmp; 
    } 

該算法背後的歸納思想是，排列集合是選擇第一個字符並以尾部遞歸連續產生的長度爲n-1的所有排列的並集。假設輸入字符串沒有重複字符，這個聯合是不相交的，所以我們不必處理重複。

一種非遞歸的溶液：

private static Collection<String> permutations2(String str) { 
    ArrayList<String> listNew = new ArrayList<String>(); 
    ArrayList<String> listPrev = new ArrayList<String>(); 

    char chr = str.charAt(0); 
    listPrev.add("" + chr); 

    for (int i = 1; i < str.length(); i++) { 
     chr = str.charAt(i); 

     for (String s : listPrev) { 
     for (int idx = 0; idx <= s.length(); idx++) { 
      String perm = s.substring(0, idx) + chr + s.substring(idx); 
      listNew.add(perm); 
     } 
     } 

     listPrev = listNew; 
     listNew = new ArrayList<String>(); 
    } 
    return listPrev; 
    } 

的想法是，在階段I我們生成長度i的所有排列，基於在先前的階段中產生長度i-1的所有排列。這是通過將新字符插入長度爲i-1的每個排列的所有可能位置來完成的。假設原始字符串具有唯一字符，該解決方案還保證了結果的唯一性。