0

我最近试图编写一个脚本，打印出 Java 中一个单词的所有排列。由于某种原因，它只打印出一个。我就是想不通！

import java.util.*;

public class AllPermutations {

    ArrayList<String> letters = new ArrayList<String>();
    public void main(){
        letters.add("H");
        letters.add("a");
        letters.add("s");
        permutate("",letters);
    }

    public void permutate(String word, ArrayList<String> lettersLeft){
        if(lettersLeft.size()==0){
            System.out.println(word);
        }else{
            for(int i=0;i<lettersLeft.size();i++){
                String newWord = new String();
                newWord = word+lettersLeft.get(i);
                lettersLeft.remove(i);
                permutate(newWord, lettersLeft);
            }
        }
    }
}
4

3 回答 3

3

您需要将已删除的字母添加回 lettersLeft 列表

public void permutate(String word, ArrayList<String> lettersLeft){
    if(lettersLeft.size()==0){
        System.out.println(word);
    }else{
        for(int i=0;i<lettersLeft.size();i++){
            String temp = lettersLeft.remove(i);
            String  newWord = word+temp;
            permutate(newWord, lettersLeft);
            lettersLeft.add(i, temp);
        }
    }
}

我还没有测试过，但我认为它应该可以工作。

问题是 Java/您通过引用传递，而不是复制（ArrayList）。因此，一旦您到达递归树的底部， lettersLeft 将包含 0 个元素，而一旦您返回，它仍将包含 0 个元素。

附带说明一下，StringBuilder/StringBuffer 更擅长执行字符串置换任务，因为 String 是不可变的，因此创建新字符串会浪费大量资源，n！确切地说。两个 StringBuilder/Buffer 的区别由你来发现。

于 2013-02-01T03:06:54.980 回答
0

原因是lettersLeft总是通过引用传递。一旦您从 lettersLeft 中删除了一个字母，它就会被永久删除。因此，对于第一次迭代，您打印出“HAS”。一旦完成，递归算法会备份一个级别以进行第二次迭代，但是您知道什么？字母左为空。所以它在没有通过 if 语句的情况下终止，导致它没有得到另一个单词或排列。为了解决这个问题，创建一个本地副本，就像使用 newWord 一样。希望有帮助。

于 2013-02-01T03:40:33.440 回答
-1

在这种情况下，您要从中删除字母Arraylist，它会变空，直到它到达第一个单词的末尾。然后在该列表大小之后总是为零Add the removed letter back to the list............

我希望recommend您使用下面的链接并找到字符串排列的好例子，因为字符串排列有内存高效和空间高效的解决方案......

http://www.codingeek.com/java/strings/find-all-possible-permutations-of-string-using-recursive-method/

于 2014-09-22T10:58:34.530 回答