example - libreria itertools python

Elimina combinaciones que contengan algunos valores antes incluso de calcularse.

Question

dada una lista y elementos de exclusiones, ¿es posible ignorar el cálculo de combinaciones que contiene estos elementos?

Ejemplo 1

Dado que l = [1, 2, 3, 4, 5] , quiero calcular todas las combinaciones de size 4 y excluyendo las combinaciones que contienen (1, 3) antes de que se calculen.

Los resultados serían:

    All results:            Wanted results:

    [1, 2, 3, 4]            [1, 2, 4, 5]
    [1, 2, 3, 5]            [2, 3, 4, 5]
    [1, 2, 4, 5]
    [1, 3, 4, 5]
    [2, 3, 4, 5]

Todas las combinaciones que contenían 1 y 3 han sido eliminadas.

Ejemplo 2

sugerido por @Eric Duminil

el resultado para l = [1, 2, 3, 4, 5, 6] , size 4 y

• Excluyendo (1, 2, 3) en la segunda columna

• Excluyendo (1, 2) en la tercera columna

  All results:        Wanted results 1            Wanted results 2
                      (Excluding [1, 2, 3]):      (Excluding [1, 2])
  
  [1, 2, 3, 4]        [1, 2, 4, 5]                [1, 3, 4, 5]
  [1, 2, 3, 5]        [1, 2, 4, 6]                [1, 3, 4, 6]
  [1, 2, 3, 6]        [1, 2, 5, 6]                [1, 3, 5, 6]
  [1, 2, 4, 5]        [1, 3, 4, 5]                [1, 4, 5, 6]
  [1, 2, 4, 6]        [1, 3, 4, 6]                [2, 3, 4, 5]
  [1, 2, 5, 6]        [1, 3, 5, 6]                [2, 3, 4, 6]
  [1, 3, 4, 5]        [1, 4, 5, 6]                [2, 3, 5, 6]
  [1, 3, 4, 6]        [2, 3, 4, 5]                [2, 4, 5, 6]
  [1, 3, 5, 6]        [2, 3, 4, 6]                [3, 4, 5, 6]
  [1, 4, 5, 6]        [2, 3, 5, 6]                                
  [2, 3, 4, 5]        [2, 4, 5, 6]                                
  [2, 3, 4, 6]        [3, 4, 5, 6]                                
  [2, 3, 5, 6]           
  [2, 4, 5, 6]           
  [3, 4, 5, 6]        

Todas las combinaciones que contenían 1 y 2 y 3 se han eliminado de los resultados deseados 1

Todas las combinaciones que contenían 1 y 2 se han eliminado de los resultados deseados 2

Tengo una combinación mucho más grande de computar pero toma mucho tiempo y quiero reducir este tiempo usando estas exclusiones.

Soluciones probadas

Con el método 1, las combinaciones aún se calculan.

Con el método 2, traté de modificar la función de combinaciones pero no pude encontrar una forma adecuada de ignorar mi lista de exclusión antes de calcular.

            Method 1                    |               Method 2
                                        |               
def main():                             |   def combinations(iterable, r):
    l = list(range(1, 6))               |       pool = tuple(iterable)
    comb = combinations(l, 4)           |       n = len(pool)
                                        |       if r > n:
    for i in comb:                      |           return
        if set([1, 3]).issubset(i):     |       indices = list(range(r))
            continue                    |       yield tuple(pool[i] for i in indices)
        else                            |       while True:
            process()                   |           for i in reversed(range(r)):
                                        |               if indices[i] != i + n - r:
                                        |                   break
                                        |               else:
                                        |                   return
                                        |           indices[i] += 1
                                        |           for j in range(i+1, r):
                                        |               indices[j] = indices[j-1] + 1
                                        |           yield tuple(pool[i] for i in indices)

EDITAR:

En primer lugar, gracias a todos por su ayuda, olvidé dar más detalles sobre las restricciones.

• El orden de las salidas no es relevante, de ejemplo, si el resultado es [1, 2, 4, 5] [2, 3, 4, 5] o [2, 3, 4, 5] [1, 2, 4, 5] , no es importante.

• Los elementos de las combinaciones deben estar ordenados (si es posible), [1, 2, 4, 5] [2, 3, 4, 5] y no [2, 1, 5, 4] [3, 2, 4, 5] pero no es importante ya que las combinaciones podrían ordenarse después.

• La lista de exclusiones es una lista de todos los elementos que no deben aparecer juntos en las combinaciones. por ejemplo, si mi lista de exclusión es (1, 2, 3) , no se deben calcular todas las combinaciones que contengan 1 y 2 y 3 . Sin embargo, se permiten combinaciones con 1 y 2 y no 3 . En ese caso, si excluyo las combinaciones que contienen (1, 2) y (1, 2, 3) es completamente inútil ya que todas las combinaciones que serán filtradas por (1, 2, 3) ya están filtradas por (1, 2)

• Deben ser posibles múltiples listas de exclusión porque uso múltiples restricciones en mis combinaciones.

Respuestas probadas

@tobias_k Esta solución considera la lista de exclusión (1, 2, 3) como el significado de exclusión OR (1, 2), (2, 3) and (1, 3) se excluirán si entendí bien, esto es útil en un caso pero no en mi problema actual, modifiqué la pregunta para dar más detalles, perdón por la confusión. En su respuesta, no puedo usar solo las listas (1, 2) y (1, 3) como exclusión como lo especificó. Sin embargo, la gran ventaja de esta solución es permitir múltiples exclusiones.

@Kasramvd y @mikuszefski Su solución está muy cerca de lo que quiero, si incluye múltiples listas de exclusión, sería la respuesta.

Gracias

Answer 1

(Resultó que mi respuesta anterior no satisface realmente las restricciones de la pregunta, aquí hay otra. Estoy publicando esto como una respuesta separada, ya que el enfoque es muy diferente y la respuesta original aún puede ayudar a otros).

Puede implementar esto recursivamente, cada vez antes de recurrir para agregar otro elemento a las combinaciones, verificando si eso violaría uno de los conjuntos de exclusión. Esto no genera combinaciones inválidas, y funciona con conjuntos de exclusión superpuestos (como (1,3), (1,5) ), y conjuntos de exclusión con más de dos elementos (como (2,4,5) , permitiendo cualquier combinación excepto todas juntas.

def comb_with_excludes(lst, n, excludes, i=0, taken=()):
    if n == 0:
        yield taken  # no more needed
    elif i <= len(lst) - n:
        t2 = taken + (lst[i],)  # add current element
        if not any(e.issubset(t2) for e in excludes):
            yield from comb_with_excludes(lst, n-1, excludes, i+1, t2)
        if i < len(lst) - n:  # skip current element
            yield from comb_with_excludes(lst, n, excludes, i+1, taken)

Ejemplo:

>>> lst = [1, 2, 3, 4, 5, 6]
>>> excludes = [{1, 3}, {1, 5}, {2, 4, 5}]
>>> list(comb_with_excludes(lst, 4, excludes))
[[1, 2, 4, 6], [2, 3, 4, 6], [2, 3, 5, 6], [3, 4, 5, 6]]

Bueno, lo hice en este momento, y resulta que esto es considerablemente más lento que usar ingenuamente itertools.combination en una expresión de generador con un filtro, como lo hace usted:

def comb_naive(lst, r, excludes):
    return (comb for comb in itertools.combinations(lst, r)
                 if not any(e.issubset(comb) for e in excludes))

Calcular las combinaciones en Python es solo más lento que usar la biblioteca (que probablemente se implementa en C) y luego filtrar los resultados. Dependiendo de la cantidad de combinaciones que se puedan excluir, esto podría ser más rápido en algunos casos, pero para ser honesto, tengo mis dudas.

Podría obtener mejores resultados si puede usar itertools.combinations para los subproblemas, como en la respuesta de Kasramvd , pero para conjuntos de exclusión múltiples, no disyuntivos, eso es más difícil. Una forma podría ser separar los elementos de la lista en dos conjuntos: los que tienen restricciones y los que no. Luego, use itertoolc.combinations para ambos, pero verifique las restricciones solo para las combinaciones de aquellos elementos donde sean importantes. Aún debe verificar y filtrar los resultados, pero solo una parte de ellos. (Una advertencia, sin embargo: los resultados no se generan en orden, y el orden de los elementos dentro de las combinaciones producidas también se confunde un poco).

def comb_with_excludes2(lst, n, excludes):
    wout_const = [x for x in lst if not any(x in e for e in excludes)]
    with_const = [x for x in lst if     any(x in e for e in excludes)]
    k_min, k_max = max(0, n - len(wout_const)), min(n, len(with_const))
    return (c1 + c2 for k in range(k_min, k_max)
                    for c1 in itertools.combinations(with_const, k)
                    if not any(e.issubset(c1) for e in excludes)
                    for c2 in itertools.combinations(wout_const, n - k))

Esto ya es mucho mejor que la solución recursiva de Python puro, pero aún no es tan bueno como el enfoque "ingenuo" para el ejemplo anterior:

>>> lst = [1, 2, 3, 4, 5, 6]
>>> excludes = [{1, 3}, {1, 5}, {2, 4, 5}]
>>> %timeit list(comb_with_excludes(lst, 4, excludes))
10000 loops, best of 3: 42.3 µs per loop
>>> %timeit list(comb_with_excludes2(lst, 4, excludes))
10000 loops, best of 3: 22.6 µs per loop
>>> %timeit list(comb_naive(lst, 4, excludes))
10000 loops, best of 3: 16.4 µs per loop

Sin embargo, los resultados dependen mucho de la entrada. Para una lista más grande, con restricciones que solo se aplican a algunos de esos elementos, este enfoque es de hecho más rápido que el ingenuo:

>>> lst = list(range(20))
>>> %timeit list(comb_with_excludes(lst, 4, excludes))
10 loops, best of 3: 15.1 ms per loop
>>> %timeit list(comb_with_excludes2(lst, 4, excludes))
1000 loops, best of 3: 558 µs per loop
>>> %timeit list(comb_naive(lst, 4, excludes))
100 loops, best of 3: 5.9 ms per loop

Answer 2

(Resulta que esto no hace exactamente lo que OP quiere. Todavía lo dejo aquí porque podría ayudar a otros).

Para incluir elementos mutuamente exclusivos, podría incluirlos en listas dentro de la lista, obtener las combinations de esos y luego el product de las combinaciones de sub-listas:

>>> from itertools import combinations, product
>>> l = [[1, 3], [2], [4], [5]]
>>> [c for c in combinations(l, 4)]
[([1, 3], [2], [4], [5])]
>>> [p for c in combinations(l, 4) for p in product(*c)]
[(1, 2, 4, 5), (3, 2, 4, 5)]

Un ejemplo más complejo:

>>> l = [[1, 3], [2, 4, 5], [6], [7]]
>>> [c for c in combinations(l, 3)]
[([1, 3], [2, 4, 5], [6]),
 ([1, 3], [2, 4, 5], [7]),
 ([1, 3], [6], [7]),
 ([2, 4, 5], [6], [7])]
>>> [p for c in combinations(l, 3) for p in product(*c)]
[(1, 2, 6),
 (1, 4, 6),
 ... 13 more ...
 (4, 6, 7),
 (5, 6, 7)]

Esto no genera ninguna combinación de "basura" que se filtre después. Sin embargo, se supone que desea un máximo de un elemento de cada grupo "exclusivo", por ejemplo, en el segundo ejemplo, no solo evita las combinaciones con 2,4,5 , sino también aquellas con 2,4 , 4,5 o 2,5 . Además, no es posible (o al menos no es fácil) tener exclusivamente uno de 1,3 y 1,5 , pero permite 3,5 . (Podría ser posible extenderlo a esos casos, pero todavía no estoy seguro de si y cómo).

Puede envolver esto en una función, derivando el formato de entrada ligeramente diferente de su formato (presumido) y devolviendo una expresión de generador acorde. Aquí, lst es la lista de elementos, r el número de elementos por combinación, y exclude_groups una lista de grupos de elementos mutuamente exclusivos:

from itertools import combinations, product

def comb_with_excludes(lst, r, exclude_groups):
    ex_set = {e for es in exclude_groups for e in es}
    tmp = exclude_groups + [[x] for x in lst if x not in ex_set]
    return (p for c in combinations(tmp, r) for p in product(*c))

lst = [1, 2, 3, 4, 5, 6, 7]
excludes = [[1, 3], [2, 4, 5]]
for x in comb_with_excludes(lst, 3, excludes):
    print(x)

Answer 3

Algorítmicamente, tiene que calcular la combinación de los elementos de su lista que no se encuentran entre los excluidos y luego agregar las combinaciones respectivas de los elementos excluidos a la combinación del resto de elementos. Por supuesto, este enfoque requiere una gran cantidad de controles y la necesidad de realizar un seguimiento de los índices que, incluso si lo hace en Python, no le dará una diferencia notable en el rendimiento (conocido como inconvenientes del problema de satisfacción de Restricción ). (En lugar de simplemente calcularlos utilizando la combination y filtrando los elementos no deseados).

Por lo tanto, creo que esta es la mejor manera de ir en la mayoría de los casos:

In [77]: from itertools import combinations, filterfalse

In [78]: list(filterfalse({1, 3}.issubset, combinations(l, 4)))
Out[78]: [(1, 2, 4, 5), (2, 3, 4, 5)]

Answer 4

Desde una perspectiva algorítmica, puede separar los excluidos y el restablecimiento de los elementos válidos y calcular las combinaciones de cada conjunto por separado y solo concatenar el resultado según la longitud deseada. Este enfoque rechazará por completo la inclusión de todos los artículos excluidos al mismo tiempo en combinación, pero omitirá el pedido real.

from itertools import combinations

def comb_with_exclude(iterable, comb_num, excludes):
    iterable = tuple(iterable)
    ex_len = len(excludes)
    n = len(iterable)

    if comb_num < ex_len or comb_num > n:
        yield from combinations(iterable, comb_num)

    else:
        rest = [i for i in iterable if not i in excludes]
        ex_comb_rang = range(0, ex_len)
        rest_comb_range = range(comb_num, comb_num - ex_len, -1)
        # sum of these pairs is equal to the comb_num
        pairs = zip(ex_comb_rang, rest_comb_range)

        for i, j in pairs:
            for p in combinations(excludes, i):
                for k in combinations(rest, j):
                    yield k + p
       """
       Note that instead of those nested loops you could wrap the combinations within a product function like following:
       for p, k in product(combinations(excludes, i), combinations(rest, j)):
            yield k + p
       """

Manifestación:

l = [1, 2, 3, 4, 5, 6, 7, 8]
ex = [2, 5, 6]
print(list(comb_with_exclude(l, 6, ex)))

[(1, 3, 4, 7, 8, 2), (1, 3, 4, 7, 8, 5), (1, 3, 4, 7, 8, 6), (1, 3, 4, 7, 2, 5), (1, 3, 4, 8, 2, 5), (1, 3, 7, 8, 2, 5), (1, 4, 7, 8, 2, 5), (3, 4, 7, 8, 2, 5), (1, 3, 4, 7, 2, 6), (1, 3, 4, 8, 2, 6), (1, 3, 7, 8, 2, 6), (1, 4, 7, 8, 2, 6), (3, 4, 7, 8, 2, 6), (1, 3, 4, 7, 5, 6), (1, 3, 4, 8, 5, 6), (1, 3, 7, 8, 5, 6), (1, 4, 7, 8, 5, 6), (3, 4, 7, 8, 5, 6)]

l = [1, 2, 3, 4, 5]
ex = [1, 3]
print(list(comb_with_exclude(l, 4, ex)))

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

Benckmark con otras respuestas:

Resultados: este enfoque es más rápido que los demás.

# this answer
In [169]: %timeit list(comb_with_exclude(lst, 3, excludes[0]))
100000 loops, best of 3: 6.47 µs per loop

# tobias_k
In [158]: %timeit list(comb_with_excludes(lst, 3, excludes))
100000 loops, best of 3: 13.1 µs per loop

# Vikas Damodar
In [166]: %timeit list(combinations_exc(lst, 3))
10000 loops, best of 3: 148 µs per loop

# mikuszefski
In [168]: %timeit list(sub_without(lst, 3, excludes[0]))
100000 loops, best of 3: 12.52 µs per loop

Answer 5

He intentado editar combinaciones de acuerdo con sus requisitos:

def combinations(iterable, r):
   # combinations(''ABCD'', 2) --> AB AC AD BC BD CD
   # combinations(range(4), 3) --> 012 013 023 123
   pool = tuple(iterable)
   n = len(pool)
   if r > n:
      return
   indices = list(range(r))
   # yield tuple(pool[i] for i in indices)
   while True:
       for i in reversed(range(r)):
           if indices[i] != i + n - r:
               break
    else:
        return
    indices[i] += 1
    for j in range(i+1, r):
        indices[j] = indices[j-1] + 1
    # print(tuple(pool[i] for i in indices ), "hai")
    if 1 in tuple(pool[i] for i in indices ) and 3  in tuple(pool[i] for i in indices ):
        pass
    else:
        yield tuple(pool[i] for i in indices)


d = combinations(list(range(1, 6)),4)
for i in d:
   print(i)

Se devolverá algo como esto:

(1, 2, 4, 5) (2, 3, 4, 5)

Answer 6

Hice la exclusión durante la combinación utilizando el siguiente código para guardar el segundo tiempo de bucle. solo tiene que pasar los índices de los elementos excluidos como un conjunto.

actualización : violín de trabajo

from itertools import permutations

def combinations(iterable, r, combIndeciesExclusions=set()):
    pool = tuple(iterable)
    n = len(pool)
    for indices in permutations(range(n), r):
        if ( len(combIndeciesExclusions)==0 or not combIndeciesExclusions.issubset(indices)) and sorted(indices) == list(indices):
            yield tuple(pool[i] for i in indices)


l = list(range(1, 6))
comb = combinations(l, 4, set([0,2]))
print list(comb)

Answer 7

Supongo que mi respuesta es similar a algunas otras aquí, pero esto fue lo que jugué en paralelo

from itertools import combinations, product

"""
with help from
https://.com/questions/374626/how-can-i-find-all-the-subsets-of-a-set-with-exactly-n-elements
https://.com/questions/32438350/python-merging-two-lists-with-all-possible-permutations
https://.com/questions/952914/making-a-flat-list-out-of-list-of-lists-in-python
"""
def sub_without( S, m, forbidden ):
    out = []
    allowed = [ s for s in S if s not in forbidden ]
    N = len( allowed )
    for k in range( len( forbidden ) ):
        addon = [ list( x ) for x in combinations( forbidden, k) ]
        if N + k >= m:
            base = [ list( x ) for x in combinations( allowed, m - k ) ]
            leveltotal = [ [ item for sublist in x for item in sublist ] for x in product( base, addon ) ]
            out += leveltotal
    return out

val = sub_without( range(6), 4, [ 1, 3, 5 ] )

for x in val:
    print sorted(x)

>>
[0, 1, 2, 4]
[0, 2, 3, 4]
[0, 2, 4, 5]
[0, 1, 2, 3]
[0, 1, 2, 5]
[0, 2, 3, 5]
[0, 1, 3, 4]
[0, 1, 4, 5]
[0, 3, 4, 5]
[1, 2, 3, 4]
[1, 2, 4, 5]
[2, 3, 4, 5]