java - 如何合并列表，保留每个人的顺序？

Question

我有几个列表，它们都有自己的顺序。这些列表通常共享相似/相等的子范围。有些列表多次包含一个项目。

B,C,D   // a list
A,B,E   // another list
A,B,A,D // a list, which contains A twice
F,G     // a list, which does not overlap with any other range

为了显示这些项目，我必须将它们全部合并在一起。但是，必须严格遵守每个列表中的顺序。简短的结果是首选:

A,B,A,C,D,E,F,G         // a valid, good result
A,B,E,A,C,D,F,G         // another valid, good result
A,B,E,F,G,C,A,D         // yet another valid result
B,C,D,A,B,E,A,B,A,D,F,G // a valid, but long (=bad) result
A,B,C,D,E,F,G           // not a valid answer, because the third input list had a B before an A

如何在 Java 中找到一个好的、有效的结果列表？

如果结果列表可以通过删除项目转换为任何输入列表，则它是有效的。

首选简短的结果列表。

Answer 1

此逻辑将合并元素，并可能缩短结果:

List<String> result = new ArrayList<>();
for (List<String> list : listOfLists) {
  int startingPos = 0;
  for (String str : list) {
    int pos = result.subList(startingPos, result.size()).indexOf(str);
    if (pos < 0) {
      // Not found at or after startingPos. Add to the end.
      result.add(str);
      startingPos = result.size();
    } else {
      // Already in the list; just update the starting pos for next element.
      startingPos += pos + 1;
    }
  }
}

至于如何以“最佳”顺序添加它们——不知道什么好方法；但假设列表的数量很少，您可以尝试每个排列并选择最短的排列。