Escoger combinaciones desordenadas de grupos con superposición

Tengo grupos de valores y me gustaría generar cada combinación desordenada posible seleccionando de ciertos grupos.

Por ejemplo, quise elegir entre el grupo 0, el grupo 0 y el grupo 1:

>>> pools = [[1, 2, 3], [2, 3, 4], [3, 4, 5]] >>> part = (0, 0, 1) >>> list(product(*(pools[i] for i in part))) [(1, 1, 2), (1, 1, 3), (1, 1, 4), (1, 2, 2), (1, 2, 3), (1, 2, 4), (1, 3, 2), (1, 3, 3), (1, 3, 4), (2, 1, 2), (2, 1, 3), (2, 1, 4), (2, 2, 2), (2, 2, 3), (2, 2, 4), (2, 3, 2), (2, 3, 3), (2, 3, 4), (3, 1, 2), (3, 1, 3), (3, 1, 4), (3, 2, 2), (3, 2, 3), (3, 2, 4), (3, 3, 2), (3, 3, 3), (3, 3, 4)] 

Esto genera todas las combinaciones posibles seleccionando del grupo 0, grupo 0 y grupo 1.

Sin embargo, el orden no me importa, así que muchas de las combinaciones son en realidad duplicados. Por ejemplo, como utilicé un producto cartesiano, se generan tanto (1, 2, 4) como (2, 1, 4) .

Se me ocurrió un método simple para mitigar este problema. Para los miembros elegidos de un solo grupo, selecciono sin ordenar usando combinations_with_replacement . Cuento cuántas veces quiero dibujar de cada grupo. El código se ve así:

     cnt = Counter() for ind in part: cnt[ind] += 1 blocks = [combinations_with_replacement(pools[i], cnt[i]) for i in cnt] return [list(chain(*combo)) for combo in product(*blocks)] 

    Esto reduce los pedidos duplicados si tengo que elegir el mismo grupo varias veces. Sin embargo, todas las agrupaciones tienen una gran cantidad de superposición, y el uso de combinations_with_replacement en múltiples agrupaciones fusionadas generaría algunas combinaciones no válidas. ¿Existe un método más eficiente para generar combinaciones desordenadas?

    Edición: Información adicional sobre las entradas: El número de partes y grupos es pequeño (~ 5 y ~ 20) y, para simplificar, cada elemento es un entero. El problema real que ya resolví, así que esto es solo por interés académico. Digamos que hay miles de enteros en cada grupo, pero algunos grupos son pequeños y solo tienen docenas. Así que algún tipo de unión o intersección parece ser el camino a seguir.

    Esto no es “una respuesta” sino tanto un estímulo para pensar más 😉 Para concretar, envolveré el código del OP, ligeramente reflejado, en una función que también elimina duplicados:

     def gen(pools, ixs): from itertools import combinations_with_replacement as cwr from itertools import chain, product from collections import Counter assert all(0 <= i < len(pools) for i in ixs) seen = set() cnt = Counter(ixs) # map index to count blocks = [cwr(pools[i], count) for i, count in cnt.items()] for t in product(*blocks): t = tuple(sorted(chain(*t))) if t not in seen: seen.add(t) yield t 

    No temo que se clasifique aquí: es eficiente en memoria, y para tuplas pequeñas es probablemente más rápido que todos los gastos generales involucrados en la creación de un objeto Counter .

    Pero independientemente de eso, el punto aquí es enfatizar el valor real que obtuvo el OP mediante la reformulación del problema para usar combinations_with_replacement ( cwr ). Considere estas entradas:

     N = 64 pools = [[0, 1]] ixs = [0] * N 

    Solo hay 65 resultados únicos, y la función los genera instantáneamente, sin duplicados internos. Por otro lado, lo esencialmente idéntico.

     pools = [[0, 1]] * N ixs = range(N) 

    también tiene los mismos 65 resultados únicos, pero esencialmente se ejecuta para siempre (como lo harían, por ejemplo, las otras respuestas que se han dado hasta ahora), a través de 2 ** 64 posibilidades. cwr no ayuda aquí porque cada índice de grupo aparece solo una vez.

    Por lo tanto, hay un espacio astronómico para mejorar sobre cualquier solución que "simplemente" elimine los duplicados de un producto cartesiano completo, y parte de eso se puede ganar haciendo lo que el OP ya hizo.

    Me parece que el enfoque más prometedor sería escribir un generador personalizado (no uno que se base principalmente en itertools funciones de itertools ) que generara todas las posibilidades en un orden lexicográfico para comenzar (por lo tanto, por construcción, no se crearían duplicados para comenzar). Pero eso requiere un análisis "global" de los grupos de entrada primero, y el código que comencé rápidamente se hizo más complejo de lo que puedo hacer ahora para luchar.

    Una basada en la respuesta de @ user2357112

    La combinación de cwr con la desduplicación incremental de @ user2357112 proporciona un breve algoritmo que se ejecuta rápidamente en todos los casos de prueba que tengo. Por ejemplo, es esencialmente instantáneo para ambos deletreos de [0, 1] ** 64 ejemplos anteriores, y ejecuta el ejemplo al final de la respuesta de @Joseph Wood aproximadamente tan rápido como dijo que corrió su código C ++ (0,35 segundos en mi caja bajo Python 3.7.0 y, sí, se encontraron 162295 resultados):

     def gen(pools, ixs): from itertools import combinations_with_replacement as cwr from collections import Counter assert all(0 <= i < len(pools) for i in ixs) result = {()} for i, count in Counter(ixs).items(): result = {tuple(sorted(old + new)) for new in cwr(pools[i], count) for old in result} return result 

    Para que a los demás pitonistas les resulte más fácil probar el último ejemplo, aquí está la entrada como ejecutable de Python:

     pools = [[1, 10, 14, 6], [7, 2, 4, 8, 3, 11, 12], [11, 3, 13, 4, 15, 8, 6, 5], [10, 1, 3, 2, 9, 5, 7], [1, 5, 10, 3, 8, 14], [15, 3, 7, 10, 4, 5, 8, 6], [14, 9, 11, 15], [7, 6, 13, 14, 10, 11, 9, 4]] ixs = range(len(pools)) 

    Sin embargo, la OP luego agregó que típicamente tienen alrededor de 20 grupos, cada uno con algunos miles de elementos. 1000 ** 20 = 1e60 está fuera del scope práctico para cualquier enfoque que construya el producto cartesiano completo, sin importar lo inteligente que elimine los duplicados. Sin embargo, queda claro como barro cuántos esperan que se dupliquen, así como claro como barro si este tipo de "desduplicación incremental" es lo suficientemente bueno como para ser práctico.

    Lo ideal sería tener un generador que produjera un resultado a la vez, en orden lexicográfico.

    Generación lexicográfica perezosa de una en una.

    Sobre la base de la deduplicación incremental, suponga que tenemos una secuencia estrictamente creciente (lexicográfica) de tuplas ordenadas, agregue la misma tupla T a cada una y clasifíquelas de nuevo. Entonces la secuencia derivada sigue en orden estrictamente creciente. Por ejemplo, en la columna de la izquierda tenemos los 10 pares únicos del range(4) , y en la columna de la derecha lo que sucede después de agregar (y ordenar de nuevo) 2 a cada uno:

     00 002 01 012 02 022 03 023 11 112 12 122 13 123 22 222 23 223 33 233 

    Comenzaron en orden ordenado, y los triples derivados también están ordenados. Saltaré la prueba fácil (croquis: si t1 y t2 son tuplas adyacentes, t1 < t2 , y dejaré que i sea ​​el índice más pequeño de manera que t1[i] != t2[i] . Luego t1[i] < t2[i] (lo que significa "lexicográfico <"). Luego, si lanza x en ambas tuplas, proceda por los casos: es x <= t1[i] ? entre t1[i] y t2[i] ? es x >= t2[i] ? En cada caso, es fácil ver que la primera tupla derivada es estrictamente menor que la segunda tupla derivada.

    Entonces, suponiendo que tenemos un result de secuencia ordenada de todas las tuplas clasificadas únicas de un número determinado de grupos, ¿qué sucede cuando agregamos elementos de un grupo P nuevo en las tuplas? Bueno, como arriba,

     [tuple(sorted(old + (P[0],))) for old in result] 

    también se ordena, y así es

     [tuple(sorted(old + (P[i],))) for old in result] 

    para todos los i en range(len(P)) . Estas secuencias garantizadas ya ordenadas se pueden combinar a través de heapq.merge() , y otro generador ( killdups() continuación) se ejecuta en el resultado de la fusión para eliminar los duplicados sobre la marcha. No es necesario, por ejemplo, mantener un conjunto de todas las tuplas vistas hasta ahora. Debido a que la salida de la combinación no disminuye, es suficiente solo para verificar si el próximo resultado es el mismo que la salida del último resultado.

    Hacer que esto funcione perezosamente es delicado. Cada uno de los elementos de la nueva agrupación que se está agregando debe acceder a la secuencia del resultado tan lejano, pero no queremos materializar todo de una sola vez. En itertools.tee() lugar, itertools.tee() permite que cada elemento de la siguiente agrupación atraviese la secuencia del resultado hasta ahora a su propio ritmo, y libera automáticamente la memoria para cada elemento de resultado una vez que todos los nuevos elementos de la agrupación hayan terminado con ella.

    La función build1() (o algún trabajo) es necesaria para garantizar que se acceda a los valores correctos en el momento adecuado. Por ejemplo, si el cuerpo de build1() se pega en línea donde se llama, el código fallará espectacularmente (el cuerpo rcopy a los valores finales vinculados a rcopy y new lugar de a los que estaban vinculados en el momento en que se encontraba la expresión del generador creado).

    En total, por supuesto, esto es algo más lento, debido a las capas de llamadas de generador retrasadas y las combinaciones de stacks. A cambio, devuelve los resultados en orden lexicográfico, puede comenzar a entregar resultados muy rápidamente y tiene una carga de memoria máxima más baja si, por ninguna otra razón, no se materializa la secuencia del resultado final (se hace poco hasta que la persona que llama se repite) el generador devuelto).

    Nota técnica: no sorted() miedo sorted() aquí. El agregado se realiza a través de old + new por una razón: old ya está ordenado, y new es típicamente 1-tuple. La clasificación de Python es de tiempo lineal en este caso, no O(N log N) .

     def gen(pools, ixs): from itertools import combinations_with_replacement as cwr from itertools import tee from collections import Counter from heapq import merge def killdups(xs): last = None for x in xs: if x != last: yield x last = x def build1(rcopy, new): return (tuple(sorted(old + new)) for old in rcopy) assert all(0 <= i < len(pools) for i in ixs) result = [()] for i, count in Counter(ixs).items(): poolelts = list(cwr(pools[i], count)) xs = [build1(rcopy, new) for rcopy, new in zip(tee(result, len(poolelts)), poolelts)] result = killdups(merge(*xs)) return result 

    2 entradas

    Resulta que para el caso de 2 entradas, hay un enfoque fácil derivado del conjunto de álgebra. Si x y y son iguales, cwr(x, 2) es la respuesta. Si x e y son desunidos, product(x, y) . De lo contrario, la intersección c de x e y no está vacía, y la respuesta es la clasificación de 4 productos cruzados obtenidos de los 3 conjuntos desunidos por pares c , xc e yc : cwr(c, 2) , product(xc, c) , product(yc, c) y product(xc, yc) . La prueba es directa pero tediosa, así que la omitiré. Por ejemplo, no hay duplicados entre cwr(c, 2) y product(xc, c) porque cada tupla en el último contiene un elemento de xc , pero cada tupla en el primero contiene elementos solo de c , y xc y c son desunión por construcción. No hay duplicados dentro del product(xc, yc) porque las dos entradas son desunidas (si contuvieran un elemento en común, eso habría estado en la intersección de x e y , contradiciendo que xc no tiene ningún elemento en la intersección). Etc.

    Por desgracia, no he encontrado una manera de generalizar esto más allá de 2 entradas, lo que me sorprendió. Se puede utilizar por sí solo, o como un bloque de construcción en otros enfoques. Por ejemplo, si hay muchas entradas, se pueden buscar pares con intersecciones grandes, y este esquema de 2 entradas se puede usar para hacer esas partes de los productos generales directamente.

    Incluso con solo 3 entradas, no me queda claro cómo obtener el resultado correcto para

     [1, 2], [2, 3], [1, 3] 

    El producto cartesiano completo tiene 2 ** 3 = 8 elementos, solo uno de los cuales se repite: (1, 2, 3) aparece dos veces (como (1, 2, 3) y nuevamente como (2, 3, 1) ). Cada par de entradas tiene una intersección de 1 elemento, pero la intersección de las 3 está vacía.

    Aquí hay una implementación:

     def pair(x, y): from itertools import product, chain from itertools import combinations_with_replacement x = set(x) y = set(y) c = x & y chunks = [] if c: x -= c y -= c chunks.append(combinations_with_replacement(c, 2)) if x: chunks.append(product(x, c)) if y: chunks.append(product(y, c)) if x and y: chunks.append(product(x, y)) return chain.from_iterable(chunks) 

    Una prueba de concepto basada en el emparejamiento máximo

    Esto combina ideas del bosquejo de @ Leon y un enfoque de @JosephWoods esbozado en comentarios. No está pulido y, obviamente, puede acelerarse, pero es bastante rápido en todos los casos que intenté. Debido a que es bastante complejo, ¡probablemente sea más útil publicarlo en una forma no lo suficientemente difícil de seguir de todos modos!

    Esto no hace ningún bash de determinar el conjunto de grupos "libres" (como en el bosquejo de @ Leon). Principalmente porque no tenía un código para eso, y en parte porque no estaba claro de inmediato cómo hacerlo de manera eficiente. Tenía un código para encontrar una coincidencia en un gráfico bipartito, que solo requería algunos cambios para usar en este contexto.

    Entonces, esto prueba los prefijos de resultados plausibles en orden lexicográfico, como en el bosquejo de @JosephWood, y para cada uno ve si en realidad es posible construirlo verificando si existe una coincidencia de gráfico bipartito.

    Entonces, aunque los detalles del boceto de @ Leon no están implementados en gran parte aquí, los comportamientos visibles son muy similares: produce resultados en orden lexicográfico, no necesita verificar duplicados, es un generador perezoso, el uso máximo de memoria es proporcional al Suma de las longitudes de las agrupaciones, obviamente puede ser paralelizada de muchas maneras (establecer diferentes procesos para trabajar en diferentes regiones del espacio de resultados), y la clave para hacerlo mucho más rápido radica en reducir las cantidades masivas de trabajo redundante realizado por la función de comparación de gráficos (una gran parte de lo que hace en cada llamada simplemente reproduce lo que hizo en la llamada anterior).

     def matchgen(pools, ixs): from collections import Counter from collections import defaultdict from itertools import chain, repeat, islice elt2pools = defaultdict(set) npools = 0 for i, count in Counter(ixs).items(): set_indices = set(range(npools, npools + count)) for elt in pools[i]: elt2pools[elt] |= set_indices npools += count elt2count = {elt : len(ps) for elt, ps in elt2pools.items()} cands = sorted(elt2pools.keys()) ncands = len(cands) result = [None] * npools # Is it possible to match result[:n] + [elt]*count? # We already know it's possible to match result[:n], but # this code doesn't exploit that. def match(n, elt, count): def extend(x, seen): for y in elt2pools[x]: if y not in seen: seen.add(y) if y in y2x: if extend(y2x[y], seen): y2x[y] = x return True else: y2x[y] = x return True return False y2x = {} freexs = [] # A greedy pass first to grab easy matches. for x in chain(islice(result, n), repeat(elt, count)): for y in elt2pools[x]: if y not in y2x: y2x[y] = x break else: freexs.append(x) # Now do real work. seen = set() for x in freexs: seen.clear() if not extend(x, seen): return False return True def inner(i, j): # fill result[j:] with elts from cands[i:] if j >= npools: yield tuple(result) return for i in range(i, ncands): elt = cands[i] # Find the most times `elt` can be added. count = min(elt2count[elt], npools - j) while count: if match(j, elt, count): break count -= 1 # Since it can be added `count` times, it can also # be added any number of times less than `count`. for k in range(count): result[j + k] = elt while count: yield from inner(i + 1, j + count) count -= 1 return inner(0, 0) 

    EDITAR: tenga en cuenta que hay una trampa potencial aquí, ilustrada por el par de range(10_000) de grupos range(10_000) y range(100_000) . Después de producir (9999, 99999) , la primera posición se incrementa a 10000, y luego continúa por mucho tiempo, deduciendo que no hay ninguna coincidencia para ninguna de las posibilidades en 10001 .. 99999 en la segunda posición; y luego para 10001 en la primera posición no hay coincidencia para ninguna de las posibilidades en 10002 .. 99999 en la segunda posición; y así. El esquema de range(10_000) , en cambio, habría notado que el range(10_000) era el único grupo libre que quedaba después de haber elegido 10000 en la primera posición, y notó al mismo tiempo que el range(10_000) no contiene ningún valor superior a 10000. Al parecer, necesitaría para hacer eso otra vez por 10001, 10002, ..., 99999 en la primera posición. Eso es un desperdicio de ciclos de tiempo lineal en lugar de tiempo cuadrático, pero un desperdicio de todos modos. La moraleja de la historia: no confíe en nada hasta que tenga el código real que debe probar 😉

    Y uno basado en el esquema de @ Leon

    A continuación hay una implementación más fiel que las ideas de @ Leon. Me gusta el código mejor que mi código de "prueba de concepto" (POC) justo arriba, pero me sorprendió descubrir que el nuevo código funciona significativamente más lento (un factor de 3 a 4 veces más lento en una variedad de casos similares a los de @ JospephWood's randomized Ejemplo) relativo a una variante comparativamente "optimizada" del código POC.

    La razón principal parece ser más llamadas a la función correspondiente. El código POC lo llamó una vez por el prefijo "plausible". El nuevo código no genera prefijos imposibles, pero para cada prefijo que genera es posible que deba realizar varias llamadas de match() para determinar el conjunto posiblemente más pequeño de grupos libres que quedan. Tal vez haya una forma más inteligente de hacerlo.

    Tenga en cuenta que agregué un giro: si los elementos de un grupo libre son todos más pequeños que el último elemento del prefijo hasta ahora, sigue siendo "un grupo libre" con respecto al prefijo, pero es inútil porque ninguno de sus elementos puede aparecer en el los candidatos Esto no es importante para el resultado, pero significa que el grupo permanece en el conjunto de grupos libres para todas las llamadas recursivas restantes, lo que a su vez significa que pueden perder tiempo determinando que aún es un "grupo libre". Entonces, cuando un grupo libre ya no se puede usar para nada, esta versión lo elimina del conjunto de grupos libres. Esto dio una aceleración significativa.

    Nota: hay muchas formas de probar la coincidencia, algunas de las cuales tienen un mejor comportamiento teórico en el peor de los casos. En mi experiencia, la búsqueda simple primero en profundidad (como aquí) se ejecuta más rápido en la vida real en casos típicos. Pero depende mucho de las características de cómo se ven los gráficos "típicos" en la aplicación en cuestión. No he probado otras formas aquí.

    Líneas de fondo, ignorando el código de caso especial "2 entradas":

    • Nada aquí supera la desduplicación incremental de la velocidad, si tiene la memoria RAM. Pero nada es peor que eso para la carga máxima de memoria.

    • Nada supera los enfoques basados ​​en la coincidencia para la carga de la memoria frugal. Están en un universo completamente diferente en esa medida. También son los más lentos, aunque al menos en el mismo universo 😉

    El código:

     def matchgen(pools, ixs): from collections import Counter from collections import defaultdict from itertools import islice elt2pools = defaultdict(list) allpools = [] npools = 0 for i, count in Counter(ixs).items(): indices = list(range(npools, npools + count)) plist = sorted(pools[i]) for elt in plist: elt2pools[elt].extend(indices) for i in range(count): allpools.append(plist) npools += count pools = allpools assert npools == len(pools) result = [None] * npools # Is it possible to match result[:n] not using pool # bady? If not, return None. Else return a matching, # a dict whose keys are pool indices and whose values # are a permutation of result[:n]. def match(n, bady): def extend(x, seen): for y in elt2pools[x]: if y not in seen: seen.add(y) if y not in y2x or extend(y2x[y], seen): y2x[y] = x return True return False y2x = {} freexs = [] # A greedy pass first to grab easy matches. for x in islice(result, n): for y in elt2pools[x]: if y not in y2x and y != bady: y2x[y] = x break else: freexs.append(x) # Now do real work. for x in freexs: if not extend(x, {bady}): return None return y2x def inner(j, freepools): # fill result[j:] from bisect import bisect_left if j >= npools: yield tuple(result) return if j: new_freepools = set() allcands = set() exhausted = set() # free pools with elts too small atleast = result[j-1] for pi in freepools: if pi not in new_freepools: m = match(j, pi) if not m: # match must use pi continue # Since `m` is a match to result[:j], # any pool in freepools it does _not_ # use must still be free. new_freepools |= freepools - m.keys() assert pi in new_freepools # pi is free with respect to result[:j]. pool = pools[pi] if pool[-1] < atleast: exhausted.add(pi) else: i = bisect_left(pool, atleast) allcands.update(pool[i:]) if exhausted: freepools -= exhausted new_freepools -= exhausted else: # j == 0 new_freepools = freepools allcands = elt2pools.keys() for result[j] in sorted(allcands): yield from inner(j + 1, new_freepools) return inner(0, set(range(npools))) 

    Nota: esto tiene sus propias clases de "casos malos". Por ejemplo, pasar 128 copias de [0, 1] consume aproximadamente 2 minutos (!) De tiempo en mi caja para encontrar los 129 resultados. El código POC toma menos de un segundo, mientras que algunos de los enfoques no coincidentes parecen instantáneos.

    No voy a entrar en detalles sobre por qué. Basta con decir que debido a que todas las piscinas son iguales, todas siguen siendo "piscinas libres" sin importar cuán profunda sea la recursión. match() nunca tiene dificultades, siempre encuentra una coincidencia completa para el prefijo en su primer (codicioso) pase, pero incluso eso toma un tiempo proporcional al cuadrado de la longitud del prefijo actual (== la profundidad de recursión actual).

    Híbrido pragmático

    Una más aquí. Como se señaló anteriormente, los enfoques basados ​​en emparejamientos sufren parte del costo de la comparación de gráficos como una operación fundamental que se repite con tanta frecuencia, y tienen algunos casos desafortunados que son muy fáciles de encontrar.

    Los grupos altamente similares hacen que el conjunto de grupos libres se reduzca lentamente (o no lo haga). Pero en ese caso, las agrupaciones son tan similares que rara vez importa de qué agrupación se extrae un elemento. Por lo tanto, el enfoque a continuación no trata de mantener un registro exacto de los grupos libres, selecciona grupos arbitrarios siempre que estén disponibles, y recurre a la comparación de gráficos solo cuando se atasca. Eso parece funcionar bien. Como ejemplo extremo, los 129 resultados de 128 [0, 1] grupos se entregan en menos de una décima de segundo en lugar de en dos minutos. Resulta que nunca se necesita hacer una comparación de gráficos en ese caso.

    Otro problema con el código POC (y menos para el otro enfoque basado en el partido) fue la posibilidad de girar las ruedas durante mucho tiempo después de que se entregó el último resultado. Un truco pragmático resuelve ese problema completamente 😉 La última tupla de la secuencia se calcula fácilmente de antemano, y el código genera una excepción interna para terminar todo inmediatamente después de que se entregue la última tupla.

    Eso es todo para mí! Una generalización del caso de "dos entradas" seguiría siendo muy interesante para mí, pero ahora se han eliminado todas las picazones que recibí de los otros enfoques.

     def combogen(pools, ixs): from collections import Counter from collections import defaultdict from itertools import islice elt2pools = defaultdict(set) npools = 0 cands = [] MAXTUPLE = [] for i, count in Counter(ixs).items(): indices = set(range(npools, npools + count)) huge = None for elt in pools[i]: elt2pools[elt] |= indices for i in range(count): cands.append(elt) if huge is None or elt > huge: huge = elt MAXTUPLE.extend([huge] * count) npools += count MAXTUPLE = tuple(sorted(MAXTUPLE)) cands.sort() ncands = len(cands) ALLPOOLS = set(range(npools)) availpools = ALLPOOLS.copy() result = [None] * npools class Finished(Exception): pass # Is it possible to match result[:n]? If not, return None. Else # return a matching, a dict whose keys are pool indices and # whose values are a permutation of result[:n]. def match(n): def extend(x, seen): for y in elt2pools[x]: if y not in seen: seen.add(y) if y not in y2x or extend(y2x[y], seen): y2x[y] = x return True return False y2x = {} freexs = [] # A greedy pass first to grab easy matches. for x in islice(result, n): for y in elt2pools[x]: if y not in y2x: y2x[y] = x break else: freexs.append(x) # Now do real work. seen = set() for x in freexs: seen.clear() if not extend(x, seen): return None return y2x def inner(i, j): # fill result[j:] with cands[i:] nonlocal availpools if j >= npools: r = tuple(result) yield r if r == MAXTUPLE: raise Finished return restre_availpools = None last = None jp1 = j + 1 for i in range(i, ncands): elt = cands[i] if elt == last: continue last = result[j] = elt pools = elt2pools[elt] & availpools if pools: pool = pools.pop() # pick one - arbitrary availpools.remove(pool) else: # Find _a_ matching, and if that's possible fiddle # availpools to pretend that's the one we used all # along. m = match(jp1) if not m: # the prefix can't be extended with elt continue if restre_availpools is None: restre_availpools = availpools.copy() availpools = ALLPOOLS - m.keys() # Find a pool from which elt was taken. for pool, v in m.items(): if v == elt: break else: assert False yield from inner(i+1, jp1) availpools.add(pool) if restre_availpools is not None: availpools = restre_availpools try: yield from inner(0, 0) except Finished: pass 

    Este es un problema dificil. Creo que lo mejor que puedes hacer en el caso general es implementar una hash table en la que la clave sea un conjunto multiset y el valor sea tu combinación real. Esto es similar a lo que @ErikWolf mencionó, sin embargo, este método evita producir duplicados en primer lugar, por lo que no es necesario filtrar. También devuelve el resultado correcto cuando nos encontramos con multisets .

    Hay una solución más rápida que estoy molestando ahora, pero guardando para más adelante. Tengan paciencia conmigo.

    Como se mencionó en los comentarios, un enfoque que parece viable es combinar todos los grupos y simplemente generar combinaciones de este grupo combinado para elegir el número de grupos. Necesitaría una herramienta que sea capaz de generar combinaciones de multisets, que hay una que sé que está disponible en python . Está en la biblioteca from sympy.utilities.iterables import multiset_combinations . El problema con esto es que todavía producimos valores duplicados y, peor aún, producimos resultados que son imposibles de obtener con un set análogo y product combo de product . Por ejemplo, si tuviéramos que hacer algo como ordenar y combinar todos los grupos del OP y aplicar lo siguiente:

     list(multiset_permutations([1,2,2,3,3,4,4,5])) 

    Un par de los resultados serían [1 2 2] y [4 4 5] que son imposibles de obtener de [[1, 2, 3], [2, 3, 4], [3, 4, 5]] .

    Fuera de los casos especiales, no veo cómo es posible evitar revisar todos los productos posibles. Espero estar equivocado.

    Resumen de algoritmos
    La idea principal es mapear combinaciones de nuestro producto de vectores a combinaciones únicas sin tener que filtrar duplicados. El ejemplo dado por el OP (es decir, (1, 2, 3) y (1, 3, 2) ) solo debe asignarse a un valor (cualquiera de ellos, ya que el orden no importa). Notamos que los dos vectores son conjuntos idénticos. Ahora, también tenemos situaciones como:

     vec1 = (1, 2, 1) vec2 = (2, 1, 1) vec3 = (2, 2, 1) 

    Necesitamos que vec1 y vec2 al mismo valor, mientras que vec3 necesita vec3 a su propio valor. Este es el problema con los conjuntos, ya que todos estos son conjuntos equivalentes (con los conjuntos, los elementos son únicos, por lo que {a, b, b} y {a, b} son equivalentes).

    Aquí es donde entran las multisets . Con los conjuntos múltiples, (2, 2, 1) y (1, 2, 1) son distintos, sin embargo, (1, 2, 1) y (2, 1, 1) son iguales. Esto es bueno. Ahora tenemos un método para generar claves únicas.

    Como no soy un progtwigdor de python , procederé en C++ .

    Tendremos algunos problemas si intentamos implementar todo lo anterior exactamente como está. Que yo sepa, no puede tener std::multiset como la parte clave para un std::unordered_map . Sin embargo, podemos para un std::map . No tiene el mismo rendimiento que una tabla hash debajo (en realidad es un árbol rojo-negro ), pero aún así ofrece un rendimiento decente. Aquí está:

     void cartestionCombos(std::vector > v, bool verbose) { std::map, std::vector > cartCombs; unsigned long int len = v.size(); unsigned long int myProd = 1; std::vector s(len); for (std::size_t j = 0; j < len; ++j) { myProd *= v[j].size(); s[j] = v[j].size() - 1; } unsigned long int loopLim = myProd - 1; std::vector > res(myProd, std::vector()); std::vector myCounter(len, 0); std::vector value(len, 0); std::multiset key; for (std::size_t j = 0; j < loopLim; ++j) { key.clear(); for (std::size_t k = 0; k < len; ++k) { value[k] = v[k][myCounter[k]]; key.insert(value[k]); } cartCombs.insert({key, value}); int test = 0; while (myCounter[test] == s[test]) { myCounter[test] = 0; ++test; } ++myCounter[test]; } key.clear(); // Get last possible combination for (std::size_t k = 0; k < len; ++k) { value[k] = v[k][myCounter[k]]; key.insert(value[k]); } cartCombs.insert({key, value}); if (verbose) { int count = 1; for (std::pair, std::vector > element : cartCombs) { std::string tempStr; for (std::size_t k = 0; k < len; ++k) tempStr += std::to_string(element.second[k]) + ' '; std::cout << count << " : " << tempStr << std::endl; ++count; } } } 

    Con los casos de prueba de 8 vectores de longitudes de 4 a 8 llenos con enteros aleatorios de 1 a 15, el algoritmo anterior se ejecuta en aproximadamente 5 segundos en mi computadora. No está mal teniendo en cuenta que estamos viendo casi 2.5 millones de resultados totales de nuestro producto, pero podemos hacerlo mejor. ¿Pero cómo?

    El mejor rendimiento lo proporciona std::unordered_map con una clave que se construye en tiempo constante. Nuestra clave anterior está integrada en el tiempo logarítmico ( complejidad de multiset, mapa y hash map ). Entonces la pregunta es, ¿cómo podemos superar estos obstáculos?

    Mejor presentación

    Sabemos que debemos abandonar std::multiset . Necesitamos algún tipo de objeto que tenga una propiedad de tipo conmutativo a la vez que proporcione resultados únicos.

    Introduzca el teorema fundamental de la aritmética

    Establece que cada número puede representarse de manera única (hasta el orden de los factores) por el producto de números primos. Esto a veces se llama la descomposición principal.

    Así que ahora, simplemente podemos proceder como antes, pero en lugar de construir un conjunto múltiple, asignamos cada índice a un número primo y multiplicamos el resultado. Esto nos dará una constante construcción de tiempo para nuestra llave. Aquí hay un ejemplo que muestra el poder de esta técnica en los ejemplos que creamos anteriormente (NB P debajo es una lista de números primos ... (2, 3, 5, 7, 11, etc.)

      Maps to Maps to product vec1 = (1, 2, 1) -->> P[1], P[2], P[1] --->> 3, 5, 3 -->> 45 vec2 = (2, 1, 1) -->> P[2], P[1], P[1] --->> 5, 3, 3 -->> 45 vec3 = (2, 2, 1) -->> P[2], P[2], P[1] --->> 5, 5, 3 -->> 75 

    ¡Esto es increíble! vec1 y vec2 asignan al mismo número, mientras que vec3 se asigna a un valor diferente como deseamos.

     void cartestionCombosPrimes(std::vector > v, std::vector primes, bool verbose) { std::unordered_map > cartCombs; unsigned long int len = v.size(); unsigned long int myProd = 1; std::vector s(len); for (std::size_t j = 0; j < len; ++j) { myProd *= v[j].size(); s[j] = v[j].size() - 1; } unsigned long int loopLim = myProd - 1; std::vector > res(myProd, std::vector()); std::vector myCounter(len, 0); std::vector value(len, 0); int64_t key; for (std::size_t j = 0; j < loopLim; ++j) { key = 1; for (std::size_t k = 0; k < len; ++k) { value[k] = v[k][myCounter[k]]; key *= primes[value[k]]; } cartCombs.insert({key, value}); int test = 0; while (myCounter[test] == s[test]) { myCounter[test] = 0; ++test; } ++myCounter[test]; } key = 1; // Get last possible combination for (std::size_t k = 0; k < len; ++k) { value[k] = v[k][myCounter[k]]; key *= primes[value[k]]; } cartCombs.insert({key, value}); std::cout << cartCombs.size() << std::endl; if (verbose) { int count = 1; for (std::pair > element : cartCombs) { std::string tempStr; for (std::size_t k = 0; k < len; ++k) tempStr += std::to_string(element.second[k]) + ' '; std::cout << count << " : " << tempStr << std::endl; ++count; } } } 

    On the same example above that would generate nearly 2.5 million products, the above algorithm returns the same result in less than 0.3 seconds.

    There are a couple of caveats with this latter method. We must have our primes generated a priori and if we have many vectors in our Cartesian product, the key could grow beyond the bounds of int64_t . The first issue shouldn't be that difficult to overcome as there are many resources (libraries, lookup tables, etc.) available for generating prime numbers. I'm not really sure, but I've read that the latter issue shouldn't be a problem for python as integers have arbitrary precision ( Python integer ranges ).

    We also have to deal with the fact that our source vectors might not be nice integer vectors with small values. This can be remedied by ranking all of the elements across all vectors before you proceed. For example, given the following vectors:

     vec1 = (12345.65, 5, 5432.11111) vec2 = (2222.22, 0.000005, 5) vec3 = (5, 0.5, 0.8) 

    Ranking them, we would obtain:

     rank1 = (6, 3, 5) rank2 = (4, 0, 3) rank3 = (3, 1, 2) 

    And now, these can be used in place of the actual values to create your key. The only portion of the code that would change would be the for loops that build the key (and of course the rank object that would need to be created):

     for (std::size_t k = 0; k < len; ++k) { value[k] = v[k][myCounter[k]]; key *= primes[rank[k][myCounter[k]]]; } 

    Editar:
    As some of the commenters have pointed out, the above method disguises the fact that all products must be generated. I should have said that the first time around. Personally, I don't see how it can be avoided given the many different presentations.

    Also, in case anybody is curious, here is the test case I used above:

     [1 10 14 6], [7 2 4 8 3 11 12], [11 3 13 4 15 8 6 5], [10 1 3 2 9 5 7], [1 5 10 3 8 14], [15 3 7 10 4 5 8 6], [14 9 11 15], [7 6 13 14 10 11 9 4] 

    It should return 162295 unique combinations.

    One way to save some work might be to generate deduplicated combinations of the first k chosen pools, then extend those to deduplicated combinations of the first k+1. This lets you avoid individually generating and rejecting all length-20 combinations that picked 2, 1 instead of 1, 2 from the first two pools:

     def combinations_from_pools(pools): # 1-element set whose one element is an empty tuple. # With no built-in hashable multiset type, sorted tuples are probably the most efficient # multiset representation. combos = {()} for pool in pools: combos = {tuple(sorted(combo + (elem,))) for combo in combos for elem in pool} return combos 

    With the input sizes you’re talking about, though, no matter how efficiently you generate combinations, you’ll never be able to process all of them. Even with 20 identical 1000-element pools, there would be 496432432489450355564471512635900731810050 combinations (1019 choose 20, by the stars and bars formula), or about 5e41. If you conquered the Earth and devoted all the processing power of all the computing equipment of all of humanity to the task, you still couldn’t make a dent in that. You need to find a better way to solve your underlying task.

    Answers that have been posted so far (including lazy lexicographic one-at-a-time generation by Tim Peters) have worst-case space complexity proportional to the size of the output. I am going to outline an approach that will constructively produce all unique unordered combinations without deduplication of internally generated intermediate data. My algorithm generates the combinations in a lexicographically sorted order. It has a computational overhead compared to the simpler algorithms. However it can be parallelized (so that different ranges of the final output can be produced concurrently).

    The idea is the following.

    So we have N pools {P 1 , …, P N } where we must draw our combinations from. We can easily identify the smallest combination (with respect to the mentioned lexicographical ordering). Let it be (x 1 , x 2 …, x N-1 , x N ) (where x 1 <= x 2 <= ... <= x N-1 <= x N , and each x j is just the smallest element from one of the pools {P i }). This smallest combination will be followed by zero or more combinations where the prefix x 1 , x 2 …, x N-1 is the same and the last position runs over an increasing sequence of values. How can we identify that sequence?

    Let’s introduce the following definition:

    Given a combination prefix C=(x 1 , x 2 …, x K-1 , x K ) (where K < N), a pool P i is called free with respect to C if the latter (the prefix) can be drawn from the rest of the pools.

    Identifying free pools for a given prefix is easily reduced to the problem of finding maximum matchings in a bipartite graph. The challenging part is doing it efficiently (taking advantage of the specifics of our case). But I will save it for later (this is work in progress, to be materialized as a Python program in a day).

    So, for the prefix (x 1 , x 2 …, x N-1 ) of our first combination we can identify all the free pools {FP i }. Any one of them can be used to pick an element for the last position. Therefore the sequence of interest is the sorted set of elements from {FP 1 U FP 2 U … } that are greater than or equal to x N-1 .

    When the last position is exhausted we must increase the last-but-one position whereupon we will repeat the procedure of finding the possible values for the last position. Unsuprisingly, the procedure of enumerating the values for the last-but-one (as well as any other) position is the same – the only difference is the length of the combination prefix based on which free pools must be identified.

    Thus the following recursive algorithm should do the work:

    1. Start with an empty combination prefix C. At this point all pools are free.
    2. If the length of C is equal to N, then output C and return.
    3. Merge the free pools into one sorted list S and drop from it all elements that are less than the last element of C.
    4. For each value x from S do
      • The new combination prefix is C’=(C, x)
      • With the current combination prefix having grown by one, some of the free pools stop being free. Identify them and recurse into step 1 with an updated free pool list and combination prefix C’.

    You could implement an hashable list and use python set() to filter all duplicates. Your hash-function just needs to ignore the order in the list which can be achieved by using collections.Counter

     from collections import Counter class HashableList(list): def __hash__(self): return hash(frozenset(Counter(self))) def __eq__(self, other): return hash(self) == hash(other) x = HashableList([1,2,3]) y = HashableList([3,2,1]) print set([x,y]) 

    Esto devuelve:

     set([[1, 2, 3]]) 

    Esto es lo que se me ocurrió:

     class Combination: def __init__(self, combination): self.combination = tuple(sorted(combination)) def __eq__(self, other): return self.combination == self.combination def __hash__(self): return self.combination.__hash__() def __repr__(self): return self.combination.__repr__() def __getitem__(self, i): return self.combination[i] 

    Entonces,

     pools = [[1, 2, 3], [2, 3, 4], [3, 4, 5]] part = (0, 0, 1) set(Combination(combin) for combin in product(*(pools[i] for i in part))) 

    Salidas:

     {(1, 1, 2), (1, 1, 3), (1, 1, 4), (1, 2, 2), (1, 2, 3), (1, 2, 4), (1, 3, 3), (1, 3, 4), (2, 2, 2), (2, 2, 3), (2, 2, 4), (2, 3, 3), (2, 3, 4), (3, 3, 3), (3, 3, 4)} 

    Not sure if this is really what you’re looking for.