Эффективный алгоритм группировки кортежей переменной длины

Question

Я пытаюсь разработать эффективный алгоритм группировки последовательности кортежей целых чисел любой длины, например:

[(), (1,), (1,1), (1,2), (2,), (2,1,1), (2,1,2), (2,2)]

Правило группировки, например, в Python, следующее:

def tupleSameGroup(tuple1, tuple2):
    sameGroup = True
    for index in range(min(len(tuple1), len(tuple2))):
        if tuple1[index] != tuple2[index]:
            sameGroup = False

    return sameGroup

Грубо говоря, если один кортеж является «подмножеством» другого совпадения с самого начала, это одна и та же группа.Пустой кортеж находится в той же группе, что и любой кортеж.

Основываясь на этом правиле, я хочу, чтобы мой алгоритм выводил список всех уникальных групп кортежей;Итак, список списка кортежей, где во внутреннем списке все кортежи находятся в одной группе, но между ними есть пара, которой нет.Для приведенного выше примера желаемый результат:

[[(), (1,), (1,1)],
 [(), (1,), (1,2)],
 [(), (2,), (2,1,1)],
 [(), (2,), (2,1,2)],
 [(), (2,), (2,2)]]

Любая помощь будет принята с благодарностью!Спасибо.

Answer 1

Вы можете сделать это в два этапа: во-первых, построить Trie или дерево префиксов из кортежей:

tuples = set([(), (1,), (1,1), (1,2), (2,), (2,1,1), (2,1,2), (2,2)])

tree = {}
for tpl in tuples:
    t = tree
    for x in tpl:
        t = t.setdefault(x, {})

В вашем примере tree будет {1: {1: {}, 2: {}}, 2: {1: {1: {}, 2: {}}, 2: {}}}

Затем добавьте DFS в дерево и добавляйте элементы в группы всякий раз, когда текущий кортеж (путь в дереве) находится в set (для более быстрого поиска) tuples.(Листья в дереве всегда являются допустимыми кортежами.)

def find_groups(tree, path):
    if len(tree) == 0:
        yield [path]
    for x in tree:
        for res in find_groups(tree[x], path + (x,)):
            yield [path] + res if path in tuples else res

Это дает:

[(), (1,), (1, 1)]
[(), (1,), (1, 2)]
[(), (2,), (2, 1, 1)]
[(), (2,), (2, 1, 2)]
[(), (2,), (2, 2)]

Сложность должна быть O (k), где k является суммой элементов во всехкортежей - общее количество промежуточных и листовых узлов в дереве.

Answer 2

Не самое эффективное решение, но оно даст желаемый результат и будет работать с увеличением максимальных размеров кортежей:

s = [(), (1,), (1,1), (1,2), (2,), (2,1,1), (2,1,2), (2,2)]

def tupleSameGroup(tuple1, tuple2, sameGroup=True):

    if any(tuple1[idx]!=tuple2[idx] for idx in range(len(tuple1))):
        return False
    return sameGroup

groups = [[i, j] for i in s for j in [x for x in s if len(x)>len(i)] if tupleSameGroup(i, j)]

Выход:

[[(), (1,)], [(), (1, 1)], [(), (1, 2)], [(), (2,)], [(), (2, 1, 1)], [(), (2, 1, 2)], [(), (2, 2)], [(1,), (1, 1)], [(1,), (1, 2)], [(2,), (2, 1, 1)], [(2,), (2, 1, 2)], [(2,), (2, 2)]]

Затем вы можете комбинировать этигруппировать вместе на основе общих элементов:

combined_groups = [sorted(list(set(i) | set(j))) for i in groups for j in groups if i[-1] in j and i!=j]

Выход:

[[(), (1,), (1, 1)], [(), (1,), (1, 2)], [(), (1,), (1, 1)], [(), (1,), (1, 2)], [(), (2,), (2, 1, 1)], [(), (2,), (2, 1, 2)], [(), (2,), (2, 2)], [(), (2,), (2, 1, 1)], [(), (2,), (2, 1, 2)], [(), (2,), (2, 2)], [(), (1,), (1, 1)], [(), (1,), (1, 2)], [(), (2,), (2, 1, 1)], [(), (2,), (2, 1, 2)], [(), (2,), (2, 2)]]

Наконец, мы можем создать новый список без дубликатов:

no_duplicates = []
for i in combined_groups:
    if i not in no_duplicates:
        no_duplicates.append(i)

Выход:

[[(), (1,), (1, 1)],
 [(), (1,), (1, 2)],
 [(), (2,), (2, 1, 1)],
 [(), (2,), (2, 1, 2)],
 [(), (2,), (2, 2)]]