Найти суперпоследовательность заданных упорядоченных подпоследовательностей в Java ⇐ JAVA

[Anonymous]

Я столкнулся с этой проблемой в несвязанной программе, которую пишу, и потратил немало часов, пытаясь ее решить, потому что думал, что это будет весело. Это было, но я не смог сделать это полностью. Мой код решает последовательность только некоторых подмножеств. Эта проблема также напоминает общую математическую задачу, которую, вероятно, решали самыми разными способами на протяжении десятилетий, но мне не хватает математических навыков и терминологии, чтобы найти решение или вообще что-либо об этой конкретной проблеме в Интернете.

У меня есть набор подпоследовательностей, которые, как я знаю, являются частью более крупной, неизвестной (супер?)последовательности. Я не думаю, что эти подпоследовательности являются наборами в математическом смысле, поскольку они упорядочены, но они похожи тем, что не содержат повторяющихся элементов. То же самое касается мастера/супер/whateversequence. (Для ясности я буду называть это суперпоследовательностью.)

Все подпоследовательности содержат данные одного и того же типа, однако данные упорядочены не по алфавиту, а по возрастанию. , или что-то в этом роде. В некотором смысле данные находятся в произвольном порядке: в порядке суперпоследовательности. И это то, что меня интересует. Я хочу найти неизвестную суперпоследовательность этих подпоследовательностей.

Для простоты я попытался решить эту задачу с помощью букв алфавита, но позже я смогу реорганизовать код в соответствии со своими потребностями. Очевидно, поскольку я все еще пытаюсь решить эту проблему, я начал с того, что придумал подходящее слово для обозначения суперпоследовательности, не содержащее повторяющихся элементов: БЛОК-СХЕМЫ.

Затем я придумал следующие шесть подпоследовательностей:

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 orderSequence(final Set unorderedSequence, final LinkedHashMappedKeyValueList ruleMap)
{
List orderedSequence = new ArrayList(unorderedSequence);

// Order the sequence according to the rules.
System.out.println("---- ORDERING SEQUENCE ----");

for (Map.Entry rule : ruleMap.entrySet())
{
char currentChar = rule.getKey();
LinkedHashSet ruleChars = rule.getValue();

System.out.println("Processing rule " + currentChar + "

Подробнее здесь: https://stackoverflow.com/questions/337 ... es-in-java