Сравнение трех (или более) словарей и поиск соответствия, если хотя бы два равны

Question

Я столкнулся с проблемой, аналогичной этой .Тем не менее, этот вопрос так строго сосредоточен на трех переменных.Я ищу решение, которое бы работало более чем на три.

Вот мой код для двух переменных:

for track_a in collection_a:
    for track_b in collection_b:

        t1 = track_a["tempo"]
        t2 = track_b["tempo"]
        k1 = track_a["key"]
        k2 = track_b["key"]
        m1 = track_a["mode"]
        m2 = track_b["mode"]

        if (t1 == t2) and (k1 == k2) and (m1 == m2):
            collection_c.append((track_a, track_b))

Вот мое решение для трех переменных:

for track_a in collection_a:
    for track_b in collection_b:
        for track_c in collection_c:

            t1 = track_a["tempo"]
            t2 = track_b["tempo"]
            t3 = track_c["tempo"]
            k1 = track_a["key"]
            k2 = track_b["key"]
            k3 = track_c["key"]
            m1 = track_a["mode"]
            m2 = track_b["mode"]
            m3 = track_c["mode"]

            a = (t1 == t2) and (k1 == k2) and (m1 == m2)
            b = (t2 == t3) and (k2 == k3) and (m2 == m3)
            c = (t3 == t1) and (k3 == k1) and (m3 == m1)

            if a: collection_c.append((track_a, track_b))
            if b: collection_c.append((track_b, track_c))
            if c: collection_c.append((track_c, track_a))

Очевидно, что это решение не является масштабируемым и медленным.Учитывая тот факт, что мне придется проверять все из них, я сомневаюсь, что это когда-нибудь будет быстрым, так как нам придется перебирать все возможные комбинации, но могу ли я хотя бы сделать его масштабируемым?(Не менее 5).Также, если возможно, разрешите добавление дополнительных характеристик сравнения позже.

Answer 1

Эффективный подход, который решает проблему в линейное время, заключается в преобразовании dicts в фиксированные наборы кортежей со значением ключа (по ключам, которые используются для тестов на равенство), чтобы их можно было хэшировать и использовать в качестве ключей dict (подписей).сами по себе, и так, что вы можете просто использовать набор множеств для их группировки:

groups = {}
for track in collections: # collections is a combination of all the collections you have
    groups.setdefault(frozenset((k, track[k]) for k in ('tempo', 'key', 'mode')), set()).add(track['name'])

так, что:

[group for group in groups.values() if len(group) >= 3]

вернет вам список наборов имен 3дорожки, подписи которых идентичны.

Answer 2

Найдите что-то полезное в itertools, не уверен, что это именно то, что вам нужно:

from itertools import product, combinations

all_collections = [collection_a, collection_b, collection_c] # d, e, f, ...
for collections in combinations(all_collections, 2):         # Pick 2 (or any number) collections from all collections
    for tracks in product(*collections):                     # Cartesian product of collections or equivalent to for track1 in collection1: for track2 in collection2: ...
        if True:                                             # check if all tracks are matched
            print(*tracks)                                   # or append them to another collection

Answer 3

Вот логически масштабируемое решение, которое для n словарей, сравниваемых по m значениям, потребует времени n*m для оценки.

Обратите внимание, если три совпадения, я верну группу3. Достаточно просто взорвать это для всех подходящих пар.Но если вы сделаете это, то можете вернуть что-то размером n*n.Я показал вам, как выглядят оба.

def group_on(variables, *tracks):
    # Build a trie first.
    trie = {}
    for track in tracks:
        this_path = trie
        for variable in variables:
            value = track[variable]
            if value not in this_path:
                this_path[value] = {}
            this_path = this_path[value]
        if 'final' not in this_path:
            this_path['final'] = [track]
        else:
            this_path['final'].append(track)

    def find_groups(this_path, count):
        if 0 == count:
            if 1 < len(this_path['final']):
                yield this_path['final']
        else:
            for next_path in this_path.values():
                for group in find_groups(next_path, count-1):
                    yield group

    for group in find_groups(trie, len(variables)):
        yield group

def group_to_pairs(group):
    for i in range(len(group)-1):
        for j in range(i+1, len(group)):
            yield (group[i], group[j])

print('Efficient version')

for group in group_on(['tempo', 'key', 'mode'],
        {'track': 1, 'tempo': 1, 'key': 'A', 'mode': 'minor'},
        {'track': 2, 'tempo': 1, 'key': 'A', 'mode': 'major'},
        {'track': 3, 'tempo': 1, 'key': 'A', 'mode': 'minor'},
        {'track': 4, 'tempo': 1, 'key': 'A', 'mode': 'major'},
        {'track': 5, 'tempo': 1, 'key': 'A', 'mode': 'minor'},
        ):
    print(group)

print('Versus')

for group in group_on(['tempo', 'key', 'mode'],
        {'track': 1, 'tempo': 1, 'key': 'A', 'mode': 'minor'},
        {'track': 2, 'tempo': 1, 'key': 'A', 'mode': 'major'},
        {'track': 3, 'tempo': 1, 'key': 'A', 'mode': 'minor'},
        {'track': 4, 'tempo': 1, 'key': 'A', 'mode': 'major'},
        {'track': 5, 'tempo': 1, 'key': 'A', 'mode': 'minor'},
        ):
    for pair in group_to_pairs(group):
        print(pair)