Me gustaría generar una lista de combinaciones. Intentaré simplificar mi problema para que sea comprensible.
Tenemos 3 variables:
Me gustaría generar usando python una lista de todas las combinaciones posibles, sin ningún duplicado sabiendo que: no me importa el orden de los grupos y el orden de las letras dentro de un grupo.
Como ejemplo, con x = 4, k = 2, n = 2:
# we start with 4 letters, we want to make 2 groups of 2 letters letters = ['A','B','C','D'] # here would be a code that generate the list # Here is the result that is very simple, only 3 combinations exist. combos = [ ['AB', 'CD'], ['AC', 'BD'], ['AD', 'BC'] ] Dado que no me importa el orden de los grupos o dentro de ellos, y las letras dentro de un grupo, ['AB', 'CD'] y ['DC', 'BA'] son un duplicado.
Esta es una simplificación de mi problema real, que tiene esos valores: x = 12 , k = 4 , n = 3 . Traté de usar algunas funciones de itertools , pero con tantas letras mi computadora se congela porque son demasiadas combinaciones.
Otra forma de ver el problema: tienes 12 jugadores, quieres hacer 4 equipos de 3 jugadores. ¿Cuáles son todas las posibilidades?
¿Alguien podría ayudarme a encontrar una solución optimizada para generar esta lista?
En primer lugar, puede usar una lista de comprensión para obtener todas las combinaciones posibles (independientemente de los duplicados):
comb = [(a,b) for a in letters for b in letters if a != b]Y, después, puede usar la función sorted para ordenar las tuplas. Después de eso, para eliminar los duplicados, puede convertir todos los elementos en un conjunto y luego volver a una lista.
var = [tuple(sorted(sub)) for sub in comb] var = list(set(var))Usar combinación de itertools
from itertools import combinations x = list(combinations(['A','B','C','D'],2)) t = [] for i in (x): t.append(i[0]+i[1]) # concatenating the strings and adding in a list g = [] for i in range(0,len(t),2): for j in range(i+1,len(t)): g.append([t[i],t[j]]) break print(g)Podría usar el enfoque de comprensión de listas, que tiene una complejidad de tiempo de O(n*n-1), o podría usar una forma más detallada, pero con una complejidad de tiempo ligeramente mejor de O(n^2-n)/2 :
comb = [] for first_letter_idx, _ in enumerate(letters): for sec_letter_idx in range(first_letter_idx + 1, len(letters)): comb.append(letters[first_letter_idx] + letters[sec_letter_idx]) print(comb) comb2 = [] for first_letter_idx, _ in enumerate(comb): for sec_letter_idx in range(first_letter_idx + 1, len(comb)): if (comb[first_letter_idx][0] not in comb[sec_letter_idx] and comb[first_letter_idx][1] not in comb[sec_letter_idx]): comb2.append([comb[first_letter_idx], comb[sec_letter_idx]]) print(comb2)Este algoritmo necesita más trabajo para manejar entradas dinámicas. Tal vez con recursividad.
Ciertamente habrá formas más sofisticadas/eficientes de hacer esto, pero aquí hay un enfoque que funciona en una cantidad de tiempo razonable para su ejemplo y debería ser lo suficientemente fácil de adaptar para otros casos.
Genera equipos únicos y combinaciones únicas de los mismos, según sus especificaciones.
from itertools import combinations # this assumes that team_size * team_num == len(players) is a given team_size = 3 team_num = 4 players = list('ABCDEFGHIJKL') unique_teams = [set(c) for c in combinations(players, team_size)] def duplicate_player(combo): """Returns True if a player occurs in more than one team""" return len(set.union(*combo)) < len(players) result = (combo for combo in combinations(unique_teams, team_num) if not duplicate_player(combo)) result es un generador que se puede iterar o convertir en una lista con list(result) . En kaggle.com, lleva aproximadamente un minuto generar la lista completa de todas las combinaciones posibles (un total de 15400, de acuerdo con los cálculos de @beaker y @John Coleman en los comentarios). Los equipos son tuplas de conjuntos que se ven así:
[({'A', 'B', 'C'}, {'D', 'E', 'F'}, {'G', 'H', 'I'}, {'J', 'K', 'L'}), ({'A', 'B', 'C'}, {'D', 'E', 'F'}, {'G', 'H', 'J'}, {'I', 'K', 'L'}), ({'A', 'B', 'C'}, {'D', 'E', 'F'}, {'G', 'H', 'K'}, {'I', 'J', 'L'}), ... ] Si lo desea, puede convertirlos en cadenas llamando a ''.join() en cada uno de ellos.
Otra solución (los jugadores están numerados 0, 1, ...):
import itertools def equipartitions(base_count: int, group_size: int): if base_count % group_size != 0: raise ValueError("group_count must divide base_count") return set(_equipartitions(frozenset(range(base_count)), group_size)) def _equipartitions(base_set: frozenset, group_size: int): if not base_set: yield frozenset() for combo in itertools.combinations(base_set, group_size): for rest in _equipartitions(base_set.difference(frozenset(combo)), group_size): yield frozenset({frozenset(combo), *rest}) all_combinations = [ [tuple(team) for team in combo] for combo in equipartitions(12, 3) ] print(all_combinations) print(len(all_combinations))Y otro:
import itertools from typing import Iterable def equipartitions(players: Iterable, team_size: int): if len(players) % team_size != 0: raise ValueError("group_count must divide base_count") return _equipartitions(set(players), team_size) def _equipartitions(players: set, team_size: int): if not players: yield [] return first_player, *other_players = players for other_team_members in itertools.combinations(other_players, team_size-1): first_team = {first_player, *other_team_members} for other_teams in _equipartitions(set(other_players) - set(first_team), team_size): yield [first_team, *other_teams] all_combinations = [ {''.join(sorted(team)) for team in combo} for combo in equipartitions(players='ABCDEFGHIJKL', team_size=3) ] print(all_combinations) print(len(all_combinations))