java - 如何在 Java 中排列通用列表？

Question

我正在尝试编写一个函数来排列通用列表，但是发生了一些非常奇怪的事情。如果我用数组替换所有列表，则以下代码结构有效，但因为它是代码，所以代码只是打印出 [1, 2, 3] 六次。为什么是这样？我认为这与按值传递和按引用传递有关。

//Main.java
import java.util.ArrayList;
import java.util.Set;
import java.util.List;

public class Main {

    public static void main (String ... args) {
        ArrayList<Integer> AL = new ArrayList<Integer>();
        AL.add(1);
        AL.add(2);
        AL.add(3);

        Permute<Integer> perm = new Permute<Integer>();
        Set<List<Integer>> set = perm.listPermutations(AL);

        for (List<Integer> lst : set) {
            System.out.println(lst);
        }
    }
}

//Permute.java
import java.util.List;
import java.util.Set;
import java.util.HashSet;

public class Permute<E> {

    public Set<List<E>> listPermutations(List<E> lst) {
        Set<List<E>> perms = new HashSet<List<E>>();
        permute(lst, 0, perms);
        return perms;
    }

    private void permute(List<E> lst, int start, Set<List<E>> perms) {
        if (start >= lst.size()) {
            // nothing left to permute 
            perms.add(lst);
        }

        for (int i = start; i < lst.size(); i++) {
            // swap elements at locations start and i
            swap(lst, start, i);
            permute(lst, start + 1, perms);
            swap(lst, start, i);
        }
    }

    private void swap(List<E> lst, int x, int y) {
        E temp = lst.get(x);
        lst.set(x, lst.get(y));
        lst.set(y, temp);
    }
}

Answer 1

当您调用permute时，您永远不会创建新的List。 lst 是对 List 的引用，该引用会传递给所有递归调用，结果是您将相同的引用添加到集合中 6 次。通常，向集合添加相同的引用 6 次意味着您的 Set 将仅包含一个元素。

它看起来有六个元素的原因是因为您在将 List 添加到哈希后修改了它的内容，而您永远不应该对 HashMap 或 HashSet 执行此操作。如果您添加对 HashMap 或 HashSet 的对象引用，然后以更改哈希代码的方式修改该对象，则会搞砸哈希的工作。

因此，不知何故，相同的引用被使用六个不同的哈希码添加到集合中六次。但它们仍然都是对同一个 List 的引用，这意味着当您打印它们时，它们看起来都是一样的。

在递归调用permute之前，您需要复制List。如果permute可以知道List是一个ArrayList，你可以这样说

List<E> newList = new ArrayList<>(lst);

然后使用 newList 执行第一次交换，然后将 newList 传递给递归调用。 (可能不再需要第二个交换。)

如果您想创建一个与源列表类型相同的 newList ...我不确定除了使用反射之外是否有一种简单的方法可以做到这一点。