python - example - Escoger combinaciones desordenadas de grupos con superposición
set combinations python (6)
Este es un problema dificil. Creo que lo mejor que puede hacer en el caso general es implementar una hash table en la que la clave sea un conjunto multiset y el valor sea su combinación real. Esto es similar a lo que @ErikWolf mencionó, sin embargo, este método evita la producción de 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 sets 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 programador de python , procederé en C++ .
Tendremos algunos problemas si intentamos implementar todo lo anterior exactamente como está. Por lo que sé, no puede tener std::multiset<int> como 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<std::vector<int> > v, bool verbose) {
std::map<std::multiset<int>, std::vector<int> > cartCombs;
unsigned long int len = v.size();
unsigned long int myProd = 1;
std::vector<unsigned long int> 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<std::vector<int> > res(myProd, std::vector<int>());
std::vector<unsigned long int> myCounter(len, 0);
std::vector<int> value(len, 0);
std::multiset<int> 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::multiset<int>, std::vector<int> > 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 commutative 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 continuación 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! vec1y asigna al vec2mismo número, mientras que vec3se asigna a un valor diferente tal como lo deseamos.
void cartestionCombosPrimes(std::vector<std::vector<int> > v,
std::vector<int> primes,
bool verbose) {
std::unordered_map<int64_t, std::vector<int> > cartCombs;
unsigned long int len = v.size();
unsigned long int myProd = 1;
std::vector<unsigned long int> 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<std::vector<int> > res(myProd, std::vector<int>());
std::vector<unsigned long int> myCounter(len, 0);
std::vector<int> 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<int, std::vector<int> > 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;
}
}
}
En el mismo ejemplo anterior que generaría casi 2.5 millones de productos, el algoritmo anterior devuelve el mismo resultado en menos de 0.3 segundos.
Hay un par de advertencias con este último método. Debemos tener nuestros primos generados a priori y si tenemos muchos vectores en nuestro producto cartesiano, la clave podría crecer más allá de los límites de int64_t. El primer problema no debería ser tan difícil de superar ya que hay muchos recursos (bibliotecas, tablas de búsqueda, etc.) disponibles para generar números primos. No estoy realmente seguro, pero he leído que este último problema no debería ser un problema pythonya que los enteros tienen una precisión arbitraria ( rangos enteros de Python ).
También tenemos que lidiar con el hecho de que nuestros vectores de origen podrían no ser buenos vectores enteros con valores pequeños. Esto puede remediarse clasificando todos los elementos en todos los vectores antes de continuar. Por ejemplo, dados los siguientes vectores:
vec1 = (12345.65, 5, 5432.11111)
vec2 = (2222.22, 0.000005, 5)
vec3 = (5, 0.5, 0.8)
Clasificándolos, obtendríamos:
rank1 = (6, 3, 5)
rank2 = (4, 0, 3)
rank3 = (3, 1, 2)
Y ahora, estos pueden usarse en lugar de los valores reales para crear su clave. La única parte del código que cambiaría serían los bucles for que crean la clave (y, por supuesto, el rankobjeto que se debe crear):
for (std::size_t k = 0; k < len; ++k) {
value[k] = v[k][myCounter[k]];
key *= primes[rank[k][myCounter[k]]];
}
Editar:
Como algunos de los comentaristas han señalado, el método anterior disfraza el hecho de que todos los productos deben generarse. Debería haber dicho eso la primera vez. Personalmente, no veo cómo se puede evitar dadas las diferentes presentaciones.
Además, en caso de que alguien tenga curiosidad, aquí está el caso de prueba que usé anteriormente:
[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]
Debe devolver 162295combinaciones únicas.
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 mucha 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 por simplicidad, cada elemento es un número 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 al reformular el 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 ya hizo el OP.
Me parece que el enfoque más prometedor sería escribir un generador personalizado (no uno que se itertools principalmente en itertools funciones de itertools ) que generara todas las posibilidades en 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 volvió 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 los dos tipos de ortografía de los [0, 1] ** 64 ejemplos anteriores, y ejecuta el ejemplo al final de la respuesta de @Joseph Wood aproximadamente tan rápido como dijo su código C ++ ejecutado (0,35 segundos en mi caja en 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 Python ejecutable:
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 alcance 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, supongamos que tenemos una secuencia estrictamente creciente (lexicográfica) de tuplas ordenadas, agregamos la misma tupla T a cada una y clasificamos cada una nuevamente. 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 (bosquejo: si t1 y t2 son tuplas adyacentes, t1 < t2 , y permítame ser 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 ya ordenadas garantizadas 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 tiene que 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 pilas. 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 anexado 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 usar por sí solo, o como un componente básico en otros enfoques. Por ejemplo, si hay muchas entradas, se pueden buscar pares con intersecciones grandes, y este esquema de 2 entradas se usa 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 intento 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 requería solo algunos cambios para usar en este contexto.
Así que esto prueba 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 hacerla mucho más rápida es 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ó a la vez que el range(10_000) no contiene ningún valor superior a 10000. 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 para intentarlo ;-)
Y uno basado en el esquema de @ Leon
A continuación se presenta 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 se ejecuta significativamente más lento (un factor de 3 a 4 veces más lento en una variedad de casos similares a los aleatorios de @ JospephWood 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 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 intentar 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 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 qué tan 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 algunos de los costos de la concordancia 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 toma 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" sería 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
restore_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 restore_availpools is None:
restore_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 restore_availpools is not None:
availpools = restore_availpools
try:
yield from inner(0, 0)
except Finished:
pass
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)}
No estoy seguro si esto es realmente lo que estás buscando.
Las respuestas que se han publicado hasta ahora (incluida la generación lexicográfica perezosa de Tim Peters) tienen una complejidad de espacio en el peor de los casos proporcional al tamaño de la salida. Voy a esbozar un enfoque que producirá de manera constructiva todas las combinaciones desordenadas únicas sin la deduplicación de los datos intermedios generados internamente. Mi algoritmo genera las combinaciones en un orden ordenado por lexicografía. Tiene una sobrecarga computacional en comparación con los algoritmos más simples. Sin embargo, puede ser paralelizado (de modo que se puedan producir simultáneamente diferentes rangos de la salida final).
La idea es la siguiente.
Entonces tenemos Ngrupos {P 1 , ..., P N } de donde debemos dibujar nuestras combinaciones. Podemos identificar fácilmente la combinación más pequeña (con respecto al ordenamiento lexicográfico mencionado). Deje que sea (x 1 , x 2 ..., x N-1 , x N ) (donde x 1 <= x 2 <= ... <= x N-1 <= x N , y cada x j es solo el elemento más pequeño de una de las agrupaciones {P i }). Esta combinación más pequeña irá seguida de cero o más combinaciones donde el prefijo x 1 , x 2 ..., x N-1es la misma y la última posición se ejecuta en una secuencia creciente de valores. ¿Cómo podemos identificar esa secuencia?
Vamos a introducir la siguiente definición:
Dada una combinación de prefijo C = (x 1 , x 2 ..., x K-1 , x K ) (donde K <N), un conjunto P i se llama libre con respecto a C si este último (el prefijo) puede Ser dibujado del resto de las piscinas.
La identificación de grupos libres para un prefijo dado se reduce fácilmente al problema de encontrar matchings máximas en un gráfico bipartito. La parte difícil es hacerlo de manera eficiente (aprovechando los detalles de nuestro caso). Pero lo guardaré para más adelante (esto es un trabajo en progreso, que se materializará como un programa Python en un día).
Entonces, para el prefijo (x 1 , x 2 ..., x N-1 ) de nuestra primera combinación podemos identificar todos los grupos libres {FP i }. Cualquiera de ellos puede usarse para elegir un elemento para la última posición. Por lo tanto, la secuencia de interés es el conjunto ordenado de elementos de {FP 1 U FP 2 U ...} que son mayores o iguales a x N-1 .
Cuando se agote la última posición, debemos aumentar la última, pero una, con lo cual repetiremos el procedimiento de encontrar los valores posibles para la última posición. Como es lógico, el procedimiento para enumerar los valores de la posición de último-uno-uno (así como cualquier otro) es el mismo: la única diferencia es la longitud del prefijo de combinación en función de los grupos libres que deben identificarse.
Así el siguiente algoritmo recursivo debería hacer el trabajo:
- Comience con un prefijo de combinación vacío C. En este punto, todas las agrupaciones son gratuitas.
- Si la longitud de C es igual a N, entonces salga C y regrese.
- Combine los grupos libres en una lista ordenada S y elimine de ella todos los elementos que sean menores que el último elemento de C.
- Para cada valor x de S do
- El nuevo prefijo de combinación es C ''= (C, x)
- Dado que el prefijo de combinación actual ha crecido en uno, algunos de los grupos libres dejan de ser gratuitos. Identifíquelos y diríjase al paso 1 con una lista de grupos gratuita actualizada y el prefijo de combinación C ''.
Podría implementar una lista de hashable y usar python set () para filtrar todos los duplicados. Su función hash solo necesita ignorar el orden en la lista que puede lograrse mediante el uso de colecciones.
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]])
Una forma de ahorrar algo de trabajo podría ser generar combinaciones deduplicadas de los primeros k grupos elegidos, luego extenderlos a combinaciones deduplicadas del primer k + 1. Esto le permite evitar generar y rechazar individualmente todas las combinaciones de longitud 20 que se seleccionaron en 2, 1lugar de 1, 2las dos primeras agrupaciones:
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
Sin embargo, con los tamaños de entrada de los que está hablando, no importa qué tan eficientemente genere combinaciones, nunca podrá procesarlas todas. Incluso con 20 grupos idénticos de 1000 elementos, habría 496432432489450355564471512635900731810050 combinaciones (1019 elegir 20, por la fórmula de estrellas y barras), o aproximadamente 5e41. Si conquistó la Tierra y dedicó todo el poder de procesamiento de todos los equipos informáticos de toda la humanidad a la tarea, todavía no podría hacer mella en eso. Necesita encontrar una mejor manera de resolver su tarea subyacente.