Как найти несколько подмножеств одного надмножества в python?

Question

[NikitaRyabukhin]

существует алгоритмическая проблема. У меня есть несколько подмножеств одного супер множества (может быть n-е количество подмножеств, в зависимости от длины супер множества). Вот пример:

['/img0.jpg ']
['/img1.jpg']
['/img10.jpg']
['/img11.jpg' '/img9.jpg']
['/img12.jpg' '/img15.jpg']
['/img11.jpg' '/img13.jpg' '/img8.jpg' '/img9.jpg']
['/img14.jpg']
['/img15.jpg']
['/img16.jpg']
['/img14.jpg' '/img17.jpg']
['/img18.jpg']
['/img19.jpg' '/img22.jpg']
['/img2.jpg']
['/img19.jpg' '/img20.jpg' '/img21.jpg' '/img22.jpg']
['/img19.jpg' '/img21.jpg' '/img22.jpg']
['/img22.jpg']
['/img23.jpg']
['/img3.jpg']
['/img3.jpg' '/img4.jpg']
['/img0.jpg' '/img5.jpg']
['/img6.jpg']
['/img2.jpg' '/img7.jpg']
['/img11.jpg' '/img8.jpg' '/img9.jpg']
['/img9.jpg']

В результате должно получится наподобие:

['/img1.jpg']
['/img10.jpg']
['/img11.jpg' '/img13.jpg' '/img8.jpg' '/img9.jpg']
['/img12.jpg' '/img15.jpg']
['/img14.jpg' '/img17.jpg']
['/img16.jpg']
['/img18.jpg']
['/img19.jpg' '/img20.jpg' '/img21.jpg' '/img22.jpg']
['/img2.jpg' '/img7.jpg']
['/img23.jpg']
['/img3.jpg' '/img4.jpg']
['/img0.jpg' '/img5.jpg']
['/img6.jpg']

Проще говоря, задача сводится к нахождению супер множества, минуя все подмножества

Пожалуйста, скажите, каковы способы и идеи для написания алгоритма? Можно ли оптимально решить без множеств?

Comments

[Алан Гибизов]

Какой-то неочевидный алгоритм. Хорошо бы описать его словами. Без этого возможны недопонимания.

[Алан Гибизов]

Ну и тэг python тут ни при чем. Нет кода - нет тэга.

[Wataru]

NikitaRyabukhin Непонятна задача. Вам надо как-то минимизировать список множеств так, чтобы все заданные множества были подмножествами этих? Надо ли, чтобы каждое подмножество множества в ответе было во входном списке?

[Wataru]

NikitaRyabukhin, или задача выкинуть из списка те множества, которые целиком покрыты другими множествами в том же списке?

Почему, например, не подходит вариант ['/img0.jpg' '/img1.jpg' ... '/img23.jpg'] (все элементы в одном множестве)?

Answer 1

[Taulan Khatuaev]

для этой задачи можно использовать алгоритм пересечения множеств .

sets = [['/img0.jpg '],
        ['/img1.jpg'],
        ['/img10.jpg'],
        ['/img11.jpg', '/img9.jpg'],
        ['/img12.jpg', '/img15.jpg'],
        ['/img11.jpg', '/img13.jpg', '/img8.jpg', '/img9.jpg'],
        ['/img14.jpg'],
        ['/img15.jpg'],
        ['/img16.jpg'],
        ['/img14.jpg', '/img17.jpg'],
        ['/img18.jpg'],
        ['/img19.jpg', '/img22.jpg'],
        ['/img2.jpg'],
        ['/img19.jpg', '/img20.jpg', '/img21.jpg', '/img22.jpg'],
        ['/img19.jpg', '/img21.jpg', '/img22.jpg'],
        ['/img22.jpg'],
        ['/img23.jpg'],
        ['/img3.jpg'],
        ['/img3.jpg', '/img4.jpg'],
        ['/img0.jpg', '/img5.jpg'],
        ['/img6.jpg'],
        ['/img2.jpg', '/img7.jpg'],
        ['/img11.jpg', '/img8.jpg', '/img9.jpg'],
        ['/img9.jpg']]

super_set = set(sets[0]) # берем первое подмножество

# последовательно вычисляем пересечения супермножества с каждым из подмножеств
for s in sets[1:]:
    super_set = super_set.intersection(set(s))

# удаляем из супермножества все элементы, которые не принадлежат пересечению
for s in sets:
    super_set.difference_update(set(s) - super_set)

# оставшиеся элементы супермножества и будут искомым результатом
result = sorted(list(super_set))
print(result)