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

Question

旧的价值/参考事物.我为Bron-Kerbosch的改编获得了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;
}

异常发生在(Integer v:newP)的行,以及那里的递归调用.我需要P.removeAll(邻居[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而不是实现 - 通常是很好的做法,因为您没有在整个代码库中公开实现.