library - itertools python 3
Encuentra los grupos de parejas más eficientes. (6)
Problema
Tengo un grupo de personas y quiero que cada persona tenga una reunión 1: 1 con todas las demás personas del grupo. Una persona determinada solo puede reunirse con otra persona a la vez, así que quiero hacer lo siguiente:
- Encuentra todas las combinaciones posibles de parejas.
- Agrupe los pares en "rondas" de reuniones, donde cada persona solo puede estar en una ronda una vez, y donde una ronda debe contener tantos pares como sea posible para satisfacer todas las combinaciones de parejas posibles en el menor número de rondas.
Para demostrar el problema en términos de entrada / salida deseada, digamos que tengo la siguiente lista:
>>> people = [''Dave'', ''Mary'', ''Susan'', ''John'']
Quiero producir el siguiente resultado:
>>> for round in make_rounds(people):
>>> print(round)
[(''Dave'', ''Mary''), (''Susan'', ''John'')]
[(''Dave'', ''Susan''), (''Mary'', ''John'')]
[(''Dave'', ''John''), (''Mary'', ''Susan'')]
Si tuviera un número impar de personas, entonces esperaría este resultado:
>>> people = [''Dave'', ''Mary'', ''Susan'']
>>> for round in make_rounds(people):
>>> print(round)
[(''Dave'', ''Mary'')]
[(''Dave'', ''Susan'')]
[(''Mary'', ''Susan'')]
La clave de este problema es que necesito que mi solución sea eficaz (dentro de lo razonable). He escrito un código que funciona , pero a medida que el tamaño de las people crece, se vuelve exponencialmente lento. No sé lo suficiente sobre cómo escribir algoritmos de rendimiento para saber si mi código es ineficiente o si simplemente estoy obligado por los parámetros del problema
Lo que he intentado
El paso 1 es fácil: puedo obtener todos los emparejamientos posibles utilizando itertools.combinations :
>>> from itertools import combinations
>>> people_pairs = set(combinations(people, 2))
>>> print(people_pairs)
{(''Dave'', ''Mary''), (''Dave'', ''Susan''), (''Dave'', ''John''), (''Mary'', ''Susan''), (''Mary'', ''John''), (''Susan'', ''John'')}
Para hacer las rondas, estoy construyendo una ronda así:
- Crear una lista
roundvacía - Iterar sobre una copia del conjunto de
people_pairscalculado usando el método decombinationsanterior - Para cada persona en el par, verifique si hay algún emparejamiento existente dentro de la
roundactual que ya contenga ese individuo - Si ya hay un par que contiene uno de los individuos, omita ese emparejamiento para esta ronda. De lo contrario, agregue el par a la ronda y elimínelo de la lista
people_pairs. - Una vez que todas las parejas de personas hayan sido iteradas, agregue la ronda a una lista de
roundsmaestras - Comienza de nuevo, ya que las
people_pairsahora contienen solo las parejas que no llegaron a la primera ronda
Eventualmente, esto produce el resultado deseado, y descompone los pares de mi gente hasta que no queda ninguno y se calculan todas las rondas. Ya puedo ver que esto requiere un número ridículo de iteraciones, pero no conozco una mejor manera de hacerlo.
Aquí está mi código:
from itertools import combinations
# test if person already exists in any pairing inside a round of pairs
def person_in_round(person, round):
is_in_round = any(person in pair for pair in round)
return is_in_round
def make_rounds(people):
people_pairs = set(combinations(people, 2))
# we will remove pairings from people_pairs whilst we build rounds, so loop as long as people_pairs is not empty
while people_pairs:
round = []
# make a copy of the current state of people_pairs to iterate over safely
for pair in set(people_pairs):
if not person_in_round(pair[0], round) and not person_in_round(pair[1], round):
round.append(pair)
people_pairs.remove(pair)
yield round
El cálculo del rendimiento de este método para tamaños de lista de 100-300 usando https://mycurvefit.com muestra que calcular rondas para una lista de 1000 personas probablemente tomaría alrededor de 100 minutos. ¿Hay una manera más eficiente de hacer esto?
Nota: en realidad no estoy tratando de organizar una reunión de 1000 personas :) este es solo un ejemplo simple que representa el problema de coincidencia / combinatoria que estoy tratando de resolver.
Cuando necesitas búsquedas rápidas, hashes / dicts son el camino a seguir. Lleve un registro de quién ha estado en cada ronda en un dict lugar de una list y será mucho más rápido.
Dado que se está introduciendo en algoritmos, el estudio de la notación O grande le ayudará y conocer qué estructuras de datos son buenas en qué tipo de operaciones también es clave. Consulte esta guía: https://wiki.python.org/moin/TimeComplexity para conocer la complejidad del tiempo de las incorporaciones de Python. Verá que la comprobación de un elemento en una lista es O (n), lo que significa que se escala linealmente con el tamaño de sus entradas. Entonces, como está en un bucle, terminas con O (n ^ 2) o peor. Para los dictados, las búsquedas son generalmente O (1) lo que significa que no importa el tamaño de su entrada.
Además, no anular las incorporaciones. He cambiado de round a round_
from itertools import combinations
# test if person already exists in any pairing inside a round of pairs
def person_in_round(person, people_dict):
return people_dict.get(person, False)
def make_rounds(people):
people_pairs = set(combinations(people, 2))
people_in_round = {}
# we will remove pairings from people_pairs whilst we build rounds, so loop as long as people_pairs is not empty
while people_pairs:
round_ = []
people_dict = {}
# make a copy of the current state of people_pairs to iterate over safely
for pair in set(people_pairs):
if not person_in_round(pair[0], people_dict) and not person_in_round(pair[1], people_dict):
round_.append(pair)
people_dict[pair[0]] = True
people_dict[pair[1]] = True
people_pairs.remove(pair)
yield round_
Dos cosas que puedes hacer de inmediato:
No haga una copia del conjunto cada vez que esté en la lista. Eso es una gran pérdida de tiempo / memoria. En su lugar, modifique el conjunto una vez después de cada iteración.
Mantenga un conjunto separado de personas en cada ronda. Buscar a una persona en un grupo será un orden de magnitud más rápido que recorrer toda la ronda.
Ex:
def make_rounds(people):
people_pairs = set(combinations(people, 2))
while people_pairs:
round = set()
people_covered = set()
for pair in people_pairs:
if pair[0] not in people_covered /
and pair[1] not in people_covered:
round.add(pair)
people_covered.update(pair)
people_pairs -= round # remove thi
yield round
Esta es una implementación del algoritmo descrito en el artículo de Wikipedia del torneo Round-robin .
from itertools import cycle , islice, chain
def round_robin(iterable):
items = list(iterable)
if len(items) % 2 != 0:
items.append(None)
fixed = items[:1]
cyclers = cycle(items[1:])
rounds = len(items) - 1
npairs = len(items) // 2
return [
list(zip(
chain(fixed, islice(cyclers, npairs-1)),
reversed(list(islice(cyclers, npairs)))
))
for _ in range(rounds)
for _ in [next(cyclers)]
]
Esto toma unos 45s en mi computadora
def make_rnds(people):
people_pairs = set(combinations(people, 2))
# we will remove pairings from people_pairs whilst we build rnds, so loop as long as people_pairs is not empty
while people_pairs:
rnd = []
rnd_set = set()
peeps = set(people)
# make a copy of the current state of people_pairs to iterate over safely
for pair in set(people_pairs):
if pair[0] not in rnd_set and pair[1] not in rnd_set:
rnd_set.update(pair)
rnd.append(pair)
peeps.remove(pair[0])
peeps.remove(pair[1])
people_pairs.remove(pair)
if not peeps:
break
yield rnd
person_in_rnd la función person_in_rnd para reducir el tiempo perdido en las llamadas de función, y agregué una variable llamada rnd_set y peeps. rnd_set es un conjunto de todos en la ronda hasta el momento y se utiliza para verificar las coincidencias contra el par. peeps es un conjunto de personas copiadas, cada vez que agregamos un par a rnd eliminamos a esos individuos de peeps. Esto nos permite detener la iteración a través de todas las combinaciones una vez que peeps está vacío, es decir, una vez que todos están en una ronda.
Solo genero los índices (porque tengo problemas para encontrar 1000 nombres =), pero para 1000 números el tiempo de ejecución es de aproximadamente 4 segundos.
El principal problema de todos los otros enfoques: usan pares y trabajan con ellos, hay muchos pares y el tiempo de ejecución se hace mucho más largo. Mi enfoque difiere en trabajar con personas, no en parejas. Tengo un dict() que asigna a la persona a la lista de otras personas que tiene que cumplir, y estas listas tienen un máximo de N elementos (no N ^ 2, como con los pares). De ahí el ahorro de tiempo.
#!/usr/bin/env python
from itertools import combinations
from collections import defaultdict
pairs = combinations( range(6), 2 )
pdict = defaultdict(list)
for p in pairs :
pdict[p[0]].append( p[1] )
while len(pdict) :
busy = set()
print ''-----''
for p0 in pdict :
if p0 in busy : continue
for p1 in pdict[p0] :
if p1 in busy : continue
pdict[p0].remove( p1 )
busy.add(p0)
busy.add(p1)
print (p0, p1)
break
# remove empty entries
pdict = { k : v for k,v in pdict.items() if len(v) > 0 }
''''''
output:
-----
(0, 1)
(2, 3)
(4, 5)
-----
(0, 2)
(1, 3)
-----
(0, 3)
(1, 2)
-----
(0, 4)
(1, 5)
-----
(0, 5)
(1, 4)
-----
(2, 4)
(3, 5)
-----
(2, 5)
(3, 4)
''''''
Tal vez me esté perdiendo algo (no del todo raro) pero esto suena como un simple torneo de round-robin, donde cada equipo juega con cada otro equipo exactamente una vez.
Hay O (n ^ 2) métodos para manejar esto "a mano", que funcionan "por máquina" muy bien. Se puede encontrar una buena descripción en el artículo de Wikipedia sobre los torneos Round-Robin .
Acerca de O (n ^ 2): Habrá n-1 o n rondas, cada una de las cuales requerirá pasos O (n) para rotar todas las entradas excepto una de la tabla y O (n) para enumerar las n//2 coincidencias en cada redondo. Puede realizar la rotación O (1) utilizando listas con doble enlace, pero la enumeración de las coincidencias sigue siendo O (n). Entonces O (n) * O (n) = O (n ^ 2).