Necesito un generador que obtenga como entrada un conjunto de 'agentes' y un conjunto de 'elementos', y genere todas las particiones en las que cada agente obtenga el mismo número de elementos. Por ejemplo:

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

Para dos agentes esto es fácil (suponiendo que el número de elementos es par):

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
            }

Para tres agentes esto se vuelve más complicado:

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
            }

¿Existe una solución más general que funcione para cualquier número de agentes?

2
Erel Segal-Halevi 17 feb. 2017 a las 09:28

5 respuestas

La mejor respuesta

Aquí hay una solución recursiva, que funciona asignando el número apropiado de elementos al primer agente y entregando el resto del problema a invocaciones adicionales de sí mismo:

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

En el caso trivial de un solo agente, producimos un solo diccionario y terminamos.

Si hay más de un agente, nosotras:

  1. Genere todas las combinaciones de índices en items que deben asignarse al primer agente.

  2. Haga estallar los elementos en esos índices de una copia de items en orden inverso (para evitar desordenar los índices) en selection, invirtiendo el resultado nuevamente nuevamente con [::-1] para mantener el orden esperado .

  3. Llame part() recursivamente sobre los agentes y elementos restantes.

  4. Agregue la selección que ya hicimos a cada resultado producido por esas llamadas recursivas, y produzca eso.

Aquí está en acción:

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

Como puede ver, maneja casos en los que items no se puede dividir por igual entre agents. Además, a diferencia de las diversas respuestas basadas en permutations(), no desperdicia trabajo calculando resultados duplicados, por lo que se ejecuta mucho más rápido que ellos.

2
Zero Piraeus 17 feb. 2017 a las 18:14
# -*- 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)

Aquí está en acción:

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)}
0
duke yu 17 feb. 2017 a las 09:42

Si tiene una función permutations que puede manejar elementos repetidos en la entrada sin producir permutaciones duplicadas en la salida, puede hacerlo de manera bastante eficiente. Desafortunadamente, itertools.permutations no hace lo que queremos (len(list(itertools.permutations('aaa'))) es 6, no 1, que queremos).

Aquí hay una función de permutación que escribí para alguna pregunta anterior, que hace lo correcto con valores de entrada duplicados:

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]

Ahora, aquí está cómo usarlo para asignar elementos a sus agentes:

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

Las primeras líneas crean una lista de referencias a nuestros agentes que tiene la misma longitud que la lista de elementos. Cada agente se repite tantas veces como la cantidad de artículos que recibirá. Si la lista items no se puede dividir exactamente de manera equitativa, agrego algunas referencias adicionales a los primeros agentes. Puede agregar algo más si lo prefiere (como ['extra'] * extra_items, tal vez).

El bucle principal se ejecuta en las permutaciones de la lista de asignaciones. Luego ejecuta un bucle interno que coincide con un agente desde la permutación hasta el elemento correspondiente, y empaqueta el resultado en un diccionario en el formato que desee.

Este código debe ser asintóticamente óptimo tanto en tiempo como en espacio para cualquier número de agentes o elementos. Dicho esto, aún puede ser lento, ya que depende de mi función permutation escrita en Python puro en lugar de una implementación más rápida en C. Puede ser que haya una manera eficiente de obtener las permutaciones que queremos usar {{X1 }}, pero no estoy exactamente seguro de cómo.

1
Blckknght 17 feb. 2017 a las 19:49

Una solución terriblemente ineficiente de memoria, pero bastante corta y más "pitónica". Además, el orden de los diccionarios en el resultado es bastante arbitrario, en mi opinión.

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()
0
Highstaker 17 feb. 2017 a las 08:57
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)
-1
Himaprasoon 17 feb. 2017 a las 08:36