字典列表，根据列表键值分组并消除交集

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

- KeyJ

---

你有更多的例子吗？我仍然不确定你希望如何对数据进行分组。 - Prashin Jeevaganth

所以你想查看所有数据，并进行最佳分组，以避免任何交叉的ID？ - Pranav Hosangadi

为什么[1, 2]和[3, 4]被分组在一起？它们被分组在一起是因为它们之间没有交集。 - KeyJ

在你的“可以分为3个元素列表”的例子中，为什么我们不能只创建两个组[(1), (2), (3), (4)]; [(1, 2), (3, 4)]？ - Pranav Hosangadi

抱歉，没有注意到，是的，它甚至可以作为2个元素列表进行分组： [[{'ids': [1]}, {'ids': [4]}, {'ids': [2]}, {'ids': [3]}], [{'ids': [3, 4]}, {'ids': [1, 2]}]] - KeyJ

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

这种情况下也没有重复项。

- Pranav Hosangadi

---

谢谢，伙计，你真是个天才。这正是我所需要的。 - KeyJ

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

- kluvin

---

嘿，谢谢你的时间，但我需要保存我的原始字典。 - KeyJ

如果我们使用如下数据： [ {"ids": [1]}, {"ids": [3, 4]}, {"ids": [1, 2]}, {"ids": [5]}, {"ids": [3]}, {"ids": [2]}, {"ids": [2, 3]}, ] 结果数据将包含重复项：[{'ids': [[1], [5], [3], [2]]}, {'ids': [[3, 4], [1, 2], [2, 3]]}] - KeyJ

也许有点晚了，但我现在明白了。也学到了一些东西。 - kluvin