1

问题如下：

编写一个静态方法子集，该方法使用递归回溯来查找给定列表的每个可能的子列表。列表 L 的子列表包含 L 的 0 个或多个元素。您的方法应该接受一个字符串列表作为其参数，并打印可以从该列表的元素创建的每个子列表，每行一个。例如，假设一个名为 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);
      }

但是我在具有 itr.add(word) 的行上得到了 ConcurrentModificationException。为什么？我认为 ListIterator 的重点是避免这个问题？

编辑：我也尝试像这样解决它：

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

我仍然得到一个并发修改异常...... :(这是怎么回事？根本没有修改原始列表......

4

4 回答 4

2

不完全是，问题（很可能）是您ListIterator()每次递归时创建的。每个 List Iterator 都试图修改相同的底层单词列表，这会触发异常。这是不允许的。

解决方案是在每次递归时提供单词列表的副本。像这样，每个列表迭代器都将在自己的个人列表上工作。

于 2011-05-27T00:59:44.727 回答
0

编辑：我错过了 OP 正在使用ListIterator.

的原因ConcurrentModificationException是您正在通过在迭代它时添加和删除元素来修改基础列表。我相信您将不得不使用更原始的迭代技术，例如传统for循环并自己跟踪迭代值。

从上面的链接：

如果线程在使用快速失败迭代器迭代集合时直接修改集合，则迭代器将抛出此异常

这是另一篇关于它的快速文章。

于 2011-05-27T01:01:19.787 回答
0

您在每个递归调用上创建新的迭代器，然后使用它删除/添加。当您上堆栈时，旧迭代器会检测到更改并产生异常。

你应该重新考虑这段代码。

于 2011-05-27T01:02:58.243 回答
0

您的第二个解决方案有一个简单的错误。

List<String> choicesCopy = choices;

这不会创建列表的副本。您可以使用 ArrayList.clone() 或 LinkedList.clone() 或像这样创建一个新列表

List<String> choicesCopy = new LinkedList<String>(choices);
于 2011-05-27T02:35:16.817 回答