Générer toutes les partitions de même taille d'un ensemble

Question

J'ai besoin d'un générateur qui reçoit en entrée un ensemble d'agents et un ensemble d'éléments, et génère toutes les partitions dans lesquelles chaque agent obtient le même nombre d'éléments. Par exemple:

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

Pour deux agents cela est facile (en supposant que le nombre d'éléments est même):

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 
      } 

Pour trois agents cela devient plus compliqué:

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 
      } 

est-il une solution plus générale, qui fonctionne pour un nombre quelconque d'agents?

Answer 1

est ici une solution récursif qui fonctionne en affectant le nombre approprié d'éléments au premier agent, et remettre le reste du problème de à d'autres invocations de lui-même:

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 

Dans le cas trivial d'un seul agent, nous cédons un seul dicti unaire et terminer.

S'il y a plus d'un agent, nous:

1. générons toutes les combinaisons d'index en items qui devraient être attribués au premier agent.

2. Pop les éléments à ces indices d'une copie de items dans l'ordre inverse (pour éviter de bousiller les index) en selection, en inversant le résultat à nouveau ensuite avec [::-1] pour maintenir l'ordre attendu.

3. Appelez part() de manière récursive sur les agents et éléments restants. Ajoutez la sélection que nous avons déjà faite à chaque résultat obtenu par ces appels récursifs, et cédez-la.

Ici, il est en action:

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

Comme vous pouvez le voir, il gère les cas où items ne peut pas être aussi divisé entre agents.En outre, contrairement aux diverses réponses basées sur permutations(), il ne gaspille pas de travail de calcul des résultats en double, donc fonctionne beaucoup plus vite que eux.

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

Une solution terriblement inefficace en mémoire, mais assez courte et plus "pythonique". En outre, l'ordre des dictionnaires dans le résultat est tout à fait arbitraire, 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) 

Ici, il est en action:

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

Si vous avez une fonction permutations qui peut gérer des éléments répétés dans l'entrée sans produire de permutations dupliquées dans la sortie, vous pouvez le faire assez efficacement. Malheureusement, itertools.permutations ne fait pas ce que nous voulons (len(list(itertools.permutations('aaa'))) est 6, pas 1, ce que nous voulons).

est ici une fonction de permutation j'ai écrit pour une question précédente, ce qui arrive à faire la bonne chose avec des valeurs d'entrée dupliquées:

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] 

Maintenant, voici comment l'utiliser pour affecter des éléments à vos agents:

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 

Les premières lignes construisent une liste de références à nos agents qui a la même longueur que la liste d'éléments. Chaque agent est répété autant de fois que le nombre d'éléments qu'il recevra. Si la liste items ne peut pas être divisée exactement également, j'ajoute quelques références supplémentaires aux premiers agents. Vous pouvez ajouter quelque chose d'autre si vous préférez (comme ['extra'] * extra_items, peut-être).

La boucle principale s'exécute sur les permutations de la liste des affectations. Il exécute ensuite une boucle interne qui correspond à un agent de la permutation à l'élément correspondant, et emballe le résultat dans un dictionnaire dans le format que vous voulez.

Ce code doit être asymptotiquement optimal dans le temps et l'espace pour un nombre quelconque d'agents ou d'éléments. Cela dit, il peut encore être lent, puisqu'il repose sur ma fonction permutation écrite en Python pur plutôt qu'une implémentation plus rapide en C. Il se peut qu'il y ait un moyen efficace d'obtenir les permutations que nous voulons en utilisant itertools, mais je ne suis pas exactement sûr comment.