GetLists(tasks[1..m], depends[1..m])
1. topological_sort(tasks)
2. cumulative = set()
3. lists = queue()
4. i = 0
5. while |cumulative| != m do
6. temp = set()
7. while depends[i] is a subset of cumulative do
8. temp = temp union {tasks[i]}
9. i = i + 1
10. cumulative = cumulative union temp
11. lists.enqueue(temp)
Нечто подобное может сработать. Обратите внимание, что lynchpin выполняет «топологическую сортировку», чтобы обеспечить получение завершения. Также обратите внимание, что, как есть, этот алгоритм корректен только для набора входов с допустимым решением. Если решения не существует, это циклы навсегда. Легко исправить, но вы можете справиться с этим.
Пример: A ни от чего не зависит, B и C зависят от A, E зависит от A и C, а D зависит от C и B.
Topological sort: A, B, C, D, E.
cumulative = {}
lists = []
i = 0
|cumulative| = 0 < 5 so...
temp = {}
depends[A] = {} is a subset of {} so
temp = {A}
i = 1
depends[B] = {A} is not a subset of {}, so break
cumulative = {A}
lists = [{A}]
|cumulative| = 1 < 5 so...
temp = {}
depends[B] = {A} is a subset of {A}, so
temp = {B}
i = 2
depends[C] = {A} is a subset of {A}, so
...
Вы поняли.