Java递归，用对象调用它 - 如何复制对象？

Question

旧的价值/参考的东西。我收到 ConcurrentModificationException 对于布朗-克博什的改编。

public int[] bk(ArrayList<Integer> R, ArrayList<Integer> P, ArrayList<Integer> X) {
    int count[] = new int[n];
    int u=0, c = 0;

    ArrayList<Integer> tempPX = new ArrayList<Integer>();
    ArrayList<Integer> newP = P;
    ArrayList<Integer> newX = X;
    ArrayList<Integer> newR = R;

    if (P.isEmpty() && X.isEmpty()) {
        count[R.size()]++;
    } else {

        u = 0; c = 0; // find vertex with largest degree            
        tempPX.addAll(P); tempPX.addAll(X); // P ⋃ X
        for (Integer v : tempPX) {            
            if (neighbours[v].size() > neighbours[u].size()) {
                u = c; 
            }
            c++;
        } 

        P.removeAll(neighbours[u]); // P \ neighbours[u]
        for (Integer v : newP) {

            newR.add(v); // R ⋃ v

            newP.retainAll(neighbours[v]); // P â‹‚ neighbours[v]

            newX.retainAll(neighbours[v]); // X â‹‚ neighbours[v]

            bk(newR, newP, newX); 

            P.remove(v); // removing object
            X.add(v); // X ⋃ v
        }

    }

    return count;
}

异常发生在 for (Integer v : newP) 行以及其中的递归调用处。 我需要 P.removeAll(neighbours[u]);然后循环遍历结果列表，在注释中执行操作，并在递归调用中传递副本，这样它就不会抱怨，并且工作不会传递引用并继续修改同一对象 P/X/R 。那么我如何以及何时复制它们？这些第一行..我正在复制参考资料不是我... （是的，我知道我“修改”newP，然后循环旧的P，它们只是指向看起来相同的对象）

---阅读回复后的新代码-

   public int[] bk(List<Integer> r, List<Integer> p, List<Integer> x) {
    int count[] = new int[n];
    int u = 1;

    List<Integer> tempPX = new ArrayList<Integer>();
    List<Integer> newR, newP, newX;

    if (p.isEmpty() && x.isEmpty()) {
        count[r.size()]++;
    } else {

        // find vertex with largest degree in P U X        
        tempPX.addAll(p); 
        tempPX.addAll(x);
        for (Integer v : tempPX) {            
            if (neighbours[v].size() > neighbours[u].size()) {
                u = v; 
            }
        } 

        p.removeAll(neighbours[u]);  // P \ neighbours[u]
        newP = new ArrayList<Integer>(p); 
        for (Integer v : newP) {

            r.add(v); // R U  v
            newR = new ArrayList<Integer>(r);

            p.retainAll(neighbours[v]);  // P /\ neighbours[v]
            newP = new ArrayList<Integer>(p);

            x.retainAll(neighbours[v]); // X /\ neighbours[v]
            newX = new ArrayList<Integer>(x);

            bk(newR, newP, newX); 

            p.remove(v); // removing object
            x.add(v); // X U v
        }

    }

    return count;
}

Answer 1

正如您所确定的，您正在复制参考，而不是列表。您需要使用旧列表中的条目实例化一个新的 ArrayList 对象。

例如

List<Integer> newList = new ArrayList<Integer>(oldList);

，这显式地创建了一个包含对相同元素的引用的新对象。

请注意，我传递了对接口 List 的引用，而不是实现 - 通常是很好的做法，因为您不会在整个代码库中公开实现。

Answer 2

ArrayList newP = P;

这只会创建对同一 ArrayList 的第二个引用。要复制数组列表，请使用

ArrayList newP = new ArrayList(P);

Answer 3

你的第一个 &&检查是多余的，最初检查是与 X 参数一起进行的？

另外，您在 else 块开头的 for 循环没有任何意义，您想在那里做什么？问题是，您同时使用了计数器 (c) 和 tempPX 列表 (v) 的内容。您使用 v 进行检查，但使用 c 作为赋值。结果完全取决于数据排序，并且不会产生任何有意义的结果。

通常，您会使用其中之一，并在检查和作业中都使用它。

if (p.isEmpty() && p.isEmpty()) {
  count[r.size()]++;
} else {
  u = 0; c = 0; // find vertex with largest degree
  tempPX.addAll(p); tempPX.addAll(x); // P U X
  for (Integer v : tempPX) {
    if (neighbours[v].size() > neighbours[u].size()) {
      u = c; 
    }
    c++;
  }

您的目标要么是在 temppx 列表中找到具有最大数量邻居的索引（删除 c 变量和 c++ 行，在赋值中使用 v），要么只是找到具有最大邻居数量的索引对索引没有任何限制的邻居数量，在这种情况下，您将使用像这样的 for 循环：

for (int c = 0; c < neighbours.size(); ++c)

并删除任何提及 temppx 列表的内容。我的猜测是你试图做第一个案例。