itertools python 3

¿Por qué itertol.permutaciones de Python contienen duplicados?(Cuando la lista original tiene duplicados)

Question

¡Se acepta universalmente que una lista de n símbolos distintos tiene n! permutaciones Sin embargo, cuando los símbolos no son distintos, la convención más común, en matemáticas y en otros lugares, parece ser contar solo con permutaciones distintas. Por lo tanto, las permutaciones de la lista [1, 1, 2] generalmente se consideran
[1, 1, 2], [1, 2, 1], [2, 1, 1] . De hecho, el siguiente código C ++ imprime precisamente esos tres:

int a[] = {1, 1, 2};
do {
    cout<<a[0]<<" "<<a[1]<<" "<<a[2]<<endl;
} while(next_permutation(a,a+3));

Por otro lado, itertools.permutations de Python parece imprimir algo más:

import itertools
for a in itertools.permutations([1, 1, 2]):
    print a

Esto imprime

(1, 1, 2)
(1, 2, 1)
(1, 1, 2)
(1, 2, 1)
(2, 1, 1)
(2, 1, 1)

Como el usuario Artsiom Rudzenka señaló en una respuesta, la documentación de Python lo dice así:

Los elementos se tratan como únicos en función de su posición, no de su valor.

Mi pregunta: ¿por qué se tomó esta decisión de diseño?

Parece que seguir la convención habitual daría resultados que son más útiles (y en realidad es exactamente lo que quiero) ... ¿o hay alguna aplicación del comportamiento de Python que me estoy perdiendo?

[¿O es algún problema de implementación? El algoritmo como en next_permutation , por ejemplo, se explica en StackOverflow aquí (por mí) y se muestra aquí como O (1) amortizado - parece eficiente e implementable en Python, pero Python está haciendo algo aún más eficiente ya que no garantiza el orden lexicográfico basado en el valor? Y si es así, ¿valió la pena el aumento de la eficiencia?]

Answer 1

Es bastante fácil obtener el comportamiento que prefieres envolviéndolo con itertools.permutations , lo que podría haber influido en la decisión. Como se describe en la documentación, itertools está diseñado como una colección de componentes / herramientas para usar en la creación de sus propios iteradores.

def unique(iterable):
    seen = set()
    for x in iterable:
        if x in seen:
            continue
        seen.add(x)
        yield x

for a in unique(permutations([1, 1, 2])):
    print a

(1, 1, 2)
(1, 2, 1)
(2, 1, 1)

Sin embargo, como se señaló en los comentarios, esto podría no ser tan eficiente como le gustaría:

>>> %timeit iterate(permutations([1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2]))
1 loops, best of 3: 4.27 s per loop

>>> %timeit iterate(unique(permutations([1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2])))
1 loops, best of 3: 13.2 s per loop

Tal vez si hay suficiente interés, una nueva función o un argumento opcional para itertools.permutations podrían agregarse a itertools , para generar permutaciones sin duplicados de manera más eficiente.

Answer 2

Estoy aceptando la respuesta de Gareth Rees como la explicación más atractiva (a excepción de una respuesta de los diseñadores de la biblioteca de Python), a saber, que itertools.permutations de itertools.permutations no compara los valores de los elementos. Ahora que lo pienso, esto es sobre lo que se pregunta la pregunta, pero ahora veo cómo podría verse como una ventaja, dependiendo de para qué se usa típicamente itertools.permutations .

Solo para completar, comparé tres métodos para generar permutaciones distintas . El método 1, que es muy ineficiente en cuanto a memoria y tiempo, pero que requiere el código menos nuevo, es envolver las itertools.permutations de Python, como en la respuesta de zeekay. El método 2 es una versión basada en el generador de next_permutation de C ++, de esta publicación de blog . El método 3 es algo que escribí que está aún más cerca del next_permutation algoritmo de next_permutation C ++ ; modifica la lista en el lugar (no la he hecho demasiado general).

def next_permutationS(l):
    n = len(l)
    #Step 1: Find tail
    last = n-1 #tail is from `last` to end
    while last>0:
        if l[last-1] < l[last]: break
        last -= 1
    #Step 2: Increase the number just before tail
    if last>0:
        small = l[last-1]
        big = n-1
        while l[big] <= small: big -= 1
        l[last-1], l[big] = l[big], small
    #Step 3: Reverse tail
    i = last
    j = n-1
    while i < j:
        l[i], l[j] = l[j], l[i]
        i += 1
        j -= 1
    return last>0

Aquí hay algunos resultados. Ahora tengo más respeto por la función incorporada de Python: es de tres a cuatro veces más rápido que los otros métodos cuando los elementos son todos (o casi todos) distintos. Por supuesto, cuando hay muchos elementos repetidos, usarlo es una idea terrible.

Some results ("us" means microseconds):

l                                       m_itertoolsp  m_nextperm_b  m_nextperm_s
[1, 1, 2]                               5.98 us       12.3 us       7.54 us
[1, 2, 3, 4, 5, 6]                      0.63 ms       2.69 ms       1.77 ms
[1, 2, 3, 4, 5, 6, 7, 8, 9, 10]         6.93 s        13.68 s       8.75 s

[1, 2, 3, 4, 6, 6, 6]                   3.12 ms       3.34 ms       2.19 ms
[1, 2, 2, 2, 2, 3, 3, 3, 3, 3]          2400 ms       5.87 ms       3.63 ms
[1, 1, 1, 1, 1, 1, 1, 1, 1, 2]          2320000 us    89.9 us       51.5 us
[1, 1, 2, 2, 3, 3, 4, 4, 4, 4, 4, 4]    429000 ms     361 ms        228 ms

El código está here si alguien quiere explorar.

Answer 3

No puedo hablar por el diseñador de itertools.permutations (Raymond Hettinger), pero me parece que hay un par de puntos a favor del diseño:

Primero, si usó un next_permutation estilo next_permutation , entonces estaría restringido a pasar objetos que admitan un ordenamiento lineal. Mientras que itertools.permutations proporciona permutaciones de cualquier tipo de objeto. Imagina lo molesto que sería esto:

>>> list(itertools.permutations([1+2j, 1-2j, 2+j, 2-j]))
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
TypeError: no ordering relation is defined for complex numbers

En segundo lugar, al no probar la igualdad en los objetos, itertools.permutations evita pagar el costo de llamar al método __eq__ en el caso habitual en el que no es necesario.

Básicamente, itertools.permutations resuelve el caso común de manera confiable y económica. Ciertamente, se debe argumentar que itertools debe proporcionar una función que evite las permutaciones duplicadas, pero tal función debe ser además de itertools.permutations , no en lugar de ello. ¿Por qué no escribir esa función y enviar un parche?

Answer 4

Tal vez me equivoque, pero parece que la razón de esto está en ''Los elementos se tratan como únicos en función de su posición, no de su valor. Entonces, si los elementos de entrada son únicos, no habrá valores de repetición en cada permutación. Ha especificado (1,1,2) y desde su punto de vista 1 en el índice 0 y 1 en el índice 1 son los mismos, pero esto no es así ya que las implementaciones de python de permutaciones usaron índices en lugar de valores.

Entonces, si echamos un vistazo a la implementación predeterminada de las permutaciones de Python, veremos que utiliza índices:

def permutations(iterable, r=None):
    pool = tuple(iterable)
    n = len(pool)
    r = n if r is None else r
    for indices in product(range(n), repeat=r):
        if len(set(indices)) == r:
            yield tuple(pool[i] for i in indices)

Por ejemplo, si cambia su entrada a [1,2,3] obtendrá las permutaciones correctas ([(1, 2, 3), (1, 3, 2), (2, 1, 3), (2, 3 , 1), (3, 1, 2), (3, 2, 1)]) ya que los valores son únicos.

Answer 5

También me sorprende que itertools no tenga una función para el concepto más intuitivo de permutaciones únicas. Generar permutaciones repetitivas solo para seleccionar las únicas entre ellas está fuera de discusión para cualquier aplicación seria.

He escrito mi propia función de generador iterativo que se comporta de manera similar a itertools.permutations pero no devuelve duplicados. Solo se consideran las permutaciones de la lista original, se pueden crear itertools con la biblioteca de itertools estándar.

def unique_permutations(t):
    lt = list(t)
    lnt = len(lt)
    if lnt == 1:
        yield lt
    st = set(t)
    for d in st:
        lt.remove(d)
        for perm in unique_permutations(lt):
            yield [d]+perm
        lt.append(d)