java - 在 Java 中查找给定有序子序列的超序列

Question

我在我正在编写的一个不相关的程序中遇到了这个问题，我花了好几个小时试图解决它，因为我认为它会很有趣。是的，但我无法一路做到。我的代码只解决了一些子集的序列。这个问题也感觉像是一个一般的数学问题，几十年来可能已经以多种方式解决了，但我缺乏数学技能和术语来找到解决方案或在线找到关于这个特定问题的任何信息。

我有一组子序列，我知道它们是更大的未知( super ？)序列的一部分。我不认为这些子序列是数学意义上的集合，因为它们是有序的但它们的相似之处在于它们不包含重复元素。 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，它非常接近但并不完美。我还需要多次运行我的订购方法，所以我想出的“算法”也不完美。 “规则映射”是一个 HashMap ，其中键是另一个字符对象的 HashMap ，它位于子序列(因此在超序列中)中的键字符之后。

有没有我可以使用的某种 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

Answer 1

您要的是根据部分订单计算总订单。我找不到太多这方面的工作。不过我们可以在这里稍微讨论一下这个问题。

考虑 A<B<C<D .如果我们有序列 A<C , B<D和 C<D ，我们将永远无法计算总订单。我们只得到A<C<D和 B<D .

我认为可以证明我们将需要所有 N-1形式关系X<Y与 X和 Y连续出现在最后的链中以重建总顺序(可能有额外的，但那些是额外的信息)。作为一个非严格的演示，假设我们有 A1<A2<A3<...<AN并假设我们能够从部分订单中重建 A_begin至 A_end .现在为了将其放入总顺序中的正确位置，我们需要知道 A_(begin-1)<A_begin .没有其他关系可以让它适应总秩序。继续向下进入 A_begin..A_end我们应该能够通过某种归纳/无限下降表明我们需要单词的连续字符给出的所有关系才能重建它。

上面这组序列缺失的信息是F<L和 C<H .可以得到的序列是W->C->R->T->S , F->O->W->H->A->R->T->S和 L->O->W->H->A->R->T->S .计算余数需要更多信息。

在上述情况下，经过分解和去重后，我们有以下关系:

A,R
A,S <-- redundant since R<S and A<R
C,R
C,S <-- redundant since R<S and A<R
F,O 
F,W <-- redundant since O<W and F<O
H,A
L,H <-- redundant since O<H and L<O
L,O
O,H <-- redundant since O<W and W<H
O,W
R,S <-- redundant since T<S and R<T
R,T
T,S
W,C
W,H

有 16 个关系，其中 6 个是直接冗余的。删除冗余我们得到以下 10 个关系:

A,R <-- consecutive letters in actual word
C,R
F,O 
H,A <-- consecutive letters in actual word
L,O <-- consecutive letters in actual word
O,W <-- consecutive letters in actual word
R,T <-- consecutive letters in actual word
T,S <-- consecutive letters in actual word
W,C <-- consecutive letters in actual word
W,H 

原始序列中唯一缺少的是 F<L和 C<H .附加给定关系 C<R , F<O和 W,H重复了 LHS 或 RHS 并给出了不可操作的信息(基本上这些连接了两个部分有序的链但不在端点，所以你知道一个链要合并或小于另一个但不知道在哪里)。

添加缺失的关系后，有多种方法可以实现这一点。您的代码可能自行运行。