0

我想获得一个返回输入字符串所有排列的方法。我在网上搜索了一下，发现大部分都和Robert Sedgewick的代码类似：http: //introcs.cs.princeton.edu/java/23recursion/Permutations.java.html

但是，我想返回排列，而不是打印它们。Robert Sedgewick 的代码复制到这里：

public class Permutations {
    // print N! permutation of the characters of the string s (in order)
    public  static void perm1(String s) { perm1("", s); }
    private static void perm1(String prefix, String s) {
        int N = s.length();
        if (N == 0) System.out.println(prefix);
        else {
            for (int i = 0; i < N; i++)
               perm1(prefix + s.charAt(i), s.substring(0, i) + s.substring(i+1, N));
        }
    }
    public static void main(String[] args) {
       perm1("abcd");
    }
}

Robert Sedgewick 自己编写的代码如下：

import java.util.ArrayList;

public class Test {
    public static ArrayList<String> permute(String prefix, String s){
        int len = s.length();
        ArrayList<String> list = new ArrayList<String>();
        if(s.length() == 0)
            list.add(prefix);
        else
            for(int i = 0; i < len; i++)
                permute(prefix + s.charAt(i), s.substring(0, i) + s.substring(i+1, len));
        return list;
    }
    public static void main(String[] args) {
        String str = "abcd";
        ArrayList<String> array = permute("", str);
        System.out.print(array.size());
    }
}

但是我的代码没有返回排列。它什么也不返回。我不知道为什么。谁能帮我？

4

2 回答 2

2

您需要将 permute 方法的结果添加到 arraylist：

import java.util.ArrayList;

public class Test {
    public static ArrayList<String> permute(String prefix, String s){
        int len = s.length();
        ArrayList<String> list = new ArrayList<String>();
        if(s.length() == 0)
            list.add(prefix);
        else
            for(int i = 0; i < len; i++)
                list.addAll(permute(prefix + s.charAt(i), s.substring(0, i) + s.substring(i+1, len)));
        return list;
    }
    public static void main(String[] args) {
        String str = "abcd";
        ArrayList<String> array = permute("", str);
        System.out.print(array.size());
    }
}
于 2013-05-15T05:38:57.990 回答
2 
import java.util.ArrayList;

public class Test {

    /** Return a list of all the permutations of the given string. */
    public static ArrayList<String> permute(String s){
        ArrayList<String> accum = new ArrayList<String>();
        permute(accum, "", s);
        return accum;
    }

    /**
     * Private helper method to do the actual work.
     *
     * @param accum Accumulator of the results.
     * @param prefix The current prefix.
     * @param s The remaining string to permute.
     */
    private static void permute(ArrayList<String> accum, String prefix, String s){
        int len = s.length();
        if(s.length() == 0)
            accum.add(prefix);
        else
            for(int i = 0; i < len; i++)
                permute(accum, prefix + s.charAt(i), s.substring(0, i) + s.substring(i+1, len));
    }

    public static void main(String[] args) {
        String str = "abcd";
        ArrayList<String> array = permute(str);
        System.out.print(array.size());
    }
}
于 2013-05-15T05:40:19.323 回答