生成一個集合的所有相同大小的分區

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，但我不是完全確定如何。