Tengo una lista de opciones posibles: [[1], [2, 4], [4], [5, 6, 2], [5, 3]] .
Quiero enumerar todas las combinaciones, tomando como máximo un elemento de cada sublista, sin repetir elementos.
Entonces [1, 2, 4, 5, 3] es una opción válida. Pero [1, 4, 4, 5, 3] no lo es. Permito no hacer una elección en ninguna sublista, por lo que [1,4, None,5,3] es válido, como en [1, None, None, None, None] y [None, None, None, None, None] .
No puedo simplemente enumerar todas las combinaciones y luego filtrar las que no quiero, ya que para una gran lista de posibles opciones, rápidamente se volvería computacionalmente inviable (estoy viendo 25 ^ 25 combinaciones máximas en mi proyecto).
editar: también aplicaría algunos criterios adicionales a los resultados, como filtrar para tener no más de un umbral de opciones de None , u ordenar la lista resultante de combinaciones en orden de combinaciones con menos opciones de None .
editar: con detalles del caso de la vida real: me gustaría aplicarlo a una lista de 25 sublistas, cada una de las cuales puede tener 1-25 elementos. De manera realista, cada sublista tendrá un máximo de 15 elementos, con 2-4 en promedio.
Entonces, la solución fácil de list(itertools.product(*choices)) luego filtrar está fuera.
También es posible que desee agregar otras condiciones de filtro a la lista de combinaciones, por lo que idealmente puedo filtrarlas por adelantado.
Intenté construir un árbol de forma recursiva, donde, por ejemplo, el nodo raíz tiene la lista completa de opciones, el nodo secundario toma la primera opción [1] y tiene una lista actualizada de opciones donde '1' se elimina de todas las listas [1:] opciones
Sin embargo, luchando por implementar la recursividad.
¿Me pueden ayudar con otros enfoques?
Otra forma de generar todas las salidas válidas con un uso mínimo de memoria es iterar sobre los elementos en lugar de sobre las listas. Utilice una búsqueda primero en profundidad para que solo genere resultados válidos desde el principio. Esto significa que debemos realizar un seguimiento de tres cosas en cada nivel de nuestro DFS: el elemento actual que quizás se agregue, las listas que ya se usan y el orden en que usamos esas listas anteriores.
Para ayudar con nuestra búsqueda, preprocesamos las opciones asignando cada elemento a un conjunto de listas posibles en las que puede estar, lo que crea una especie de versión dual del problema. Esto también genera las listas en orden de "máximo de opciones no vacías primero".
Dado que especificó que la cantidad de elementos únicos, N, es igual a la cantidad de listas, este enfoque se ejecuta en O(N * |output|) , y usamos generadores en todas partes para ahorrar memoria.
import collections from typing import Dict, Generator, List, Optional, Set choices = [[1], [2, 4], [4], [5, 6, 2], [5, 3]] element_to_containing_lists: Dict[int, Set[int]] = collections.defaultdict(set) for i, choice_list in enumerate(choices): for x in choice_list: element_to_containing_lists[x].add(i) all_unique_elements = sorted(element_to_containing_lists) def dfs(used_list_indices: Set[int], next_element_index: int, used_list_ordered_indices: List[Optional[int]]) -> Generator[List[Optional[int]]]: if next_element_index == len(all_unique_elements): yield used_list_ordered_indices else: # If we use the element, find an unused list index for possible_list_to_use in element_to_containing_lists[ all_unique_elements[next_element_index]] - used_list_indices: yield from dfs(used_list_indices | {possible_list_to_use}, next_element_index + 1, used_list_ordered_indices + [possible_list_to_use]) # If we don't use the element: Add None as a sentinel value yield from dfs(used_list_indices, next_element_index + 1, used_list_ordered_indices + [None]) for element_to_used_list in dfs(set(), 0, []): list_to_chosen_element = ['N'] * len(choices) for x, y in zip(all_unique_elements, element_to_used_list): if y is not None: list_to_chosen_element[y] = x print(*list_to_chosen_element, sep=' ')Primeras 10 líneas de la salida:
1 2 4 5 3 1 2 4 6 3 1 2 4 N 3 1 2 N 5 3 1 2 N 6 3 1 2 NN 3 1 2 4 5 N 1 2 4 6 5 1 2 4 N 5 Posiblemente, esto se puede optimizar para ejecutarse en tiempo O(|output|) mediante el uso de una máscara de bits para 'listas usadas' en lugar de un conjunto de sus índices.
No conviertas el resultado en una lista. product es un generador. Usa eso a tu favor. filter también es un generador. Solo tienes una combinación en la memoria de esta manera. A veces, una única salida de product se descartará internamente sin que usted la vea, pero no ocupará espacio adicional.
def criterion(x): k = [i for i in x if i is not None] return len(k) == len(set(k)) choices = [[1], [2, 4], [4], [5, 6, 2], [5, 3]] for c in choices: c.append(None) filter(criterion, product(*choices))Muy similar a la respuesta anterior. No tan rápido, pero creo que es más fácil de entender. Una implementación recursiva simple.
def pick_all(choices): # The result on an empty choices list is just a single empty list if not choices: yield [] return # Pluck off the first choice first_choice, *remainder = choices # Recursively find all solutions to the smaller problem. for result in pick_all(remainder): # We can always add None to the front yield [None, *result] for item in first_choice: # And we can add any item in this choice that's not already there. if item not in result: yield [item, *result]