Блог

Главная - Вопросы по программированию - Перекрывающиеся элементы в многобайловых наборах в python

Перекрывающиеся элементы в многобайловых наборах в python

#python-3.x #set

#python-3.x #набор

Вопрос:

Допустим, у меня есть 6 наборов:

 s1 = {"a", "b", "d"}
s2 = {"a", "b", "c"}
s3 = {"a", "c", "d"}
s4 = {"x", "y"}
s5 = {"x", "z"}
s6 = {"u"}

Я хочу получить все максимально перекрывающиеся элементы и все еще хочу знать, откуда они взялись. (например, в таком словаре, как этот)

 result = {"a": [s1, s2, s3], "x": [s4, s5], "u": [s6]}

Есть ли необычный способ решить эту проблему или мне нужно просмотреть все возможные комбинации и посчитать мои элементы?

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

Комментарии:

1. Почему ваш ожидаемый результат не отражает тот факт, что ‘b’ появляется в s1 и s2, а ‘d’ появляется в s1 и s3, а также тот факт, что ‘c’ появляется в s2, ‘y’ появляется в s4, а ‘z’ появляется в s5?

2. Потому что мне нужен только максимально перекрывающийся элемент. Итак, поскольку в s1, s2 и s3 есть «a», я не хочу понимать, что есть еще один перекрывающийся элемент, который встречается только в подмножестве из них.

Ответ №1:

Мое решение этой проблемы:

 def main():
    s1 = frozenset({"a", "b", "d"})
    s2 = frozenset({"a", "b", "c"})
    s3 = frozenset({"a", "c", "d"})
    s4 = frozenset({"x", "y"})
    s5 = frozenset({"x", "z"})
    s6 = frozenset({"u"})

    sets = {s1, s2, s3, s4, s5, s6}

    print(select_keyqueries(sets))


def select_keyqueries(docs):
    kqs = set(doc for subset in docs for doc in subset)
    # one should probably use OrderedDicts
    ms = dict(sorted({kq: set(s for s in docs if kq in s) for kq in kqs}.items(), key=lambda t: len(t[1]), reverse=True))
    
    return greedy(ms, docs)


def greedy(ms, docs):
    found_docs = set()
    solution = dict()
    for kq, kq_docs in ms.items():
        if not kq_docs.issubset(found_docs):
            solution[kq] = kq_docs
            found_docs.update(kq_docs)
            if found_docs == docs:
                break
    return solution

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

Но, пожалуйста, не стесняйтесь сообщать мне, есть ли более простое решение или более эффективное.