Создать все равные по размеру разделы

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 не может быть поровну между agents.Кроме того, в отличие от различных ответов на вопросы 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

Жесткое решение, неэффективное для памяти, но довольно короткое и более «питоновое». Кроме того, порядок словарей в результате довольно произволен, имо.

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'))) is 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, возможно).

Главный цикл работает на перестановках списка назначений. Затем он запускает внутренний цикл, который соответствует агенту от перестановки к соответствующему элементу, и упаковывает результат в словарь в нужном формате.

Этот код должен быть асимптотически оптимальным как во времени, так и пространстве для любого количества агентов или предметов. Тем не менее, он все еще может быть медленным, поскольку он полагается на мою функцию permutation, написанную на чистом Python, а не на более быструю реализацию на C. Возможно, что есть эффективный способ получить перестановки, которые мы хотим, используя itertools, но я не точно точно как.