变长元组分组的有效算法

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

不是最有效的解决方案，但这将产生所需的输出，并可用于增加最大元组大小：

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)]]

Answer 2

您可以通过两个步骤完成此操作：首先，构建元组的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: {}}}

然后，只要当前元组（树中的路径）在set（为了更快地查找）的tuples中，DFS就会进入树并向组添加元素。（树中的叶子始终是有效的元组。）

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是所有元组中元素的总和，即树中中间节点和叶节点的总数。你知道吗