生成一个集合的所有相同大小的分区

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 

在单剂的琐碎情况下，我们得到一个单一dicti onary并终止。

如果有不止一个代理，我们：

1. 生成索引到items应该被分配到第一代理的所有组合。

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

正如你所看到的，它处理的情况下，items不能平分在之间3210。此外，与各种基于permutations()的答案不同，它不会浪费工作计算重复结果，因此运行速度比他们快得多。

Answer 2

from itertools import combinations,permutations 
def get(items, no_of_agents): 
    def chunks(l, n): 
     """Yield successive n chunks from l.""" 
     rt = [] 
     ln = len(l) // n 
     for i in range(0, len(l) - ln - 1, ln): 
      rt.append(l[i:i + ln]) 
     rt.append(l[i + ln:]) 
     return rt 

    for i in permutations(items, len(items)): 
     yield chunks(i,no_of_agents) 

def get_equal_partitions(items, agents): 
    for i in get(items, len(agents)): 
     yield dict(zip(agents, i)) 

items = [i for i in range(4)] 
agents = ["A","B","C"] 

for i in get_equal_partitions(items,agents): 
    print(i) 

Answer 3

一个非常低效的内存解决方案，但很短，更“pythonic”。而且，结果中的字典顺序也是非常随意的，imo。

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() 

Answer 4

# -*- coding: utf-8 -*- 

from itertools import combinations 
from copy import copy 


def main(agents, items): 
    if len(items) % len(agents): 
     return [] 

    result = [{'remain': items}] 

    part_size = len(items)/len(agents) 

    while True: 
     for item in result[:]: 
      remain_agent = set(agents) - set(item.keys()) 
      if not remain_agent: 
       continue 

      result.remove(item) 

      agent = remain_agent.pop() 

      for combination in combinations(item['remain'], part_size): 
       current_item = copy(item) 
       current_item.update({agent: combination, 'remain': list(set(item['remain']) - set(combination))}) 
       result.append(current_item) 

      break 
     else: 
      break 

    for item in result: 
     item.pop('remain', None) 
    return result 


if __name__ == '__main__': 
    agents = ['A', 'B', 'C'] 
    items = [1, 2, 3, 4, 5, 6] 

    t = main(agents, items) 

这是在行动：

In [3]: agents = ['A', 'B'] 

In [4]: items = [1, 2, 3, 4] 

In [5]: result = main(agents, items) 

In [6]: for item in result: 
    ...:  print item 
    ...: 
{'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)} 

Answer 5

如果你有一个permutations功能，它可以处理输入重复的元素没有在输出端产生重复的排列，可以很有效地做到这一点。不幸的是，itertools.permutations不会做我们想要的（len(list(itertools.permutations('aaa')))为6，不1，这是我们想要的）。

这里有一个置换函数我写了以前的一些问题，这恰好做正确的事与重复的输入值：

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] 

现在，这里是如何使用它的项目分配给您的代理：

def equal_partitions(agents, items): 
    items_per_agent, extra_items = divmod(len(items), len(agents)) 
    item_assignments = agents * items_per_agent + agents[:extra_items] 
    for assignment in permutations(item_assignments): 
     result = {} 
     for agent, item in zip(assignment, items): 
      result.setdefault(agent, []).append(item) 
     yield result 

第一线建立引用到我们代理的列表是相同长度的项目列表。每个代理人的重复次数与他们将收到的物品数量相同。如果items列表不能完全均匀分配，我会为前几个代理添加一些额外的引用。如果您愿意，可以添加其他内容（例如['extra'] * extra_items，也许）。

主循环运行在作业列表中的排列。然后，它运行一个内部循环，将来自排列的代理与相应的项目进行匹配，并将结果打包到您想要的格式的字典中。

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