1

如果我搞砸了，请原谅我，这是我的第一个问题。我已经研究这个问题几个小时了。它应该使用递归生成字符串中的所有字符子集（不一定是子字符串）。我评论了很多，所以你可以看到我的想法，并希望能告诉我哪里出错了。如果这有什么不同，我将使用 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();
    }

}
4

4 回答 4

1

给你：

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]
于 2013-07-08T06:24:56.723 回答
0

您应该将剩余的字符串作为参数传递给 generateSubsets(remaining) 方法。您在每次递归调用时都访问相同的剩余副本，它始终等于原始副本，并且它永远不会达到剩余长度（） == 1 的条件。您应该将修改后的剩余字符串传递给 generateSubsets（）。

编辑是的，你是对的。我发现了问题。它在你的 for 循环中。每次将项目添加到子集中时，它的大小都会不断增加。所以for循环变成了无限循环。进行此更改

int size = subset.size()

for(int i =0; i< size; i++)
{..}
于 2013-07-08T06:02:14.373 回答
0

我宁愿建议从初始字符串创建字符数组并使用该数组。在这里创建大量子字符串并不是最好的选择。

您还可以通过 jvm 参数增加可用内存，例如 -Xmx1g -XX:MaxPermSize=512m -XX:MaxHeapSize=256m

于 2013-07-08T06:09:53.680 回答
-1

我不太确定你在寻找什么结果....但如果不是这样，我相信我可以按照你想要的方式得到它。请给我们一个示例数据和结果。

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]”

当发送空字符串或空列表时，此代码也不执行任何操作。如果您愿意，请编辑列表检查。

于 2013-07-08T05:51:44.153 回答