根据列表大小将包含字典的列表拆分为不同的列表，但次要条件是基于条件。

Question

我目前有一个字典列表，其外观如下:

total_list = [
    {'email': '[e-mail]', 'id': 1, 'country': 'UK'},
    {'email': '[e-mail]', 'id': 1, 'country': 'Germany'}, 
    {'email': '[e-mail]', 'id': 2, 'country': 'UK'}
    {'email': '[e-mail]', 'id': 3, 'country': 'Italy'},
    {'email': '[e-mail]', 'id': 3, 'country': 'Netherland'},
    {'email': '[e-mail]', 'id': 4, 'country': 'France'},
    ...
]

我想根据大小来进行分割，比如说新的大小列表是每个列表3个项目，但我也想确保所有相同用户在同一个新子列表中。

所以我试图创建的结果是：

list_a = [
    {'email': '[e-mail]', 'id': 1, 'country': 'UK'},
    {'email': '[e-mail]', 'id': 2, 'country': 'UK'}    
    {'email': '[e-mail]', 'id': 1, 'country': 'Germany'}
]
  
list_b = [
    {'email': '[e-mail]', 'id': 3, 'country': 'Italy'},
    {'email': '[e-mail]', 'id': 4, 'country': 'France'}
    {'email': '[e-mail]', 'id': 3, 'country': 'Netherland'},
    ...
]

显然在我提供的示例中，用户在列表中非常靠近，但实际上它们可能分散更多。 我考虑根据电子邮件对列表进行排序，然后进行拆分，但是如果应该分组在一起的项目恰好位于主列表将被分割的确切位置，我不确定会发生什么。

到目前为止我尝试过：

def list_splitter(main_list, size):
    for i in range(0, len(main_list), size):
        yield main_list[i:i + size]

# calculating the needed number of sublists
max_per_batch = 3
number_of_sublists = ceil(len(total_list) / max_per_batch)

# sort the data by email
total_list.sort(key=lambda x: x['email'])

sublists = list(list_splitter(main_list=total_list, size=max_per_batch))

问题在于使用这种逻辑，我无法 100% 确保具有相同电子邮件值的任何项目最终都会出现在同一个子列表中。由于排序的原因，这种情况可能发生，但并不确定。

基本上，我需要一种方法来确保具有相同电子邮件的项目始终位于同一子列表中，但拆分的主要条件是子列表大小。

- Flora Biletsiou

---

你忘记了在问题中附上你尝试解决这个问题的内容。 - Scott Hunter

先把它做得不好，然后再改进。看看如何创建一个 [mcve] 并 [edit] 问题。 - Peter Wood

我的错，现在已经添加了。 - Flora Biletsiou

每个子列表需要是相同的大小吗？或者特定的子列表可以更小吗？假设电子邮件用户数量始终比子列表大小小。如果是这样，那么这听起来像是装箱问题的变体。另请参见：装箱幻灯片。 - Pavloski

用户输入如何平衡？假设我们有一个包含1000个电子邮件的列表。我们可以只有2个用户吗？并且完全不平衡的表示，例如998个条目属于用户a，而仅有2个属于用户b吗？那么生成的子列表大小呢？全部相同吗？ - 0x0fba

Answer 1

这个解决方案首先仅使用所有电子邮件的列表进行操作。然后，基于频率和组大小的limit将电子邮件分组。接下来，剩余数据，即id和country，将与电子邮件组合并。

第一个函数create_groups对电子邮件列表进行操作。它计算每个电子邮件出现的次数并将它们分组。每个新的组以最常见的电子邮件开始。如果组中还有空间，则查找最常见且适合该组的项。如果存在这样的项，则将其添加到该组中。

这个过程重复进行，直到组满为止；然后，开始一个新的组。

from operator import itemgetter
from itertools import groupby, chain
from collections import Counter


def create_groups(items, group_size_limit):
    # Count the frequency of all items and create a list of items 
    # sorted by descending frequency
    items_not_grouped = Counter(items).most_common()
    groups = []

    while items_not_grouped:
        # Start a new group with the most frequent ungrouped item
        item, count = items_not_grouped.pop(0)
        group, group_size = [item], count
        while group_size < group_size_limit:
            # If there is room left in the group, look for a new group member
            for index, (candidate, candidate_count) \
                    in enumerate(items_not_grouped):
                if candidate_count <= group_size_limit - group_size:
                    # If the candidate fits, add it to the group
                    group.append(candidate)
                    group_size += candidate_count
                    # ... and remove it from the items not grouped
                    items_not_grouped.pop(index)
                    break
            else:
                # If the for loop did not break, no items fit in the group
                break

        groups.append(group)

    return groups

这是在您的示例上使用该函数的结果：

users = [
    {'email': '[e-mail]', 'id': 1, 'country': 'UK',},
    {'email': '[e-mail]', 'id': 2, 'country': 'UK'},
    {'email': '[e-mail]', 'id': 1, 'country': 'Germany'},
    {'email': '[e-mail]', 'id': 3, 'country': 'Italy'},
    {'email': '[e-mail]', 'id': 4, 'country': 'France'},
    {'email': '[e-mail]', 'id': 3, 'country': 'Netherland'}
]

emails = [user["email"] for user in users]
email_groups = create_groups(emails, 3)
# -> [
#   ['[e-mail]', '[e-mail]'], 
#   ['[e-mail]', '[e-mail]']
# ]

最后，当组已经创建后，函数join_data_on_groups会将原始用户字典分组。它将之前的电子邮件组和字典列表作为参数传入：

def join_data_on_groups(groups, item_to_data):
    item_to_data = {item: list(data) for item, data in item_to_data}

    groups = [(item_to_data[item] for item in group) for group in groups]
    groups = [list(chain(*group)) for group in groups]

    return groups


email_getter = itemgetter("email")
users_grouped_by_email = groupby(sorted(users, key=email_getter), email_getter)

user_groups = join_data_on_groups(email_groups, users_grouped_by_email)

print(user_groups)

结果：

[
  [
    {'email': '[e-mail]', 'id': 1, 'country': 'UK'},
    {'email': '[e-mail]', 'id': 1, 'country': 'Germany'}, 
    {'email': '[e-mail]', 'id': 2, 'country': 'UK'}
  ],
  [
    {'email': '[e-mail]', 'id': 3, 'country': 'Italy'},
    {'email': '[e-mail]', 'id': 3, 'country': 'Netherland'},
    {'email': '[e-mail]', 'id': 4, 'country': 'France'}
  ]
]

- Sebastian Baltser

---

我在考虑使用模数方法，但是您的答案很好！ - Jason Chia

Answer 2

通用解决方案（详细解释如下）：

import pandas as pd
import numpy as np
from numberpartitioning import karmarkar_karp

def solution(data, groupby: str, partition_size: int):
    df = pd.DataFrame(data)
    groups = df.groupby([groupby]).count()
    groupby_counts = groups.iloc[:, 0].values
    num_parts = len(df) // partition_size
    result = karmarkar_karp(groupby_counts, num_parts=num_parts, return_indices=True)
    part_keys = groups.index.values[np.array(result.partition)]
    partitions = [df.loc[df[groupby].isin(key)].to_dict('records') for key in part_keys]
    return partitions


solution(total_list, groupby="email", partition_size=3)

给出了一个有效的解决方案（尽管与您示例中的解决方案稍有不同）

[[{'country': 'UK', 'email': '[e-mail]', 'id': 2},
  {'country': 'Italy', 'email': '[e-mail]', 'id': 3},
  {'country': 'Netherland', 'email': '[e-mail]', 'id': 3}],
 [{'country': 'UK', 'email': '[e-mail]', 'id': 1},
  {'country': 'Germany', 'email': '[e-mail]', 'id': 1},
  {'country': 'France', 'email': '[e-mail]', 'id': 4}]]

---

解释

我们可以使用分区算法，例如Karmarkar-Karp Algorithm。它将一组数字分成k个分区，使得每个分区的总和尽可能接近。已经存在一个纯Python实现numberpartition。只需执行python3 -m pip install numberpartitioning即可。

该算法仅适用于数字，但我们可以使用每个组中电子邮件数量的计数来编码电子邮件组。让我们使用数据框来保存您的数据：

>>> df = pd.DataFrame(total_list)

然后按电子邮件分组查找计数：

>>> email_counts = df.groupby(["email"])["id"].count().rename("count")

例如，对于total_list的组计数：

>>> email_counts
email
[e-mail]    2
[e-mail]    1
[e-mail]    2
[e-mail]    1
Name: count, dtype: int64

在您的示例中，我们希望每个分区有3个条目（因此partition_size=3），这意味着分区数为num_parts = len(total_list)/partition_size = 2 因此，如果我们执行karmarkar_karp([2, 1, 2, 1], num_parts=True)，我们将得到以下分区[[2, 1], [2, 1]]和分区大小[3, 3]。

但是我们不关心计数，我们关心哪个电子邮件与每个计数相关联。因此，我们只需返回索引：

>>> result = karmarkar_karp(email_counts.values, num_parts=2, return_indices=True)
>>> result
PartitioningResult(partition=[[2, 1], [0, 3]], sizes=[3, 3])

根据索引，分组如下：

partition 1: indices [2, 1] -> [userc, userb]
partition 2: indices [0, 3] -> [usera, userd]

这与你所写的略有不同，但仍然是一个有效的解决方案。

我们通过运行以下命令来查找电子邮件分区：

>>> email_partitions = email_counts.index.values[np.array(result.partition)]

给定电子邮件分区，我们现在只需根据其所属的分区拆分total_list中的每个条目。

>>> partitions = [df.loc[df["email"].isin(emails)].to_dict('records') for emails in email_partitions]

然后打印partitions，我们得到：

>>> partitions
[[{'email': '[e-mail]', 'id': 2, 'country': 'UK'},
  {'email': '[e-mail]', 'id': 3, 'country': 'Italy'},
  {'email': '[e-mail]', 'id': 3, 'country': 'Netherland'}],
 [{'email': '[e-mail]', 'id': 1, 'country': 'UK'},
  {'email': '[e-mail]', 'id': 1, 'country': 'Germany'},
  {'email': '[e-mail]', 'id': 4, 'country': 'France'}]]

- imakappa

Answer 3

我会考虑使用队列或FIFO类型，弹出元素供使用，而不是将字典保存在列表中。但是根据您所拥有的内容，您可以首先创建一个新的排序列表并执行您正在执行的操作（有点），或者这里有另一种解决方案，因为有许多解决方案可以以任何想象的方式组织数据（实际上，您的约束条件不同，因为您希望将每个输出对象分配给变量名？我将忽略该部分）：

1. 创建一个类型为str：list的字典D，其中您的键是用户电子邮件，列表是最初为空的[]的所有字典条目的列表。如果您有大量数据，则排队/生成器会更好，但重点是过滤/格式化输入。
2. 将total_list解析为D，因此每次命中相同的用户电子邮件时，您都会将该字典附加到该键的值列表中。可以删除total_list。
3. 现在解析D，形成包含字典列表的输出列表（或生成器），每个列表限制为3个字典。这可以是类似于您现在拥有的生成器的生成器。

- MrMattBusby