Алгоритм генерации последовательностей на основе ограниченной информации

Question

Предположим, что у нас есть набор букв, например. {A, B, C, D, E, F}, которые мы хотим упорядочить последовательно, ограниченные набором правил.

Мы не знаем, как выглядит последовательность, но мы знаем, какие буквы находятся в последовательности. И у нас есть информация о заказе пар букв. Существуют ли какие-либо известные алгоритмы или методы, которые найдут возможные последовательности, которые удовлетворяют данной информации?

Например, предположим, что мы имеем следующую информацию:

• Есть 6 букв {A, B, C, D, E, F} в последовательности
• E приходит после того, как B
• С приходит после того, как Е
• приходит после того, как D
• F приходит после B
• D приходит после Е

Каковы возможные последовательности, которые удовлетворяют этим критериям?

Answer 1

Эта проблема может быть решена с помощью depth-first search (DFS).

В вашем примере начальное состояние проблемы

------ abcdef 
BE 
EC 
DA 
BF 
ED 

который должен сказать, что письма не были добавлены к последовательности, остальные буквы, доступные abcdef, а остальные правила "B должны быть представлены до E " и т. д.

Ни одна из букв с правой стороны правила не может быть выбрана в качестве следующей буквы. Поэтому B является единственным выбором для первой буквы. Новое состояние проблемы является

B----- acdef 
EC 
DA 
ED 

правила, относящееся к B было удовлетворено, и не служит никакой иной цели. Вторая буква должна быть E или F, так как ACD отображаются в правой части правила. Предполагая, что ДФС исследует E первое, новое состояние

BE---- acdf 
DA 

Допустимые варианты CDF поскольку A все еще находится на правой части правила. Выберите C

BEC--- adf 
DA 

Допустимые варианты DF. Выберите D

BECD-- af 

Выберите A, затем F и последовательность завершения

BECDAF 

После достижения решения, ДФС должны вернуться и изучить другие варианты. Например, выбирая F вместо E в качестве второй буквы.

Answer 2

построить Ориентированный граф G (V, E)
V = {a,b,c,d,e} ваших писем
E = (x,y) for any pair where x comes before y.

затем использовать топологическую сортировку (read more here) (visualization here)