Блог

Я думаю об алгоритме, который перестраивает последовательность выполняемых операций, в то время как каждая операция может зависеть от некоторых операций в этой последовательности.

Предположим, у нас есть несколько типов операций, например: A, B, C, ... . Последовательность операций должна быть такой [a_0, b_0, a_1, c_0, b_1, c_1, a_2, a_3, ...] , и зависимости заданы. Я хочу изменить их порядок, чтобы они соответствовали этим ограничениям:

1. Их зависимости сохраняются, т. е. операция должна быть выполнена после того, как зависящая от нее операция будет выполнена как в исходной последовательности, так и в переупорядоченной последовательности.
2. Все операторы одного и того же типа будут собраны вместе, т. е. упорядоченная последовательность будет такой [a_0, a_1, ..., b_0, b_1, ..., c_0, c_1, ...] .
3. (Необязательно) Каждый тип оператора отображается в том же порядке, что и в исходной последовательности, например, в [a_0, b_0, a_1, c_0, b_1, c_1, a_2, a_3, ...] и в переупорядоченной последовательности сначала появляется первый оператор типа A, затем появляется первый оператор типа B и, наконец, выполняется первый оператор типа C.

Не могли бы вы помочь мне придумать правильный алгоритм?