java - 递归列出 Integer Arraylist 中的所有排列组合

Question

我有一个方法 perm1 打印字符串中字符的所有排列/组合

// print permutation / combination 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 {
        System.out.println(prefix);
        for (int i = 0; i < N; i++)
           perm1(prefix + s.charAt(i), s.substring(0, i) + s.substring(i+1, N));
    }
}

perm1 工作正常并产生所需的输出。

我正在尝试创建一个类似的方法perm2，它适用于整数数组列表

public static void perm2(ArrayList<Integer> a) {
    ArrayList<Integer> sub = new ArrayList<Integer>(); 
    perm2(sub, a);
}
public static void perm2(ArrayList<Integer> sub, ArrayList<Integer> a){
    int L = a.size();
    if (L==0) System.out.println(sub);
    else {
        System.out.println(sub);
        for (int i = 0; i < L; i++){
            sub.add(a.get(i));
            a.remove(i);
            perm2(sub, a);
            L = a.size(); // to avoid Index out of bounds exception
        }           
    }
}

这并没有像我希望的那样生成所有的排列和组合。使用数组列表 [1, 2, 3]，它只打印以下内容:

[]
[1]
[1, 2]
[1, 2, 3]

谁能告诉我如何修改 perm2 以便它打印其他预期值，如 [2] [3] [2, 3] [3, 2] [2, 3, 1] [2, 1, 3] 等...

Answer 1

我强烈建议查看 Google 的 Guava 包:

http://docs.guava-libraries.googlecode.com/git/javadoc/com/google/common/collect/Collections2.html

这个包有非常有用的方法“permutations(Collection elements)”

此包还包含“Sets”类中的方法“powerSet(Set set)”。 http://docs.guava-libraries.googlecode.com/git/javadoc/com/google/common/collect/Sets.html

对 powerSet(Set) 和 permutations(Collection) 的嵌套调用应该会让事情变得非常简单。