DICT列表，按列表键分组，无交叉点

Question

我需要帮助来优化我的代码

我有一个数据：

data = [
  {"ids": [1]},
  {"ids": [3, 4]},
  {"ids": [1, 2]},
  {"ids": [2]},
]

我需要按ID对其进行分组，而不交叉，因此预期数据应为：

expected = [
  [{"ids": [1]}, {"ids": [2]}],
  [{"ids": [3, 4]}, {"ids": [1, 2]}],
]  # only 2 sublist here

我要拆分的代码（未优化）：

import itertools as it

def _split(
    list_of_dicts,
):
    splitted_list_of_dicts = []
    sub_list = []
    while list_of_dicts:
        for dct in list_of_dicts:
            ids_in_sub_list = set(
                it.chain(*[sub_list_el["ids"] for sub_list_el in sub_list]),
            )
            if not set(dct["ids"]).intersection(ids_in_sub_list):
                sub_list.append(dct)
                list_of_dicts.remove(dct)
        splitted_list_of_dicts.append(sub_list)
        sub_list = []
    return splitted_list_of_dicts

我的代码的结果是：

result = [
    [{'ids': [1]}, {'ids': [2]}],
    [{'ids': [3, 4]}],
    [{'ids': [1, 2]}]
]  # 3 sublist

我又得到了一个列表，我试图对其进行优化。 如果你对如何帮助我有任何想法，我会很高兴的，谢谢你的时间

更多示例：

data = [
  {"ids": [1]},
  {"ids": [3, 4]},
  {"ids": [1, 2]},
  {"ids": [4]},
  {"ids": [3]},
  {"ids": [2]},
]

可分组为两个元素列表：

expected = [
    [{'ids': [1]}, {'ids': [4]}, {'ids': [2]}, {'ids': [3]}],
    [{'ids': [3, 4]}, {'ids': [1, 2]}],
]

但现在我得到了全部4：

result = [
    [{'ids': [1]}, {'ids': [4]}, {'ids': [2]}],
    [{'ids': [3, 4]}],
    [{'ids': [1, 2]}],
    [{'ids': [3]}]
]

Answer 1

如果任何不包含重复项的组合都是可以接受的，那么您可以简单地迭代data列表，并将当前元素附加到结果中不存在任何ID的第一个元素

def split(list_of_dicts):
    result_helper = [set()] # This will be a list of sets for easy membership checks
    result_list = [[]] # This will be what we return
    for d in list_of_dicts:
        for s, l, in zip(result_helper, result_list):
            if not any(x in s for x in d["ids"]):
                s.update(d["ids"])
                l.append(d)
                break
        else:
            # for loop ended without being broken
            # This means no elements of result_list took this dict item. 
            # So create a new element
            result_list.append([d])
            result_helper.append(set(d["ids"]))
    return result_list

用你的原始数据

data = [
  {"ids": [1]},
  {"ids": [3, 4]},
  {"ids": [1, 2]},
  {"ids": [2]},
]
split(data)

我们得到的结果是：

 [
    [{'ids': [1]}, {'ids': [3, 4]}, {'ids': [2]}],
    [{'ids': [1, 2]}]
 ]

这似乎是一个可接受的解决方案，因为所有列表都没有重复的id

第二个例子是：

data = [
  {"ids": [1]},
  {"ids": [3, 4]},
  {"ids": [1, 2]},
  {"ids": [4]},
  {"ids": [3]},
  {"ids": [2]},
]
split(data)

这将提供以下输出：

 [
    [{'ids': [1]}, {'ids': [3, 4]}, {'ids': [2]}],
    [{'ids': [1, 2]}, {'ids': [4]}, {'ids': [3]}]
 ]

在这种情况下也没有重复

Answer 2

从您的问题中我可以看出，您基本上是根据每个组的基数对ID进行排序

from itertools import groupby


def transform(data):
    cardinality = lambda x: len(x['ids'])
    sorted_data = sorted(data, key=cardinality)
    return [list(group) for _, group in groupby(sorted_data, key=cardinality)]

给予：

[
    [
        {'ids': [1]},
        {'ids': [4]},
        {'ids': [3]},
        {'ids': [2]}
    ],
    [
        {'ids': [3, 4]},
        {'ids': [1, 2]}
    ]
]