如何返回字符串ArrayList的所有排列

Question

我正在尝试编写一个返回一个ArrayList<ArrayList<String>>包含较小ArrayLists的大型方法的方法,每个ArrayLists都有一个不同的起始ArrayList排列.

这是我的方法:

public static ArrayList<ArrayList<String>> permute(ArrayList<String> x) {

    ArrayList<ArrayList<String>> res = new ArrayList<ArrayList<String>>();

    while (res.size() < fac(x.size())) {  //fac method works fine

        Collections.shuffle(x);

        if (!res.containsAll(x)) {
            res.add(x);
        }

    }

    return res;
}

我的方法是基本上重新调整原始的ArrayList,x,并检查它是否已经在结果ArrayList中,如果不是,那么我添加它.出于某种原因,当我尝试这个方法时,结果ArrayList包含相同的ArrayLists,即使我有一个if语句,这是特定的,所以不会发生.

我错过了什么？

Answer 1

您的算法有三个问题:

1. 您正在重新洗牌并一次又一次地添加相同的列表.尝试x = new ArrayList(x)在循环中添加某个地方.
2. 正如Manos所指出的,你必须使用contains,而不是containsAll; 否则,你正在检查所有元素是否内新洗牌数组列表包含,这是从来没有的情况下,所以你再次添加相同的列表.
3. 你的算法非常可怕,速度非常慢.一旦你已经解决了上述两个问题,那么算法就可以完成工作,获得最后一个排列的概率将是1/n!(对于n元素),所以这将花费非常非常长的时间.