如何以所有可能的方式分割數字？

Question

我有很多，比方說123，我想生成的所有可能的方式列表的列表拆分它：

[[1,2,3], [12,3], [1, 23], [123]] 

我發現了一段代碼，幾乎做到這一點：http://www.quora.com/How-do-I-take-a-string-by-the-user-and-split-it-in-all-possible-ways。

我已經修改了一點：

class breakString 
{ 
    public static List<List<Integer>> res = new ArrayList<>(); 

public static List<List<Integer>> breaker(String input, int start, int end, List ans) 
{ 
    if(start > end) 
    { 
     System.out.println(ans); 

     res.add(ans); 
     System.out.println("res:" + res.toString()); 
    } 
    else 
    { 
      ans.add(input.charAt(start) + ""); 
      breaker(input, start+1, end, ans); 

      int listSize = ans.size(); 
      ans.remove(listSize - 1); 
      String lastChar = ans.get(listSize - 2).toString(); 
      ans.remove(listSize - 2); 
      ans.add(lastChar + input.charAt(start) + ""); 
      breaker(input, start+1, end,ans); 
    } 
    return res; 
} 

public static void main(String args[]) 
{ 
String input = "123"; 

List ans = new ArrayList(); 
ans.add(input.charAt(0) + ""); 

breaker(input,1, input.length() - 1, ans);  
    System.out.println("----------------------------------------------"); 

    for (List<Integer> intList : res) 
    { 
     System.out.println(intList); 
    } 
} 
} 

但althought它打印正確的解決方案，我不能讓它回到它的權利。 輸出是：

[1, 2, 3] 
res:[[1, 2, 3]] 
[1, 23] 
res:[[1, 23], [1, 23]] 
[12, 3] 
res:[[12, 3], [12, 3], [12, 3]] 
[123] 
res:[[123], [123], [123], [123]] 
---------------------------------------------- 
[123] 
[123] 
[123] 
[123] 

你能告訴我如何解決它返回：

[[1,2,3], [12,3], [1, 23], [123]] 

Answer 1

而不是使用反向跟蹤你可以考慮這種解決方案。假設輸入是一個包含n數字的數字。該號碼可以分爲n - 1職位。我們可以描述每種方式將輸入數字分成boolean的一個字符串 - 或者假設輸入數字不大於10^32，則作爲int。現在問題很簡單：每個不同的分割輸入號碼的方式都由int表示。 0表示不分割（原始輸入將被返回），並且最低有效位設置爲HI的數字將表示分割爲所有部分。現在執行：

public List<List<String>> split(int in) { 
    List<List<String>> result = new ArrayList<>(); 

    String num = String.valueOf(in); 

    //the maximum is to split the number at each possible position 
    int maxSplit = 0; 
    for (int i = 0; i < num.length() - 1; i++) 
     maxSplit |= (1 << i); 

    for (int i = 0; i <= maxSplit; i++) { 
     List<Integer> split = new ArrayList<>(); 

     //translate the representation of the splitting into the respective indices 
     for (int b = 0; b < num.length() - 1; b++) 
      if ((i & (1 << b)) != 0) 
       split.add(b + 1); 

     //ensure that the last part of the solution is in the result 
     split.add(num.length()); 

     //split the input in the specified way 
     List<String> strings = new ArrayList<>(); 
     int lastSplit = 0; 
     for (int s : split) { 
      strings.add(num.substring(lastSplit, s)); 

      lastSplit = s; 
     } 

     result.add(strings); 
    } 

    return result; 
} 

Answer 2

這是因爲您在所有迭代中使用相同的ArrayList(ans)。因此，即使增加ans後您res它的變化（當添加ans到res它是由參考添加，因此下一個水平的變化也將反映在res這就是爲什麼你只得到了這是在末尾添加123）。

所以，簡單地改變

 res.add(ans); 

到

 res.add(new ArrayList<String>(ans)); 

一切都將正常工作。

Answer 3

我把被接受的答案提出的辦法和實施自己的版本，但沒有使用位運算符和它的作品爲字符串或數字，任意長度：

public class ListSplitter { 

    public static void main(String[] args) { 
    String data = "ABCDEFGHIJK"; 

    int combinations = (int) Math.pow(2, data.length() - 1); 
    for(int c = 0; c < combinations; c++) { 
     String pattern = ""; 
     int half = (int)combinations/2; 
     while(half >= 1) { 
     pattern += Integer.toString((int)(c/half) % 2); 
     half = (int)half/2; 
     } 
     System.out.println(tokenize(pattern, data)); 
    } 
    } 

    private static String tokenize(String pattern, String data) { 

    int patternIndex = 0; 
    int dataIndex = 0; 
    String result=""; 

    for(int index = 0; index < (data.length() * 2) - 1; index++) { 
     if(index % 2 == 0) { 
     result += data.charAt(dataIndex++); 
     } 
     else { 
     if(pattern.charAt(patternIndex++) == '1') { 
      result += ","; 
     } 
     } 
    } 
    return result; 
    } 
}