Итерация по списку в Java

Проблема заключается в следующем:

Напишите подмножества статических методов, которые используют рекурсивный поиск с возвратом для поиска всех возможных подсписков заданного списка. Подсписок списка L содержит 0 или более элементов L. Ваш метод должен принимать список строк в качестве своего параметра и печатать каждый подсписок, который может быть создан из элементов этого списка, по одному в строке. Например, предположим, что переменная с именем list хранит следующие элементы:

[Janet, Robert, Morgan, Char]

Вызов подмножеств(списка); выдаст следующий вывод:

[Janet, Robert, Morgan, Char]
[Janet, Robert, Morgan]
[Janet, Robert, Char]
[Janet, Robert]
[Janet, Morgan, Char]
[Janet, Morgan]
[Janet, Char]
[Janet]
[Robert, Morgan, Char]
[Robert, Morgan]
[Robert, Char]
[Robert]
[Morgan, Char]
[Morgan]
[Char]
[]

Часть моего решения требует использования рекурсивного возврата:

ListIterator<String> itr = choices.listIterator();
      while (itr.hasNext()) {
         String word = itr.next();
         chosen.add(word);
         itr.remove();
         subsets(choices, chosen, alreadyPrinted);
         chosen.remove(word);
         itr.add(word);
      }

Но я получаю исключение ConcurrentModificationException в строке с itr.add(word). Почему? Я думал, что весь смысл ListIterator в том, чтобы избежать этой проблемы?

РЕДАКТИРОВАТЬ: я также пытался решить это следующим образом:

for (String word : choices) {
         List<String> choicesCopy = choices;
         chosen.add(word);
         choicesCopy.remove(word);
         subsets(choicesCopy, chosen, alreadyPrinted);
      }

Я все еще получаю исключение concurrentmodification.... : ( Как это происходит? Исходный список вообще не модифицируется...


java listiterator
person user658168    schedule 27.05.2011    source источник

Ответы (4)


arrow_upward
2
arrow_downward

Не совсем, проблема (скорее всего) в том, что вы создаете ListIterator() каждый раз, когда выполняете рекурсию. Каждый итератор списка пытается изменить один и тот же базовый список слов, что вызывает исключение. Это не разрешено.

Решение состоит в том, чтобы предоставлять копию списка слов каждый раз, когда вы выполняете рекурсию. Таким образом, каждый итератор списка будет работать со своим личным списком.

person Jérôme Verstrynge    schedule 27.05.2011
comment
Итак, я ДОЛЖЕН использовать итератор? - person user658168; 27.05.2011
comment
Вы МОЖЕТЕ, но не обязаны. Проблема в том, что вы не должны использовать два итератора списка и выполнять изменения в одном и том же списке одновременно. - person Jérôme Verstrynge; 27.05.2011

arrow_upward
0
arrow_downward

вы создаете новый итератор при каждом вызове рекурсии, а затем удаляете/добавляете его. Когда вы идете вверх по стеку, старый итератор обнаруживает изменение и создает исключение.

Вы должны переосмыслить этот код.

person Alex Gitelman    schedule 27.05.2011

arrow_upward
0
arrow_downward

РЕДАКТИРОВАТЬ: я пропустил, что OP использовал ListIterator.

Причина ConcurrentModificationException заключается в том, что вы изменение базового списка путем добавления и удаления элементов из него во время его повторения. Я считаю, что вам придется использовать более примитивную технику итерации, такую ​​как традиционный цикл for, и самостоятельно отслеживать значение итерации.

Из приведенной выше ссылки:

если поток изменяет коллекцию напрямую, когда он перебирает коллекцию с отказоустойчивым итератором, итератор выдаст это исключение

Вот еще одна небольшая статья на эту тему.

person Casey    schedule 27.05.2011
comment
Это неверно, Iterator.add() и Iterator.remove() указаны явно, чтобы разрешить изменение во время итерации. Эти методы не вызывают это исключение, если у вас нет нескольких активных итераторов в одной и той же коллекции одновременно. - person verdesmarald; 27.05.2011
comment
Ах да вы правы. По какой-то причине я полностью перечитал ListIterator. - person Casey; 27.05.2011
comment
Итак, я ДОЛЖЕН использовать итератор? - person user658168; 27.05.2011

arrow_upward
0
arrow_downward

В вашем втором решении есть простая ошибка.

List<String> choicesCopy = choices;

Это не создает копию списка. Вы можете использовать ArrayList.clone() или LinkedList.clone() или создать новый список, подобный этому

List<String> choicesCopy = new LinkedList<String>(choices);
person donaldh    schedule 27.05.2011