使用遞歸生成字符串中的所有字符子集，JAVA

Question

請原諒我，如果我搞砸了，這是我的第一個問題。我一直在解決這個問題幾個小時。它應該使用遞歸生成字符串中的所有子字符（不一定是子字符串）。我評論了很多，所以你可以看到我的想法，並希望告訴我哪裏出錯了。如果這有什麼不同，我將Eclipse用作IDE。

import java.util.ArrayList; 

//Generates subsets of a string 
public class SubsetGenerator 
{ 
    private String original; 
    private String remaining; 
    private ArrayList<String> subsets; 
    //Constructs a subset generator 
    //@param input string to have subsets generated 
    public SubsetGenerator(String input) 
    { 
     original = input; 
     remaining = original; 
     subsets = new ArrayList<String>(); 
    } 

    public void printSubsets() 
    { 
     System.out.print(subsets); 
    } 
    //gets subsets 
    public void generateSubsets() 
    {  
     //if the string is empty, it has no subsets 
     if(remaining.length() == 1) 
     { 
      subsets.add(remaining); 
      return; 
     } 
     else 
     { 
      //remove the first character and hold onto it 
      String removed = remaining.substring(0,1); 
      remaining = remaining.substring(1); 
      //recursion. Eventually it should add the last character in the string to the ArrayList and return 
      generateSubsets(); 
      //Take each element that is in the ArrayList, add the removed character to it, add this back to the list 
      for (int i = 0; i < subsets.size(); i++) 
      { 
       String temp = removed + subsets.get(i); 
       subsets.add(temp); 
      } 
      subsets.add(removed);//add the removed character by itself 
      return; 
     } 
    } 

} 

這是我得到的錯誤：

Exception in thread "main" java.lang.OutOfMemoryError: Java heap space 
    at java.util.Arrays.copyOfRange(Arrays.java:3221) 
    at java.lang.String.<init>(String.java:233) 
    at java.lang.StringBuilder.toString(StringBuilder.java:447) 
    at SubsetGenerator.generateSubsets(SubsetGenerator.java:41) 
    at SubsetGenerator.generateSubsets(SubsetGenerator.java:37) 
    at SubsetGenerator.generateSubsets(SubsetGenerator.java:37) 
    at SubsetGenerator.generateSubsets(SubsetGenerator.java:37) 
    at SubsetGeneratorTester.main(SubsetGeneratorTester.java:7) 

我使用此代碼測試它：

public class SubsetGeneratorTester 
{ 
    public static void main(String[] args) 
    { 
     SubsetGenerator s = new SubsetGenerator("world"); 
     s.generateSubsets(); 
     s.printSubsets(); 
    } 

} 

Answer 1

您應該將剩餘的字符串作爲參數傳遞給generateSubsets（remaining）方法。您正在訪問每次遞歸調用時剩餘的相同副本，並且它始終等於原始值，並且它永遠不會遇到remaining.length（）== 1的情況。您應該將修改的剩餘字符串傳遞給generateSubsets（）。

編輯是的，你是對的。我發現了這個問題。它在你的for循環中。每次您將項目添加到子集時，它的大小都在不斷增加。因此for循環變成無限循環。做這個改變

int size = subset.size() 

for(int i =0; i< size; i++) 
{..} 

Answer 2

我不太清楚是什麼導致你正在尋找因爲......但如果不是這樣，我相信我可以按照你想要的方式得到它。請給我們一個示例數據和結果。

public void GetSubsets(String str, ArrayList list) 
{ 
     if(str.length() > 0 && list != null) 
     { 
      list.add(str); 
      GetSubsets(str.substring(1), list); 
     } 
} 

輸出爲 「世界」 是：

ArrayList list = new ArrayList(); 
GetSubsets("World", list); 
System.out.println(list.toString()); 

「[世界，ORLD，RLD，LD，d]」

此代碼還什麼都不做的時候有一個空字符串發送或空列表。編輯列表檢查，如果你願意。

Answer 3

我寧願推薦從最初的字符串創建字符數組，並使用數組。創建大量的子串並不是這裏最好的選擇。

您還可以增加可用內存傳遞jvm參數，例如 -Xmx1g -XX：MaxPermSize參數=512米-XX：MaxHeapSize =256米

Answer 4

這裏亞去：

public class SubsetGenerator { 
    public static void main(String[] args) { 
     // TODO Auto-generated method stub 
     ArrayList<String> list = new ArrayList<String>(); 
     StringBuilder myBuilder = new StringBuilder(); 
     String original = "World"; 


     for(int i=0; i<original.length(); ++i) 
      genSubs(original, myBuilder, list, i); 

     System.out.println(list.toString()); 


    } 

static void genSubs(String original, StringBuilder current, ArrayList<String> myList, int index){ 

    current.append(original.charAt(index)); 

    System.out.println(current.toString() + index); 

    myList.add(current.toString()); 


    for(int i=index+1; i<original.length(); ++i) 
     genSubs(original, current, myList, i); 

    current.deleteCharAt(current.toString().length()-1); 


    return; 
} 

} 

輸出：

[W, Wo, Wor, Worl, World, Word, Wol, Wold, Wod, Wr, Wrl, Wrld, Wrd, Wl, Wld, Wd, o, or, orl, orld, ord, ol, old, od, r, rl, rld, rd, l, ld, d]