我在正在编写的一个不相关的程序中遇到了这个问题，我花了好几个小时试图解决它，因为我认为它会很有趣。是的，但我一直无法做到。我的代码只解决了一些子集的序列。这个问题也感觉像是一个一般的数学问题，几十年来可能已经以多种方式解决了，但我缺乏数学技能和术语来找到解决方案，或者在网上找到关于这个特定问题的任何东西。
我有一组子序列，我知道它们是更大的未知（超级？）序列的一部分。我不认为这些子序列是数学意义上的集合，因为它们是有序的，但它们的相似之处在于它们不包含重复的元素。master/super/whateversequence 也是如此。（为了清楚起见，我将其称为超序列。）
子序列都包含相同类型的数据，但是数据不是按字母顺序、升序或类似顺序排列的。从某种意义上说，数据是任意顺序的：在超序列中。这就是我感兴趣的。我想找到这些子序列的未知超序列。
为了简单起见，我尝试使用字母来解决这个问题，但我可以稍后重构代码以满足我的需要。显然，因为我仍在尝试解决这个问题，所以我首先为不包含重复元素的超序列想出了一个合适的词：FLOWCHARTS。
然后我想出了以下六个子序列：
F,W,C,R
L,H,A
L,O,H,A,R,S
C,S
R,T,S
F,O,W,H,A,S
这是我的顺序排序方法：
// LinkedHashMappedKeyValueList keeps the data in the order it was inserted and allows one key to have multiple values.
private static LinkedHashSet<Character> orderSequence(final Set<Character> unorderedSequence, final LinkedHashMappedKeyValueList ruleMap)
{
List<Character> orderedSequence = new ArrayList<Character>(unorderedSequence);
// Order the sequence according to the rules.
System.out.println("---- ORDERING SEQUENCE ----");
for (Map.Entry<Character, LinkedHashSet<Character>> rule : ruleMap.entrySet())
{
char currentChar = rule.getKey();
LinkedHashSet<Character> ruleChars = rule.getValue();
System.out.println("Processing rule " + currentChar + "<" + ruleChars.toString());
if (orderedSequence.contains(currentChar))
{
int ruleCharIndex = -1;
int smallestRuleCharIndex = Integer.MAX_VALUE;
Iterator<Character> it = ruleChars.iterator();
// Find the rule character with the smallest index.
while (it.hasNext())
{
char ruleChar = it.next();
ruleCharIndex = orderedSequence.indexOf(ruleChar);
System.out.println("\tChecking for rule character: " + ruleChar + " (" + ruleCharIndex + ")");
if (ruleCharIndex > -1 && smallestRuleCharIndex > ruleCharIndex)
smallestRuleCharIndex = ruleCharIndex;
}
if (smallestRuleCharIndex != Integer.MAX_VALUE)
System.out.println("\tMoving '" + currentChar + "' before '"
+ orderedSequence.get(smallestRuleCharIndex) + "'.");
else
System.out.println("\tMoving '" + currentChar + "' to the end of the sequence.");
if (!moveBefore(orderedSequence.indexOf(currentChar), smallestRuleCharIndex, orderedSequence))
System.out.println("\tAlready in correct position.");
else
System.out.println("\tCurrent sequence: " + listToString(orderedSequence));
}
else
throw new ArithmeticException("Element of a subsequence not a part of the sequence.");
}
return new LinkedHashSet<Character>(orderedSequence);
}
最后，我的代码找到了F,L,O,W,H,C,A,R,T,S这些子序列的超序列，它非常接近但并不完美。我还需要多次运行我的排序方法，所以我想出的“算法”也不完美。“规则映射”是一个哈希映射，其中键是字符对象的另一个哈希映射，它位于子序列中的键 Character 之后（因此在超序列中）。
是否有某种我可以使用的 Java 库来进行这种序列查找？有人可以在告诉我这叫什么和/或帮助我找到适合这项工作的算法方面指出我正确的方向吗？
此外，我的程序的缩短控制台输出：
---- BUILDING RULE MAP ----
Subsequences: F,W,C,R
L,H,A
L,O,H,A,R,S
C,S
R,T,S
F,O,W,H,A,S
All subsequences processed. Number of ordering rules: 10
Rule map: (F<[W, O]),(W<[C, H]),(C<[R, S]),(R<[, S, T]),(L<[H, O]),(H<[A]),(A<[, R, S]),(O<[H, W]),(S<[]),(T<[S])
---- BUILDING UNORDERED SEQUENCE ----
Sequence size is 10.
Unordered sequence: F,W,C,R,L,H,A,O,S,T
---- ORDERING SEQUENCE ----
Processing rule F<[W, O]
Moving 'F' before 'W'.
Already in correct position.
Processing rule W<[C, H]
Moving 'W' before 'C'.
Already in correct position.
Processing rule C<[R, S]
Moving 'C' before 'R'.
Already in correct position.
Processing rule R<[, S, T]
Moving 'R' before 'S'.
Current sequence: F,W,C,L,H,A,O,R,S,T
Processing rule L<[H, O]
Moving 'L' before 'H'.
Already in correct position.
Processing rule H<[A]
Moving 'H' before 'A'.
Already in correct position.
Processing rule A<[, R, S]
Moving 'A' before 'R'.
Current sequence: F,W,C,L,H,O,A,R,S,T
Processing rule O<[H, W]
Moving 'O' before 'W'.
Current sequence: F,O,W,C,L,H,A,R,S,T
Processing rule S<[]
Moving 'S' to the end of the sequence.
Current sequence: F,O,W,C,L,H,A,R,T,S
Processing rule T<[S]
Moving 'T' before 'S'.
Already in correct position.
Previous sequence: F,W,C,R,L,H,A,O,S,T
Ordered sequence: F,O,W,C,L,H,A,R,T,S
Sequences match: false
---- ORDERING SEQUENCE ----
Processing rule F<[W, O]
Moving 'F' before 'O'.
Already in correct position.
Processing rule W<[C, H]
Moving 'W' before 'C'.
Already in correct position.
Processing rule C<[R, S]
Moving 'C' before 'R'.
Current sequence: F,O,W,L,H,A,C,R,T,S
Processing rule R<[, S, T]
Moving 'R' before 'T'.
Already in correct position.
Processing rule L<[H, O]
Moving 'L' before 'O'.
Current sequence: F,L,O,W,H,A,C,R,T,S
Processing rule H<[A]
Moving 'H' before 'A'.
Already in correct position.
Processing rule A<[, R, S]
Moving 'A' before 'R'.
Current sequence: F,L,O,W,H,C,A,R,T,S
Processing rule O<[H, W]
Moving 'O' before 'W'.
Already in correct position.
Processing rule S<[]
Moving 'S' to the end of the sequence.
Already in correct position.
Processing rule T<[S]
Moving 'T' before 'S'.
Already in correct position.
Previous sequence: F,O,W,C,L,H,A,R,T,S
Ordered sequence: F,L,O,W,H,C,A,R,T,S
Sequences match: false
---- ORDERING SEQUENCE ----
Processing rule F<[W, O]
Moving 'F' before 'O'.
Current sequence: L,F,O,W,H,C,A,R,T,S
Processing rule W<[C, H]
Moving 'W' before 'H'.
Already in correct position.
Processing rule C<[R, S]
Moving 'C' before 'R'.
Current sequence: L,F,O,W,H,A,C,R,T,S
Processing rule R<[, S, T]
Moving 'R' before 'T'.
Already in correct position.
Processing rule L<[H, O]
Moving 'L' before 'O'.
Current sequence: F,L,O,W,H,A,C,R,T,S
Processing rule H<[A]
Moving 'H' before 'A'.
Already in correct position.
Processing rule A<[, R, S]
Moving 'A' before 'R'.
Current sequence: F,L,O,W,H,C,A,R,T,S
Processing rule O<[H, W]
Moving 'O' before 'W'.
Already in correct position.
Processing rule S<[]
Moving 'S' to the end of the sequence.
Already in correct position.
Processing rule T<[S]
Moving 'T' before 'S'.
Already in correct position.
Previous sequence: F,L,O,W,H,C,A,R,T,S
Ordered sequence: F,L,O,W,H,C,A,R,T,S
Sequences match: true
Sequence ordered according to the limits of the rule map.
Sequence found after 2 tries.
Expected sequence: F,L,O,W,C,H,A,R,T,S FLOWCHARTS
Found sequence: F,L,O,W,H,C,A,R,T,S FLOWHCARTS
Sequences match: false
