itertools.permutaciones genera que sus elementos son tratados como único basado en su posición, no de su valor. Así que, básicamente quiero evitar duplicados como este:

>>> list(itertools.permutations([1, 1, 1]))
[(1, 1, 1), (1, 1, 1), (1, 1, 1), (1, 1, 1), (1, 1, 1), (1, 1, 1)]

Filtrado después no es posible debido a que la cantidad de permutaciones es demasiado grande en mi caso.

¿Alguien sabe de un algoritmo adecuado para esto?

Muchas gracias!

EDICIÓN:

Lo que básicamente quiere es la siguiente:

x = itertools.product((0, 1, 'x'), repeat=X)
x = sorted(x, key=functools.partial(count_elements, elem='x'))

que no es posible porque sorted crea una lista y la salida de itertools.el producto es demasiado grande.

Lo siento, debería haber descrito el problema real.

  • Lo que es demasiado grande? El TOTAL de permutaciones o el ÚNICO permutaciones o ambos?
  • ambos, consulte EDITAR.
  • Existe una solución más rápida que la aceptación de la respuesta (una implementación del Algoritmo de Knuth L) dado aquí
  • Estás buscando permutaciones de Multisets. Consulte el respuesta por Bill Bell a continuación.
  • Intenta for x in permutation() set.add(x)?
  • Tal vez un mejor título para esta pregunta sería «distintas permutaciones». Mejor aún, «distintas permutaciones de una lista con los duplicados».

InformationsquelleAutor xyz-123 | 2011-06-08

16 Comentarios

  1. 50
    class unique_element:
        def __init__(self,value,occurrences):
            self.value = value
            self.occurrences = occurrences
    
    def perm_unique(elements):
        eset=set(elements)
        listunique = [unique_element(i,elements.count(i)) for i in eset]
        u=len(elements)
        return perm_unique_helper(listunique,[0]*u,u-1)
    
    def perm_unique_helper(listunique,result_list,d):
        if d < 0:
            yield tuple(result_list)
        else:
            for i in listunique:
                if i.occurrences > 0:
                    result_list[d]=i.value
                    i.occurrences-=1
                    for g in  perm_unique_helper(listunique,result_list,d-1):
                        yield g
                    i.occurrences+=1
    
    
    
    
    a = list(perm_unique([1,1,2]))
    print(a)

    resultado:

    [(2, 1, 1), (1, 2, 1), (1, 1, 2)]

    EDITAR (cómo funciona):

    Reescribí el programa anterior para ser más largo, pero más legible.

    Por lo general tienen un tiempo difícil explicar cómo funciona algo, pero permítame.
    Con el fin de entender cómo funciona esto, usted tiene que entender de una similar pero más sencillo programa que daría todas las permutaciones con repeticiones.

    def permutations_with_replacement(elements,n):
        return permutations_helper(elements,[0]*n,n-1)#this is generator
    
    def permutations_helper(elements,result_list,d):
        if d<0:
            yield tuple(result_list)
        else:
            for i in elements:
                result_list[d]=i
                all_permutations = permutations_helper(elements,result_list,d-1)#this is generator
                for g in all_permutations:
                    yield g

    Este programa es, obviamente, mucho más simple:
    d representa la profundidad en permutations_helper y tiene dos funciones. Una función es la condición de parada de nuestro algoritmo recursivo, y el otro es para la lista de resultados que se pasa alrededor.

    Lugar de devolver cada resultado, nos rendimiento. Si no hay ninguna función/operador yield tendríamos que empujar el resultado en algunos de cola en el punto de la condición de parada. Pero de esta manera, una vez que la condición de parada se cumple, el resultado se propaga a través de todas las pilas a la persona que llama. Ese es el propósito de

    for g in perm_unique_helper(listunique,result_list,d-1): yield g
    para cada resultado se propagará a la persona que llama.

    Volver al programa original:
    tenemos una lista de elementos únicos. Antes de que podamos utilizar cada elemento, tenemos que comprobar cómo muchos de ellos todavía están disponibles a empujar a result_list. Trabajar con este programa es muy similar a permutations_with_replacement. La diferencia es que cada elemento no se puede repetir más veces de lo que es en perm_unique_helper.

    • Estoy tratando de entender cómo funciona esto, pero estoy perplejo. Podría por favor proporcionar algún tipo de comentario?
    • He editado la respuesta y refinado código. Siéntase libre de publicar extra preguntas que usted tenga.
    • Bonita pieza de código. Re-implementado itertools.Counter, ¿verdad?
    • Yo no estoy familiarizado con itertools Contador. Este código es de más de un ejemplo y con fines educativos, pero menos para la producción, debido a problemas de rendimiento. Si uno tiene mejor solución que yo sugeriría iterativo/no recursing solución procedentes de Narayana Pandita y explica también por la Donad Knuth en el arte de la programación de la computadora con la posible implementación de python en stackoverflow.com/a/12837695/429982
    • He recreado este con itertools.Counter, pero parece que su código es más rápido 🙂
  2. 31

    Porque a veces las nuevas preguntas que se marcan como duplicados y sus autores se refieren a esta pregunta puede ser importante mencionar que sympy tiene un iterador para este propósito.

    >>> from sympy.utilities.iterables import multiset_permutations
    >>> list(multiset_permutations([1,1,1]))
    [[1, 1, 1]]
    >>> list(multiset_permutations([1,1,2]))
    [[1, 1, 2], [1, 2, 1], [2, 1, 1]]
    • Esta es la única respuesta que explícitamente identifica lo que el OP es realmente buscando (es decir, las permutaciones de Multisets).
  3. 20

    Esto se basa en el detalle de implementación que cualquier permutación de una ordenados iterable están ordenados a menos que estén duplicados de antes de permutaciones.

    from itertools import permutations
    
    def unique_permutations(iterable, r=None):
        previous = tuple()
        for p in permutations(sorted(iterable), r):
            if p > previous:
                previous = p
                yield p
    
    for p in unique_permutations('cabcab', 2):
        print p

    da

    ('a', 'a')
    ('a', 'b')
    ('a', 'c')
    ('b', 'a')
    ('b', 'b')
    ('b', 'c')
    ('c', 'a')
    ('c', 'b')
    ('c', 'c')
    • funciona perfectamente bien, pero más lento que la aceptación de la solución. Gracias!
    • Esto no es cierto en las nuevas versiones de Python. Por ejemplo, en Python 3.7.1, list(itertools.permutations([1,2,2], 3)) devuelve [(1, 2, 2), (1, 2, 2), (2, 1, 2), (2, 2, 1), (2, 1, 2), (2, 2, 1)].
    • Estás en lo correcto. La declaración «cualquier permutación de una ordenados iterable están en orden», no era cierto incluso de antiguas versiones de Python. He probado las versiones de Python de vuelta a través de 2.7 y encontrar el resultado exacto. Curiosamente esto no invalida el algoritmo. Lo que no produce permutaciones de tal manera que sólo max permutaciones en cualquier punto son originales.
    • Debo modificarla. Usted es incorrecta. Fui a editar mi respuesta y leer más de cerca lo que escribí. Mi declaración había un calificador que hizo lo correcto: «cualquier permutación de una ordenados iterable son en orden de a menos que estén duplicados de antes de permutaciones
  4. 13

    Aproximadamente tan rápido como Luka Rahne la respuesta, pero más corto & más simple, en mi humilde opinión.

    def unique_permutations(elements):
        if len(elements) == 1:
            yield (elements[0],)
        else:
            unique_elements = set(elements)
            for first_element in unique_elements:
                remaining_elements = list(elements)
                remaining_elements.remove(first_element)
                for sub_permutation in unique_permutations(remaining_elements):
                    yield (first_element,) + sub_permutation
    
    >>> list(unique_permutations((1,2,3,1)))
    [(1, 1, 2, 3), (1, 1, 3, 2), (1, 2, 1, 3), ... , (3, 1, 2, 1), (3, 2, 1, 1)]

    Funciona de forma recursiva mediante el establecimiento de la primer elemento (la iteración a través de todos los elementos singulares), y recorrer las permutaciones de todos los elementos restantes.

    Vamos a ir a través de la unique_permutations de (1,2,3,1) para ver cómo funciona:

    • unique_elements son 1,2,3
    • Vamos a iterar a través de ellos: first_element comienza con 1.
      • remaining_elements son [2,3,1] (es decir. 1,2,3,1 menos la primera 1)
      • Repetimos (de forma recursiva) a través de las permutaciones de los elementos restantes: (1, 2, 3), (1, 3, 2), (2, 1, 3), (2, 3, 1), (3, 1, 2), (3, 2, 1)
      • Para cada sub_permutation, podemos insertar first_element: (1,1,2,3), (1,1,3,2), … y producir el resultado.
    • Ahora repetimos a first_element = 2, y hacer lo mismo que el anterior.
      • remaining_elements son [1,3,1] (es decir. 1,2,3,1 menos los 2 primeros)
      • Nos recorrer las permutaciones de los elementos restantes: (1, 1, 3), (1, 3, 1), (3, 1, 1)
      • Para cada sub_permutation, podemos insertar first_element: (2, 1, 1, 3), (2, 1, 3, 1), (2, 3, 1, 1)… y producir el resultado.
    • Finalmente, hacemos lo mismo con first_element = 3.
  5. 12

    Usted podría tratar de usar set:

    >>> list(itertools.permutations(set([1,1,2,2])))
    [(1, 2), (2, 1)]

    La llamada para establecer eliminado los duplicados

    • Él puede ser que necesite de la lista(set(itertools.permutaciones([1,1,2,2])))
    • O list(itertools.permutations({1,1,2,2})) en Python 3+ o Python 2.7, debido a la existencia de un conjunto de literales. Aunque si él no está usando los valores literales, que acababa de ser mediante set() de todos modos. Y @ralu: mira la pregunta de nuevo, el filtrado después sería muy costoso.
    • set(permutaciones(algunalista)) != permutaciones(set(algunalista))
    • el problema con esto es que necesito que la salida tenga la longitud de la entrada. E. g. list(itertools.permutations([1, 1, 0, 'x'])) pero wihtout los duplicados donde los que son intercambiados.
    • Si eso es un requisito, entonces usted realmente necesita para filtrar después, incluso si usted no desea. Lo que significa que list(set(itertools.permutations([1,1,2,2]))) es lo que tendríamos que utilizar.
    • hm, esto toma un tiempo muy largo para los más de 12 valores… lo que yo realmente quiero es algo como itertools.product((0, 1, 'x'), repeat=X) pero necesito valores de proceso con unos ‘x primera (ordenados no es suitible porque es la generación de una lista y utilizando demasiada memoria).

  6. 9

    Esta es mi solución con 10 líneas:

    class Solution(object):
        def permute_unique(self, nums):
            perms = [[]]
            for n in nums:
                new_perm = []
                for perm in perms:
                    for i in range(len(perm) + 1):
                        new_perm.append(perm[:i] + [n] + perm[i:])
                        # handle duplication
                        if i < len(perm) and perm[i] == n: break
                perms = new_perm
            return perms
    
    
    if __name__ == '__main__':
        s = Solution()
        print s.permute_unique([1, 1, 1])
        print s.permute_unique([1, 2, 1])
        print s.permute_unique([1, 2, 3])

    — Resultado —-

    [[1, 1, 1]]
    [[1, 2, 1], [2, 1, 1], [1, 1, 2]]
    [[3, 2, 1], [2, 3, 1], [2, 1, 3], [3, 1, 2], [1, 3, 2], [1, 2, 3]]
    • Me gusta esta solución
    • Me alegra que te guste este método
    • Hola @LittleRoys. He utilizado una versión ligeramente modificada de su código para un PR en more-itertools. Estás bien con eso?
    • Tengo curiosidad, ¿la clase de añadir ningún valor? ¿Por qué no se trata simplemente de una función?
  7. 5

    Un enfoque ingenuo podría ser la de tomar el conjunto de las permutaciones:

    list(set(it.permutations([1, 1, 1])))
    # [(1, 1, 1)]

    Sin embargo, esta técnica pierde calcula replicar permutaciones y se deshace de ellos. Un enfoque más eficiente sería more_itertools.distinct_permutations, un herramienta de terceros.

    Código

    import itertools as it
    
    import more_itertools as mit
    
    
    list(mit.distinct_permutations([1, 1, 1]))
    # [(1, 1, 1)]

    Rendimiento

    Con una mayor iterable, vamos a comparar las actuaciones entre los ingenuos y de terceros técnicas.

    iterable = [1, 1, 1, 1, 1, 1]
    len(list(it.permutations(iterable)))
    # 720
    
    %timeit -n 10000 list(set(it.permutations(iterable)))
    # 10000 loops, best of 3: 111 µs per loop
    
    %timeit -n 10000 list(mit.distinct_permutations(iterable))
    # 10000 loops, best of 3: 16.7 µs per loop

    Vemos more_itertools.distinct_permutations es de un orden de magnitud más rápido.


    Detalles

    De la fuente, una recursividad algoritmo (como se ve en la aceptación de la respuesta) se usa para calcular distintas permutaciones, evitándose despilfarro en los cálculos. Ver el código fuente para obtener más detalles.

  8. 2

    Parecer como si usted está buscando para itertools.combinaciones() docs.python.org

    list(itertools.combinations([1, 1, 1],3))
    [(1, 1, 1)]
    • No, combinaciones tendría el mismo problema.
    • sólo se da en orden, e.g [1, 2, 3] se produce [1, 2, 3] pero no [3, 2, 1] o [2, 3, 1], etc.
  9. 2

    Aquí es una solución recursiva del problema.

    def permutation(num_array):
        res=[]
        if len(num_array) <= 1:
            return [num_array]
        for num in set(num_array):
            temp_array = num_array.copy()
            temp_array.remove(num)
            res += [[num] + perm for perm in permutation(temp_array)]
        return res
    
    arr=[1,2,2]
    print(permutation(arr))
    • No puedo entender cómo este código funcionó
  10. 1

    De bruces con esta pregunta, mientras que en busca de algo a mí mismo !

    Esto es lo que hice:

    def dont_repeat(x=[0,1,1,2]): # Pass a list
    from itertools import permutations as per
    uniq_set = set()
    for byt_grp in per(x, 4):
    if byt_grp not in uniq_set:
    yield byt_grp
    uniq_set.update([byt_grp])
    print uniq_set
    for i in dont_repeat(): print i
    (0, 1, 1, 2)
    (0, 1, 2, 1)
    (0, 2, 1, 1)
    (1, 0, 1, 2)
    (1, 0, 2, 1)
    (1, 1, 0, 2)
    (1, 1, 2, 0)
    (1, 2, 0, 1)
    (1, 2, 1, 0)
    (2, 0, 1, 1)
    (2, 1, 0, 1)
    (2, 1, 1, 0)
    set([(0, 1, 1, 2), (1, 0, 1, 2), (2, 1, 0, 1), (1, 2, 0, 1), (0, 1, 2, 1), (0, 2, 1, 1), (1, 1, 2, 0), (1, 2, 1, 0), (2, 1, 1, 0), (1, 0, 2, 1), (2, 0, 1, 1), (1, 1, 0, 2)])

    Básicamente, hacer un set y seguir añadiendo a la misma. Mejor que hacer listas, etc. que tomar demasiada memoria..
    Espero que ayude a la persona siguiente, mirando hacia fuera 🙂 Comentario el conjunto de ‘actualización’ en la función para ver la diferencia.

    • El , 4 debe ser eliminado por lo que se va a trabajar en las cosas de cualquier longitud. Incluso con que fija, esto no es una gran solución. Para una cosa que almacena todos los elementos en la memoria a la vez, derrotando a algunas de las ventajas de un generador. Por otra parte, que todavía es super ineficiente en términos de tiempo, en algunos casos, donde debe ser instantánea. Trate de for i in dont_repeat([1]*20+[2]): print i; llevará para siempre.
  11. 1

    La mejor solución a este problema he visto que utiliza Knuth del «Algoritmo L» (como se señaló previamente por Gerrat en los comentarios al post original):

    http://stackoverflow.com/questions/12836385/how-can-i-interleave-or-create-unique-permutations-of-two-stings-without-recurs/12837695

    Algunos tiempos:

    Clasificación [1]*12+[0]*12 (2,704,156 único permutaciones):

    Algoritmo de L → 2.43 s

    Lucas Rahne la solución → 8.56 s

    scipy.multiset_permutations() → 16.8 s

  12. 1

    Usted puede hacer una función que utiliza collections.Counter para obtener objetos únicos y sus recuentos de la secuencia dada, y utiliza itertools.combinations elegir combinaciones de índices para cada elemento único en cada llamada recursiva, y el mapa de los índices de vuelta a una lista cuando todos los índices son recogidos:

    from collections import Counter
    from itertools import combinations
    def unique_permutations(seq):
    def index_permutations(counts, index_pool):
    if not counts:
    yield {}
    return
    (item, count), *rest = counts.items()
    rest = dict(rest)
    for indices in combinations(index_pool, count):
    mapping = dict.fromkeys(indices, item)
    for others in index_permutations(rest, index_pool.difference(indices)):
    yield {**mapping, **others}
    indices = set(range(len(seq)))
    for mapping in index_permutations(Counter(seq), indices):
    yield [mapping[i] for i in indices]

    para que [''.join(i) for i in unique_permutations('moon')] devuelve:

    ['moon', 'mono', 'mnoo', 'omon', 'omno', 'nmoo', 'oomn', 'onmo', 'nomo', 'oonm', 'onom', 'noom']
  13. 0

    Encontré el otro día mientras trabajaba en un problema de mi cuenta. Me gusta Luka Rahne del enfoque, pero pensé que usando el Contador de clase en las colecciones de la biblioteca parecía una modesta mejoría. Aquí está mi código:

    def unique_permutations(elements):
    "Returns a list of lists; each sublist is a unique permutations of elements."
    ctr = collections.Counter(elements)
    # Base case with one element: just return the element
    if len(ctr.keys())==1 and ctr[ctr.keys()[0]] == 1:
    return [[ctr.keys()[0]]]
    perms = []
    # For each counter key, find the unique permutations of the set with
    # one member of that key removed, and append the key to the front of
    # each of those permutations.
    for k in ctr.keys():
    ctr_k = ctr.copy()
    ctr_k[k] -= 1
    if ctr_k[k]==0: 
    ctr_k.pop(k)
    perms_k = [[k] + p for p in unique_permutations(ctr_k)]
    perms.extend(perms_k)
    return perms

    Este código devuelve cada permutación como una lista. Si usted alimenta a una cadena, que va a dar una lista de las permutaciones donde cada uno es una lista de caracteres. Si desea que la salida como una lista de cadenas en lugar (por ejemplo, si eres una persona terrible y quiere abusar de mi código para ayudar a los que hacen trampa en el Scrabble), acaba de hacer lo siguiente:

    [''.join(perm) for perm in unique_permutations('abunchofletters')]
  14. 0

    Se me ocurrió un muy adecuado utilizando la implementación itertools.producto en este caso (se trata de una aplicación donde se desea que todas las combinaciones

    unique_perm_list = [''.join(p) for p in itertools.product(['0', '1'], repeat = X) if ''.join(p).count() == somenumber]

    esta es esencialmente una combinación (n sobre k) con n = X y somenumber = k
    itertools.producto() recorre desde k = 0 para k = X posterior filtrado con el conde asegura que sólo las permutaciones con el número de la derecha de los que son lanzados en una lista. usted puede ver fácilmente que funciona al calcular n sobre k y compararlo con el len(unique_perm_list)

  15. 0

    Para generar único permutaciones de ["A","B","C","D"] yo uso el siguiente:

    from itertools import combinations,chain
    l = ["A","B","C","D"]
    combs = (combinations(l, r) for r in range(1, len(l) + 1))
    list_combinations = list(chain.from_iterable(combs))

    Que genera:

    [('A',),
    ('B',),
    ('C',),
    ('D',),
    ('A', 'B'),
    ('A', 'C'),
    ('A', 'D'),
    ('B', 'C'),
    ('B', 'D'),
    ('C', 'D'),
    ('A', 'B', 'C'),
    ('A', 'B', 'D'),
    ('A', 'C', 'D'),
    ('B', 'C', 'D'),
    ('A', 'B', 'C', 'D')]

    Aviso, los duplicados no se crean (por ejemplo, los elementos en combinación con D no se generan, como los que ya existen).

    Ejemplo: Esto puede ser utilizado en la generación de condiciones de mayor o menor orden para la OPERACIÓN de los modelos a través de los datos en una Pandas dataframe.

    import statsmodels.formula.api as smf
    import pandas as pd
    # create some data
    pd_dataframe = pd.Dataframe(somedata)
    response_column = "Y"
    # generate combinations of column/variable names
    l = [col for col in pd_dataframe.columns if col!=response_column]
    combs = (combinations(l, r) for r in range(1, len(l) + 1))
    list_combinations = list(chain.from_iterable(combs))
    # generate OLS input string
    formula_base = '{} ~ '.format(response_column)
    list_for_ols = [":".join(list(item)) for item in list_combinations]
    string_for_ols = formula_base + ' + '.join(list_for_ols)

    Crea…

    Y ~ A + B + C + D + A:B + A:C + A:D + B:C + B:D + C:D + A:B:C + A:B:D + A:C:D + B:C:D + A:B:C:D'

    Que luego pueden ser canalizado para su De regresión OLS

    model = smf.ols(string_for_ols, pd_dataframe).fit()
    model.summary()
  16. -1

    Lo que acerca de

    np.unique(itertools.permutations([1, 1, 1]))

    El problema es que las permutaciones son ahora las filas de una Colección de la matriz, por lo tanto el uso de más memoria, pero puede desplazarse a través de ellos como antes

    perms = np.unique(itertools.permutations([1, 1, 1]))
    for p in perms:
    print p

Dejar respuesta

Please enter your comment!
Please enter your name here