numeros - permutaciones sin repeticion python

permutaciones con valores únicos

Question

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.

Answer 1

¡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. Es mejor que hacer listas, etc. que lleven demasiada memoria. Espero que ayude a la siguiente persona a mirar :-) Comente el conjunto ''actualización'' en la función para ver la diferencia.

Answer 2

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.

Veamos las unique_permutations de (1,2,3,1) para ver cómo funciona:

• unique_elements are 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 damos el resultado.
• Ahora first_element a first_element = 2, y hacemos 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 damos el resultado.
• Finalmente, hacemos lo mismo con first_element = 3.

Answer 3

Aquí hay una solución recursiva al 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))

Answer 4

Debido a que algunas veces las nuevas preguntas se marcan como duplicadas 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]]

Answer 5

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

Answer 6

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

Answer 7

Me encontré con esto el otro día mientras trabajaba en un problema mío. Me gusta el enfoque de Luka Rahne, pero pensé que usar la clase Counter en la biblioteca de colecciones parecía una mejora modesta. 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 le das una cadena, te dará una lista de permutaciones donde cada una es una lista de caracteres. Si quieres el resultado como una lista de cadenas en su lugar (por ejemplo, si eres una persona terrible y quieres abusar de mi código para ayudarte a hacer trampa en Scrabble), solo haz lo siguiente:

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

Answer 8

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

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

Answer 9

Podría intentar usar el conjunto:

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

La llamada para establecer duplicados eliminados

Answer 10

Qué pasa

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

El problema es que las permutaciones ahora son filas de una matriz de Numpy, por lo tanto, usan más memoria, pero pueden recorrerlas como antes

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

Answer 11

Se me ocurrió una implementación muy adecuada usando itertools.product en este caso (esta es una implementación donde quieres todas las combinaciones

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

esto es esencialmente una combinación (n sobre k) con n = X y somenumber = k itertools.product () itera de k = 0 ak = X el filtrado subsiguiente con conteo asegura que solo las permutaciones con el número correcto de unidades se transfieren a una lista. puede ver fácilmente que funciona cuando calcula n sobre k y lo compara con len (unique_perm_list)

Answer 12

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 , una 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 que 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. Vea el código fuente para más detalles.

Answer 13

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 hubo yield función / operador, tuvimos que presionar el resultado en alguna cola en el punto de detención. 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 para que cada resultado se propague a 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 las permutations_with_replacement diferencia de permutations_with_replacement es que cada elemento no puede repetirse más veces que está en perm_unique_helper.