Pregunta permutaciones con valores únicos


itertools.permutations genera donde sus elementos se tratan como únicos en función de su posición, no de su valor. Entonces, 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)]

Filtrar después no es posible porque la cantidad de permutaciones es demasiado grande en mi caso.

¿Alguien sabe de un algoritmo adecuado para esto?

¡Muchas gracias!

EDITAR:

Lo que básicamente quiero es lo 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.product es demasiado grande.

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


57
2018-06-08 19:51


origen


Respuestas:


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 esto):

Reescribí el programa superior para que sea más largo pero más legible

Por lo general, me cuesta explicar cómo funciona algo, pero déjame intentarlo. Para entender cómo funciona esto, debes entender algo similar, pero un programa más simple que ceda todas las permutaciones con repetición.

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 significa profundidad en permutations_helper y tiene dos funciones. Una función es detener la condición de nuestro algoritmo recursivo y otra es para la lista de resultados, que se pasa.

En lugar de devolver cada resultado, lo cedemos. Si no hubiera función / operador yield tuvimos que presionar el resultado en alguna cola en el punto de la condición de parada. Pero de esta manera, una vez que se detiene la condición, el resultado se propaga a través de toda la pila hasta la persona que llama. Ese es el propósito de
for g in perm_unique_helper(listunique,result_list,d-1): yield g por lo que cada resultado se propaga hasta la persona que llama.

Volver al programa original: Tenemos una lista de elementos únicos. Antes de que podamos usar cada elemento, debemos verificar cuántos de ellos todavía están disponibles para insertarlo en la lista de resultados. El funcionamiento de este programa es muy similar en comparación con permutations_with_replacement La diferencia es que cada elemento no puede repetirse más veces que está en perm_unique_helper.


44
2018-06-08 20:59



Esto se basa en los detalles de implementación que cualquier permutación de un iterable ordenado está en orden ordenado a menos que sean duplicados de permutaciones anteriores.

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')

18
2018-06-08 21:11



Debido a que a veces las nuevas preguntas se marcan como duplicados y sus autores son referidos 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]]

15
2017-10-27 16:27



Aproximadamente tan rápido como la respuesta de Luka Rahne, pero más corto y 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 recursivamente estableciendo el primer elemento (iterando a través de todos los elementos únicos) e iterando a través de las permutaciones para todos los elementos restantes.

Repasemos el 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 el primero 1)
    • Realizamos iteraciones (recursivamente) 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, insertamos el first_element: (1, 1,2,3), (1, 1,3,2), ... y produce el resultado.
  • Ahora iteramos a first_element = 2, y haz lo mismo que arriba.
    • remaining_elements son [1,3,1] (es decir, 1,2,3,1 menos los primeros 2)
    • Nos iteramos a través de las permutaciones de los elementos restantes: (1, 1, 3), (1, 3, 1), (3, 1, 1)
    • Para cada sub_permutation, insertamos el first_element: (2, 1, 1, 3), (2, 1, 3, 1), (2, 3, 1, 1) ... y produce el resultado.
  • Finalmente, hacemos lo mismo con first_element = 3.

10
2018-05-31 13:32



Podría intentar usar el conjunto:

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

La llamada para establecer duplicados eliminados


9
2018-06-08 19:57



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]]

8
2017-08-18 09:09



Parece que estás buscando itertools.combinations () docs.python.org

list(itertools.combinations([1, 1, 1],3))
[(1, 1, 1)]

3
2018-06-08 19:57



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

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

Sin embargo, esta técnica calcula derrochadamente las permutaciones repetidas y las descarta. 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)]

Actuación

Usando un iterable más grande, compararemos las actuaciones entre las técnicas ingenua y de terceros.

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 un orden de magnitud más rápido.


Detalles

Desde la fuente, se usa un algoritmo de recursión (como se ve en la respuesta aceptada) para calcular permutaciones distintas, obviando de este modo los cálculos innecesarios. Ver el código fuente para más detalles.


3
2017-12-30 20:37



¡Se topó con esta pregunta mientras buscaba algo yo 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, crea un conjunto y sigue añadiéndolo. Mejor que hacer listas, etc. que requieren demasiada memoria. Espero que ayude a la siguiente persona a mirar :-) Comenta el conjunto 'actualización' en la función para ver la diferencia.


1
2017-07-13 05:27