python - 生成集合中所有大小相等的分区

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

对于两个代理来说，这很容易(假设项目数量是偶数):

itemsPerAgent = len(items) // len(agents)
for bundle0 in itertools.combinations(items, itemsPerAgent):
        bundle1 =  [item for item in items if item not in bundle0]
        yield {
            agents[0]: list(bundle0),
            agents[1]: bundle1
            }

对于三个代理来说，这变得更加复杂:

itemsPerAgent = len(items) // len(agents)
for bundle0 in itertools.combinations(items, itemsPerAgent):
    bundle12 =  [item for item in items if item not in bundle0]
    for bundle1 in itertools.combinations(bundle12, itemsPerAgent):
        bundle2 =  [item for item in bundle12 if item not in bundle1]
        yield {
            agents[0]: list(bundle0),
            agents[1]: list(bundle1),
            agents[2]: bundle2
            }

是否有更通用的解决方案，适用于任意数量的代理？

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. 将所有索引组合生成到应分配给第一个代理的项目中。

2. 将这些索引处的项目从 items 的副本中以相反的顺序(以避免弄乱索引)弹出到 selection 中，再次反转结果然后使用 [::-1] 来维持预期的顺序。

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

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

这是在行动:

>>> for p in part(["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]}

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

如您所见，它处理项目无法在代理之间平均分配的情况。此外，与各种基于 permutations() 的答案不同，它不会浪费工作来计算重复结果，因此运行速度比它们快得多。