Java Recursion, вызывая его с помощью объектов - Как скопировать объекты?

Question

Старое значение / эталонные вещи.Я получаю ConcurrentModificationException для этой адаптации Bron-Kerbosch.

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, а не на реализацию - как правило, это хорошая практика, поскольку вы не раскрываете реализацию во всей кодовой базе.

Answer 2

Ваша первая проверка && избыточна, изначально проверка была с аргументом X?

Кроме того, ваш цикл for в начале блока else не имеет никакого смысла, что вы пытаетесь делать там? Дело в том, что вы используете счетчик (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. Я думаю, что вы пытаетесь сделать первый случай.

Answer 3

ArrayList newP = P;

Это создает только вторую ссылку на тот же ArrayList.Чтобы скопировать массив, используйте

ArrayList newP = new ArrayList (P);