将子集组合成更大的集合

Question

好吧，我对这个非常迷恋。我需要一个执行以下操作的函数。

接受列表的列表。

input = [['A'], ['A', 'B'], ['A', 'B', 'C'], ['A', 'B'], ['X', 'Y'], ['A', 'B', 'C'], ['X'], ['A'], ['X', 'A', 'B']

然后将列表缩减为超集，同时记录转入超集的子集数量。它将继续这样做，直到无法制作更多的超级集为止。

规则是子集中项目的顺序必须保持有序，并且必须在较大的超集中按顺序匹配。因此，对于这个输入，它将减少为字典形式：

output = {['A', 'B', 'C'] : 6, ['X', 'Y'] : 2, ['X', 'A', 'B'] : 5}.

基本上，超集会计算自身、自身的重复项以及它包含的所有子集，所以......

['A', 'B', 'C'] = 6 (['A', 'B', 'C']*2 + ['A', 'B']*2 + ['A']*2),  ['X', 'Y'] = 3 (['X', 'Y']*1 + ['X']*1),  ['X', 'A', 'B'] = 3 (['X', 'A', 'B']*1 + ['A', 'B']*2 + ['X']*1 + ['A']*1)

已汇总的子集不应成为最终输出的一部分。一旦它们被卷起来，它们基本上就被破坏了。上面的示例是硬编码的，而我的实际数据集包含 1000 个子集。

这个问题快要了我的命，所以如果你能开发这个功能，那将非常有帮助。很高兴向第一个正确的人发送一些 BTC（不多，但表示感谢）。

我已经尝试过一百万个组合，并且可以思考如何继续。 GPT 也出现重大失败。

Answer 1

假设我关于决定超集的规则是有效的，下面是完成大部分工作的代码：

master = [['A'], ['A', 'B'], ['A', 'B', 'C'], ['A', 'B'], ['X', 'Y'], ['A', 'B', 'C'], ['X'], ['A'], ['X', 'A', 'B']]

# Make them tuples so they can be keys.
master = list(map(tuple,master))
mlen = max(len(s) for s in master)
supers = {s:[] for s in master if len(s)==mlen}

def is_subset(sub,sup):
    return all(t in sup for t in sub)

for s in master:
    for t,v in supers.items():
        if is_subset(s,t):
            v.append(s)

from pprint import pprint
pprint(supers)

输出：

{('A', 'B', 'C'): [('A',),
                   ('A', 'B'),
                   ('A', 'B', 'C'),
                   ('A', 'B'),
                   ('A', 'B', 'C'),
                   ('A',)],
 ('X', 'A', 'B'): [('A',),
                   ('A', 'B'),
                   ('A', 'B'),
                   ('X',),
                   ('A',),
                   ('X', 'A', 'B')]}