У меня есть большая коллекция наборов, некоторые из которых являются подмножествами друг друга, например:
[{1, 2, 3, 4}, {1, 2}, {1, 5}, {1, 2, 3, 4, 5}, {2, 6}]
Я хотел бы взять эту коллекцию и вывести DAG частичного порядка отношений подмножества
{1, 2, 3, 4, 5} >= {1, 2, 3, 4} >= {1, 2}
{1, 2, 3, 4, 5} >= {1, 5}
{2, 6}
Есть ли способ сделать это, кроме как сравнивать все комбинации наборов (что недопустимо при большом количестве наборов). Это кажется близким к ряду проблем с обложками, но я не могу найти проблему, к которой это сводится.
Одна оптимизация заключается в создании инвертированного индекса, который поможет избежать сравнения наборов, не имеющих общего элемента, такого как {2, 6} и {1, 5}.
Эта проблема связана с топологической сортировкой и Линейные расширения частичного порядка.
Это почти дубликат Создать DAG из poset используя строго функциональное программирование, но я открыт для решения, которое не является чисто функциональным.
