0

我正在尝试编写一种方法，该方法返回一个ArrayList<ArrayList<String>>包含较小 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 包含相同的 ArrayList，即使我有一个专门的 if 语句，这样就不会发生这种情况。

我错过了什么？

4

2 回答 2

6

您的算法存在三个问题：

  1. 您正在重新洗牌并一次又一次地添加相同的列表。尝试x = new ArrayList(x)在循环中的某处添加。
  2. 正如 Manos 所指出的，您必须使用contains，而不是containsAll; 否则，您将检查是否包含新洗牌的数组列表中的所有元素，但事实并非如此，因此您将再次添加相同的列表。
  3. 你的算法非常非常慢。一旦你解决了上述两个问题，那么算法就会在原则上起作用，得到最后一个排列的概率将是1/n!（对于n元素），所以这将需要非常非常长的时间。
于 2015-09-07T18:43:35.207 回答
0

res.containsAll(x)

String如果x中类型的所有元素都存在于 中，这将是正确的res。但是 的元素res是ArrayList<String>。你可能想要：

res.contains(x)

ArrayList<String>如果 x存在于 res 中，这将是正确的。

于 2015-09-07T18:38:00.100 回答