生成一个

Question

我需要一个生成器，它获取一组“代理”和一组“项”作为输入，并生成所有分区，其中每个代理都获得相同数量的项。例如：

>>> for p in equalPartitions(["A","B"], [1,2,3,4]): print(p)
{'A': [1, 2], 'B': [3, 4]}
{'A': [1, 3], 'B': [2, 4]}
{'A': [1, 4], 'B': [2, 3]}
{'A': [2, 3], 'B': [1, 4]}
{'A': [2, 4], 'B': [1, 3]}
{'A': [3, 4], 'B': [1, 2]}

对于两个代理，这很简单（假设项目数为偶数）：

^{pr2}$

对于三个探员来说，情况变得更加复杂：

^{3}$

有没有更通用的解决方案，适用于任何数量的代理？在

Answer 1

下面是一个递归解决方案，它通过将适当数量的项分配给第一个代理，然后将问题的其余部分交给进一步的自身调用来实现：

from itertools import combinations

def part(agents, items):
    if len(agents) == 1:
        yield {agents[0]: items}
    else:
        quota = len(items) // len(agents)
        for indexes in combinations(range(len(items)), quota):
            remainder = items[:]
            selection = [remainder.pop(i) for i in reversed(indexes)][::-1]
            for result in part(agents[1:], remainder):
                result[agents[0]] = selection
                yield result

在单个代理的简单情况下，我们生成一个字典并终止。在

如果有多个代理，我们：

1. 将应分配给第一个代理的索引的所有组合生成到items中。

2. 将这些索引处的项按相反顺序从items的副本弹出到selection，然后用[::-1]将结果反转回来，以保持预期的顺序。

3. 对其余的代理和项递归调用part()。

4. 将我们已经做出的选择添加到这些递归调用生成的每个结果中，并生成该结果。

这就是它的作用：

^{pr2}$

>>> for p in part(["A", "B", "C"], [1, 2, 3, 4, 5, 6, 7, 8, 9]):
...     print(p)
... 
{'A': [1, 2, 3], 'B': [4, 5, 6], 'C': [7, 8, 9]}
{'A': [1, 2, 3], 'B': [4, 5, 7], 'C': [6, 8, 9]}
{'A': [1, 2, 3], 'B': [4, 5, 8], 'C': [6, 7, 9]}
{'A': [1, 2, 3], 'B': [4, 5, 9], 'C': [6, 7, 8]}
{'A': [1, 2, 3], 'B': [4, 6, 7], 'C': [5, 8, 9]}
  # [...]    
{'A': [7, 8, 9], 'B': [3, 4, 5], 'C': [1, 2, 6]}
{'A': [7, 8, 9], 'B': [3, 4, 6], 'C': [1, 2, 5]}
{'A': [7, 8, 9], 'B': [3, 5, 6], 'C': [1, 2, 4]}
{'A': [7, 8, 9], 'B': [4, 5, 6], 'C': [1, 2, 3]}

>>> for p in part(["A", "B", "C"], [1, 2, 3, 4, 5, 6, 7]):
...     print(p)
... 
{'A': [1, 2], 'B': [3, 4], 'C': [5, 6, 7]}
{'A': [1, 2], 'B': [3, 5], 'C': [4, 6, 7]}
{'A': [1, 2], 'B': [3, 6], 'C': [4, 5, 7]}
{'A': [1, 2], 'B': [3, 7], 'C': [4, 5, 6]}
  # [...]
{'A': [6, 7], 'B': [2, 5], 'C': [1, 3, 4]}
{'A': [6, 7], 'B': [3, 4], 'C': [1, 2, 5]}
{'A': [6, 7], 'B': [3, 5], 'C': [1, 2, 4]}
{'A': [6, 7], 'B': [4, 5], 'C': [1, 2, 3]}

如您所见，它处理items不能在agents之间等分的情况。此外，与各种基于permutations()的答案不同，它不会浪费计算重复结果的工作量，因此运行速度比它们快得多。在

Answer 2

如果您有一个permutations函数，它可以处理输入中的重复元素，而不会在输出中产生重复的置换，那么您可以非常有效地做到这一点。不幸的是，itertools.permutations没有做我们想做的事情（len(list(itertools.permutations('aaa')))是{}，不是{}，这是我们想要的）。在

这是我为前面的问题编写的一个置换函数，它恰好对重复的输入值做了正确的处理：

def permutations(seq):
    perm = sorted(seq) # the first permutation is the sequence in sorted order
    while True:
        yield perm

        # find largest index i such that perm[i] < perm[i+1]
        for i in range(len(perm)-2, -1, -1):
            if perm[i] < perm[i+1]:
                break
        else: # if none was found, we've already found the last permutation
            return

        # find the largest index j such that perm[i] < perm[j] (always exists)
        for j in range(len(perm)-1, -1, -1):
            if perm[i] < perm[j]:
                break

        # Swap values at indexes i and j, then reverse the values from i+1
        # to the end. I've packed that all into one operation, with slices.
        perm = perm[:i]+perm[j:j+1]+perm[-1:j:-1]+perm[i:i+1]+perm[j-1:i:-1]

现在，下面是如何使用它将项目分配给代理：

^{pr2}$

第一行构建对我们代理的引用列表，其长度与项目列表的长度相同。每个代理重复的次数与它们将接收的项目数相同。如果items列表不能完全均匀地划分，我将添加一些额外的引用到前几个代理。如果愿意，可以添加其他内容（比如['extra'] * extra_items）。在

主循环在分配列表的排列上运行。然后，它运行一个内部循环，该循环将置换中的代理与相应的项相匹配，并将结果打包到所需格式的字典中。在

对于任意数量的代理或项目，该代码在时间和空间上都应该是渐近最优的。也就是说，它可能仍然很慢，因为它依赖于我用纯Python编写的permutation函数，而不是用C编写的更快的实现。也许有一种有效的方法可以使用itertools来获得我们想要的排列，但我不太确定如何实现。在

Answer 3

一个非常低内存的解决方案，但相当短和更“Python”。而且，词典在结果中的顺序是相当随意的

import itertools as it
from pprint import pprint
from time import time

agents = ('a', 'b', 'c')
items = (1,2,3,4,5,6,7,8,9)

items_per_agent = int(len(items)/len(agents))

def split_list(alist,max_size=1):
    """Yield successive n-sized chunks from alist."""
    for i in range(0, len(alist), max_size):
        yield alist[i:i+max_size]

def my_solution():
    # I have put this into one-liner below
    # combos = set()
    # i=0
    # for perm in it.permutations(items, len(items)):
    #   combo = tuple(tuple(sorted(chunk)) for chunk in split_list(perm, max_size=items_per_agent))
    #   combos.add(combo)
    #   print(combo, i)
    #   i+=1

    combos = {tuple(tuple(sorted(chunk)) for chunk in split_list(perm, max_size=items_per_agent)) for perm in it.permutations(items, len(items))}

    # I have put this into one-liner below
    # result = []
    # for combo in combos:
    #   result.append(dict(zip(agents,combo)))

    result = [dict(zip(agents,combo)) for combo in combos]

    pprint(result)

my_solution()