¿Cómo generar todas las permutaciones de una lista?

592

¿Cómo se generan todas las permutaciones de una lista en Python, independientemente del tipo de elementos en esa lista?

Por ejemplo:

permutations([])
[]

permutations([1])
[1]

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

permutations([1, 2, 3])
[1, 2, 3]
[1, 3, 2]
[2, 1, 3]
[2, 3, 1]
[3, 1, 2]
[3, 2, 1]
Ricardo Reyes
fuente
55
Estoy de acuerdo con la respuesta recursiva y aceptada - HOY. Sin embargo, esto aún persiste como un gran problema informático. La respuesta aceptada resuelve este problema con una complejidad exponencial (2 ^ NN = len (lista)) Resuélvelo (o demuestra que no puedes) en tiempo polinómico :) Ver "problema de vendedor ambulante"
FlipMcF
38
@FlipMcF Será difícil "resolverlo" en tiempo polinómico, dado que toma tiempo factorial incluso enumerar la salida ... así que no, no es posible.
Thomas

Respuestas:

489

A partir de Python 2.6 (y si estás en Python 3) tiene una norma-biblioteca herramienta para esto: itertools.permutations.

import itertools
list(itertools.permutations([1, 2, 3]))

Si está utilizando un Python anterior (<2.6) por alguna razón o simplemente tiene curiosidad por saber cómo funciona, aquí hay un buen enfoque, tomado de http://code.activestate.com/recipes/252178/ :

def all_perms(elements):
    if len(elements) <=1:
        yield elements
    else:
        for perm in all_perms(elements[1:]):
            for i in range(len(elements)):
                # nb elements[0:1] works in both string and list contexts
                yield perm[:i] + elements[0:1] + perm[i:]

Un par de enfoques alternativos se enumeran en la documentación de itertools.permutations. Aquí hay uno:

def permutations(iterable, r=None):
    # permutations('ABCD', 2) --> AB AC AD BA BC BD CA CB CD DA DB DC
    # permutations(range(3)) --> 012 021 102 120 201 210
    pool = tuple(iterable)
    n = len(pool)
    r = n if r is None else r
    if r > n:
        return
    indices = range(n)
    cycles = range(n, n-r, -1)
    yield tuple(pool[i] for i in indices[:r])
    while n:
        for i in reversed(range(r)):
            cycles[i] -= 1
            if cycles[i] == 0:
                indices[i:] = indices[i+1:] + indices[i:i+1]
                cycles[i] = n - i
            else:
                j = cycles[i]
                indices[i], indices[-j] = indices[-j], indices[i]
                yield tuple(pool[i] for i in indices[:r])
                break
        else:
            return

Y otro, basado en itertools.product:

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)
Eli Bendersky
fuente
14
Esta y otras soluciones recursivas tienen el riesgo potencial de consumir toda la RAM si la lista permutada es lo suficientemente grande
Boris Gorelik,
3
También alcanzan el límite de recursión (y mueren) con grandes listas
dbr
58
bgbg, dbr: está utilizando un generador, por lo que la función en sí no consumirá memoria. Le queda a usted cómo consumir el iterador devuelto por all_perms (digamos que podría escribir cada iteración en el disco y no preocuparse por la memoria). Sé que esta publicación es antigua, pero la estoy escribiendo para beneficio de todos los que la leen ahora. También ahora, la mejor manera sería usar itertools.permutations () como lo señalan muchos.
Jagtesh Chadha
18
No solo un generador. Está utilizando generadores anidados, que cada uno cede al anterior en la pila de llamadas, en caso de que no esté claro. Utiliza memoria O (n), lo cual es bueno.
cdunn2001
1
PD: lo arreglé, con en for i in range(len(elements))lugar de for i in range(len(elements)+1). De hecho, el elemento seleccionado elements[0:1]puede estar en len(elements)diferentes posiciones, en el resultado, no len(elements)+1.
Eric O Lebigot
339

Y en Python 2.6 en adelante:

import itertools
itertools.permutations([1,2,3])

(devuelto como generador. Utilícelo list(permutations(l))para regresar como una lista).

Brian
fuente
15
También funciona en Python 3
wheleph
10
Observe que existe un rparámetro, por ejemplo itertools.permutations([1,2,3], r=2), que generará todas las permutaciones posibles seleccionando 2 elementos:[(1, 2), (1, 3), (2, 1), (2, 3), (3, 1), (3, 2)]
toto_tico
278

El siguiente código con Python 2.6 y superior SOLAMENTE

Primero, importa itertools:

import itertools

Permutación (el orden importa):

print list(itertools.permutations([1,2,3,4], 2))
[(1, 2), (1, 3), (1, 4),
(2, 1), (2, 3), (2, 4),
(3, 1), (3, 2), (3, 4),
(4, 1), (4, 2), (4, 3)]

Combinación (el orden NO importa):

print list(itertools.combinations('123', 2))
[('1', '2'), ('1', '3'), ('2', '3')]

Producto cartesiano (con varios iterables):

print list(itertools.product([1,2,3], [4,5,6]))
[(1, 4), (1, 5), (1, 6),
(2, 4), (2, 5), (2, 6),
(3, 4), (3, 5), (3, 6)]

Producto cartesiano (con uno iterable y en sí mismo):

print list(itertools.product([1,2], repeat=3))
[(1, 1, 1), (1, 1, 2), (1, 2, 1), (1, 2, 2),
(2, 1, 1), (2, 1, 2), (2, 2, 1), (2, 2, 2)]
e-satis
fuente
`print list (itertools.permutations ([1,2,3,4], 2)) ^` SyntaxError: sintaxis no válida` Recién comenzando a usar VS Code ¿Qué hice mal? El puntero apunta debajo de la "t" de "lista"
gus
39
def permutations(head, tail=''):
    if len(head) == 0: print tail
    else:
        for i in range(len(head)):
            permutations(head[0:i] + head[i+1:], tail+head[i])

llamado:

permutations('abc')
kx2k
fuente
¿Por qué imprimir cola y luego devolver Ninguno? ¿Por qué no devolver la cola en su lugar? ¿Por qué no devolver nada de todos modos?
bugmenot123
30
#!/usr/bin/env python

def perm(a, k=0):
   if k == len(a):
      print a
   else:
      for i in xrange(k, len(a)):
         a[k], a[i] = a[i] ,a[k]
         perm(a, k+1)
         a[k], a[i] = a[i], a[k]

perm([1,2,3])

Salida:

[1, 2, 3]
[1, 3, 2]
[2, 1, 3]
[2, 3, 1]
[3, 2, 1]
[3, 1, 2]

Como estoy intercambiando el contenido de la lista, se requiere un tipo de secuencia mutable como entrada. Por ejemplo perm(list("ball")), funcionará y perm("ball")no lo hará porque no puede cambiar una cadena.

Esta implementación de Python está inspirada en el algoritmo presentado en el libro Algoritmos informáticos de Horowitz, Sahni y Rajasekeran .

Silveira Neto
fuente
Supongo que k es la longitud o permutaciones. Para k = 2 salidas [1, 2, 3]. ¿No debería ser (1, 2) (1, 3) (2, 1) (2, 3) (3, 1) (3, 2) ??
Konstantinos Monachopoulos
k es el índice del elemento que desea intercambiar
sf8193
22

Esta solución implementa un generador, para evitar mantener todas las permutaciones en la memoria:

def permutations (orig_list):
    if not isinstance(orig_list, list):
        orig_list = list(orig_list)

    yield orig_list

    if len(orig_list) == 1:
        return

    for n in sorted(orig_list):
        new_list = orig_list[:]
        pos = new_list.index(n)
        del(new_list[pos])
        new_list.insert(0, n)
        for resto in permutations(new_list[1:]):
            if new_list[:1] + resto <> orig_list:
                yield new_list[:1] + resto
Ricardo Reyes
fuente
16

En un estilo funcional

def addperm(x,l):
    return [ l[0:i] + [x] + l[i:]  for i in range(len(l)+1) ]

def perm(l):
    if len(l) == 0:
        return [[]]
    return [x for y in perm(l[1:]) for x in addperm(l[0],y) ]

print perm([ i for i in range(3)])

El resultado:

[[0, 1, 2], [1, 0, 2], [1, 2, 0], [0, 2, 1], [2, 0, 1], [2, 1, 0]]
Paolo
fuente
15

El siguiente código es una permutación in situ de una lista dada, implementada como un generador. Como solo devuelve referencias a la lista, la lista no debe modificarse fuera del generador. La solución no es recursiva, por lo que utiliza poca memoria. Funciona bien también con múltiples copias de elementos en la lista de entrada.

def permute_in_place(a):
    a.sort()
    yield list(a)

    if len(a) <= 1:
        return

    first = 0
    last = len(a)
    while 1:
        i = last - 1

        while 1:
            i = i - 1
            if a[i] < a[i+1]:
                j = last - 1
                while not (a[i] < a[j]):
                    j = j - 1
                a[i], a[j] = a[j], a[i] # swap the values
                r = a[i+1:last]
                r.reverse()
                a[i+1:last] = r
                yield list(a)
                break
            if i == first:
                a.reverse()
                return

if __name__ == '__main__':
    for n in range(5):
        for a in permute_in_place(range(1, n+1)):
            print a
        print

    for a in permute_in_place([0, 0, 1, 1, 1]):
        print a
    print
Ber
fuente
15

Una forma bastante obvia en mi opinión podría ser también:

def permutList(l):
    if not l:
            return [[]]
    res = []
    for e in l:
            temp = l[:]
            temp.remove(e)
            res.extend([[e] + r for r in permutList(temp)])

    return res
tzwenn
fuente
11
list2Perm = [1, 2.0, 'three']
listPerm = [[a, b, c]
            for a in list2Perm
            for b in list2Perm
            for c in list2Perm
            if ( a != b and b != c and a != c )
            ]
print listPerm

Salida:

[
    [1, 2.0, 'three'], 
    [1, 'three', 2.0], 
    [2.0, 1, 'three'], 
    [2.0, 'three', 1], 
    ['three', 1, 2.0], 
    ['three', 2.0, 1]
]
zmk
fuente
2
Si bien técnicamente produce la salida deseada, está resolviendo algo que podría ser O (n lg n) en O (n ^ n) - "ligeramente" ineficiente para conjuntos grandes.
James
3
@ James: Estoy un poco confundido por el O (n log n) que das: el número de permutaciones es n !, que ya es mucho mayor que O (n log n); entonces, no puedo ver cómo una solución podría ser O (n log n). Sin embargo, es cierto que esta solución está en O (n ^ n), que es mucho más grande que n !, como se desprende de la aproximación de Stirling.
Eric O Lebigot
9

Utilicé un algoritmo basado en el sistema de números factoriales : para una lista de longitud n, puede ensamblar cada elemento de permutación por elemento, seleccionando entre los elementos que quedan en cada etapa. Tiene n opciones para el primer elemento, n-1 para el segundo y solo una para el último, por lo que puede usar los dígitos de un número en el sistema de números factoriales como índices. De esta manera, los números del 0 al n! -1 corresponden a todas las permutaciones posibles en orden lexicográfico.

from math import factorial
def permutations(l):
    permutations=[]
    length=len(l)
    for x in xrange(factorial(length)):
        available=list(l)
        newPermutation=[]
        for radix in xrange(length, 0, -1):
            placeValue=factorial(radix-1)
            index=x/placeValue
            newPermutation.append(available.pop(index))
            x-=index*placeValue
        permutations.append(newPermutation)
    return permutations

permutations(range(3))

salida:

[[0, 1, 2], [0, 2, 1], [1, 0, 2], [1, 2, 0], [2, 0, 1], [2, 1, 0]]

Este método no es recursivo, pero es un poco más lento en mi computadora y xrange genera un error cuando n! es demasiado grande para convertirlo en un entero C largo (n = 13 para mí). Fue suficiente cuando lo necesitaba, pero no es itertools.permutations por asomo.

tiempoeeee
fuente
3
Hola, bienvenido a Stack Overflow. Aunque publicar el método de fuerza bruta tiene sus ventajas, si no cree que su solución es mejor que la solución aceptada, probablemente no debería publicarla (especialmente en una pregunta anterior que ya tiene tantas respuestas).
Hannele
1
En realidad estaba buscando un enfoque de fuerza bruta que no sea de biblioteca, ¡así que gracias!
Jay Taylor
8

Tenga en cuenta que este algoritmo tiene una n factorialcomplejidad temporal, donde nes la longitud de la lista de entrada

Imprima los resultados en la ejecución:

global result
result = [] 

def permutation(li):
if li == [] or li == None:
    return

if len(li) == 1:
    result.append(li[0])
    print result
    result.pop()
    return

for i in range(0,len(li)):
    result.append(li[i])
    permutation(li[:i] + li[i+1:])
    result.pop()    

Ejemplo:

permutation([1,2,3])

Salida:

[1, 2, 3]
[1, 3, 2]
[2, 1, 3]
[2, 3, 1]
[3, 1, 2]
[3, 2, 1]
Chen Xie
fuente
8

De hecho, uno puede iterar sobre el primer elemento de cada permutación, como en la respuesta de tzwenn. Sin embargo, es más eficiente escribir esta solución de esta manera:

def all_perms(elements):
    if len(elements) <= 1:
        yield elements  # Only permutation possible = no permutation
    else:
        # Iteration over the first element in the result permutation:
        for (index, first_elmt) in enumerate(elements):
            other_elmts = elements[:index]+elements[index+1:]
            for permutation in all_perms(other_elmts): 
                yield [first_elmt] + permutation

Esta solución es aproximadamente un 30% más rápida, aparentemente gracias a que la recursión termina en len(elements) <= 1lugar de 0. También es mucho más eficiente en la memoria, ya que utiliza una función de generador (a través yield), como en la solución de Riccardo Reyes.

Eric O Lebigot
fuente
6

Esto está inspirado en la implementación de Haskell utilizando la comprensión de la lista:

def permutation(list):
    if len(list) == 0:
        return [[]]
    else:
        return [[x] + ys for x in list for ys in permutation(delete(list, x))]

def delete(list, item):
    lc = list[:]
    lc.remove(item)
    return lc
alcancía
fuente
6

Implementación regular (sin rendimiento; hará todo en la memoria):

def getPermutations(array):
    if len(array) == 1:
        return [array]
    permutations = []
    for i in range(len(array)): 
        # get all perm's of subarray w/o current item
        perms = getPermutations(array[:i] + array[i+1:])  
        for p in perms:
            permutations.append([array[i], *p])
    return permutations

Implementación de rendimiento:

def getPermutations(array):
    if len(array) == 1:
        yield array
    else:
        for i in range(len(array)):
            perms = getPermutations(array[:i] + array[i+1:])
            for p in perms:
                yield [array[i], *p]

La idea básica es repasar todos los elementos de la matriz para la primera posición, y luego, en la segunda posición, repasar el resto de los elementos sin el elemento elegido para la primera, etc. Puede hacerlo con recursividad , donde el criterio de detención es llegar a una matriz de 1 elemento, en cuyo caso devuelve esa matriz.

ingrese la descripción de la imagen aquí

David Refaeli
fuente
Esto no funciona para mí _> ValueError: los operandos no se pudieron transmitir junto con las formas (0,) (2,) , para esta línea:perms = getPermutations(array[:i] + array[i+1:])
RK1
@ RK1, ¿cuál fue la entrada?
David Refaeli
Estoy pasando una numpymatriz _> getPermutations(np.array([1, 2, 3])), veo que funciona para una lista, me confundí porque el argumento es array:)
RK1
@ RK1 me alegro de que funcione :-) list es una palabra clave en python, por lo que generalmente no es una buena idea llamar a su parámetro una palabra clave, ya que la "sombreará". Así que uso la matriz de palabras, ya que esta es la funcionalidad real de la lista que estoy usando, su forma de matriz. Supongo que si escribiera documentación, lo aclararía. También creo que las preguntas básicas de "entrevista" deben resolverse sin paquetes externos, como numpy.
David Refaeli
Jaja eso es cierto, sí, estaba tratando de usarlo numbay se volvió codicioso con la velocidad, así que traté de usarlo exclusivamente con numpymatrices
RK1
4

Para el rendimiento, una solución complicada inspirada en Knuth , (p22):

from numpy import empty, uint8
from math import factorial

def perms(n):
    f = 1
    p = empty((2*n-1, factorial(n)), uint8)
    for i in range(n):
        p[i, :f] = i
        p[i+1:2*i+1, :f] = p[:i, :f]  # constitution de blocs
        for j in range(i):
            p[:i+1, f*(j+1):f*(j+2)] = p[j+1:j+i+2, :f]  # copie de blocs
        f = f*(i+1)
    return p[:n, :]

Copiar grandes bloques de memoria ahorra tiempo: es 20 veces más rápido que list(itertools.permutations(range(n)):

In [1]: %timeit -n10 list(permutations(range(10)))
10 loops, best of 3: 815 ms per loop

In [2]: %timeit -n100 perms(10) 
100 loops, best of 3: 40 ms per loop
BM
fuente
3
from __future__ import print_function

def perm(n):
    p = []
    for i in range(0,n+1):
        p.append(i)
    while True:
        for i in range(1,n+1):
            print(p[i], end=' ')
        print("")
        i = n - 1
        found = 0
        while (not found and i>0):
            if p[i]<p[i+1]:
                found = 1
            else:
                i = i - 1
        k = n
        while p[i]>p[k]:
            k = k - 1
        aux = p[i]
        p[i] = p[k]
        p[k] = aux
        for j in range(1,(n-i)/2+1):
            aux = p[i+j]
            p[i+j] = p[n-j+1]
            p[n-j+1] = aux
        if not found:
            break

perm(5)
Adrian Statescu
fuente
3

Aquí hay un algoritmo que funciona en una lista sin crear nuevas listas intermedias similares a la solución de Ber en https://stackoverflow.com/a/108651/184528 .

def permute(xs, low=0):
    if low + 1 >= len(xs):
        yield xs
    else:
        for p in permute(xs, low + 1):
            yield p        
        for i in range(low + 1, len(xs)):        
            xs[low], xs[i] = xs[i], xs[low]
            for p in permute(xs, low + 1):
                yield p        
            xs[low], xs[i] = xs[i], xs[low]

for p in permute([1, 2, 3, 4]):
    print p

Puede probar el código usted mismo aquí: http://repl.it/J9v

cdiggins
fuente
3

La belleza de la recursividad:

>>> import copy
>>> def perm(prefix,rest):
...      for e in rest:
...              new_rest=copy.copy(rest)
...              new_prefix=copy.copy(prefix)
...              new_prefix.append(e)
...              new_rest.remove(e)
...              if len(new_rest) == 0:
...                      print new_prefix + new_rest
...                      continue
...              perm(new_prefix,new_rest)
... 
>>> perm([],['a','b','c','d'])
['a', 'b', 'c', 'd']
['a', 'b', 'd', 'c']
['a', 'c', 'b', 'd']
['a', 'c', 'd', 'b']
['a', 'd', 'b', 'c']
['a', 'd', 'c', 'b']
['b', 'a', 'c', 'd']
['b', 'a', 'd', 'c']
['b', 'c', 'a', 'd']
['b', 'c', 'd', 'a']
['b', 'd', 'a', 'c']
['b', 'd', 'c', 'a']
['c', 'a', 'b', 'd']
['c', 'a', 'd', 'b']
['c', 'b', 'a', 'd']
['c', 'b', 'd', 'a']
['c', 'd', 'a', 'b']
['c', 'd', 'b', 'a']
['d', 'a', 'b', 'c']
['d', 'a', 'c', 'b']
['d', 'b', 'a', 'c']
['d', 'b', 'c', 'a']
['d', 'c', 'a', 'b']
['d', 'c', 'b', 'a']
darxtrix
fuente
3

Este algoritmo es el más efectivo, evita el paso de matriz y la manipulación en llamadas recursivas, funciona en Python 2, 3:

def permute(items):
    length = len(items)
    def inner(ix=[]):
        do_yield = len(ix) == length - 1
        for i in range(0, length):
            if i in ix: #avoid duplicates
                continue
            if do_yield:
                yield tuple([items[y] for y in ix + [i]])
            else:
                for p in inner(ix + [i]):
                    yield p
    return inner()

Uso:

for p in permute((1,2,3)):
    print(p)

(1, 2, 3)
(1, 3, 2)
(2, 1, 3)
(2, 3, 1)
(3, 1, 2)
(3, 2, 1)
Cmyker
fuente
3
def pzip(c, seq):
    result = []
    for item in seq:
        for i in range(len(item)+1):
            result.append(item[i:]+c+item[:i])
    return result


def perm(line):
    seq = [c for c in line]
    if len(seq) <=1 :
        return seq
    else:
        return pzip(seq[0], perm(seq[1:]))
kumar viril
fuente
3

OTRO ENFOQUE (sin libs)

def permutation(input):
    if len(input) == 1:
        return input if isinstance(input, list) else [input]

    result = []
    for i in range(len(input)):
        first = input[i]
        rest = input[:i] + input[i + 1:]
        rest_permutation = permutation(rest)
        for p in rest_permutation:
            result.append(first + p)
    return result

La entrada puede ser una cadena o una lista

print(permutation('abcd'))
print(permutation(['a', 'b', 'c', 'd']))
Tatsu
fuente
Esto no funciona para una lista con enteros, por ejemplo. [1, 2, 3]vuelve[6, 6, 6, 6, 6, 6]
RK1
@ RK1, puedes probar estoprint(permutation(['1','2','3']))
Tatsu
Gracias, eso funciona
RK1
3

Descargo de responsabilidad: enchufe sin forma por autor del paquete. :)

El paquete trotter es diferente de la mayoría de las implementaciones en el sentido de que genera pseudo listas que en realidad no contienen permutaciones, sino que describen asignaciones entre permutaciones y posiciones respectivas en un orden, lo que permite trabajar con 'listas' muy grandes de permutaciones, como se muestra en esta demo que realiza operaciones y búsquedas bastante instantáneas en una pseudo-lista que 'contiene' todas las permutaciones de las letras en el alfabeto, sin usar más memoria o procesamiento que una página web típica.

En cualquier caso, para generar una lista de permutaciones, podemos hacer lo siguiente.

import trotter

my_permutations = trotter.Permutations(3, [1, 2, 3])

print(my_permutations)

for p in my_permutations:
    print(p)

Salida:

Una pseudo-lista que contiene 6 3-permutaciones de [1, 2, 3].
[1, 2, 3]
[1, 3, 2]
[3, 1, 2]
[3, 2, 1]
[2, 3, 1]
[2, 1, 3]
Richard Ambler
fuente
2

Generar todas las permutaciones posibles.

Estoy usando python3.4:

def calcperm(arr, size):
    result = set([()])
    for dummy_idx in range(size):
        temp = set()
        for dummy_lst in result:
            for dummy_outcome in arr:
                if dummy_outcome not in dummy_lst:
                    new_seq = list(dummy_lst)
                    new_seq.append(dummy_outcome)
                    temp.add(tuple(new_seq))
        result = temp
    return result

Casos de prueba:

lst = [1, 2, 3, 4]
#lst = ["yellow", "magenta", "white", "blue"]
seq = 2
final = calcperm(lst, seq)
print(len(final))
print(final)
Miled Louis Rizk
fuente
2

Para ahorrarles a las personas posibles horas de búsqueda y experimentación, aquí está la solución de permutaciones no recursiva en Python que también funciona con Numba (a partir del v. 0.41):

@numba.njit()
def permutations(A, k):
    r = [[i for i in range(0)]]
    for i in range(k):
        r = [[a] + b for a in A for b in r if (a in b)==False]
    return r
permutations([1,2,3],3)
[[1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2], [3, 2, 1]]

Para dar una impresión sobre el rendimiento:

%timeit permutations(np.arange(5),5)

243 µs ± 11.1 µs per loop (mean ± std. dev. of 7 runs, 1 loop each)
time: 406 ms

%timeit list(itertools.permutations(np.arange(5),5))
15.9 µs ± 8.61 ns per loop (mean ± std. dev. of 7 runs, 100000 loops each)
time: 12.9 s

Por lo tanto, use esta versión solo si debe llamarla desde la función njitted, de lo contrario, prefiera la implementación de itertools.

Anatoly Alekseev
fuente
1

Veo mucha iteración dentro de estas funciones recursivas, no exactamente pura recursión ...

así que para aquellos de ustedes que no pueden cumplir ni siquiera un solo bucle, aquí hay una solución grosera, totalmente innecesaria y totalmente recursiva

def all_insert(x, e, i=0):
    return [x[0:i]+[e]+x[i:]] + all_insert(x,e,i+1) if i<len(x)+1 else []

def for_each(X, e):
    return all_insert(X[0], e) + for_each(X[1:],e) if X else []

def permute(x):
    return [x] if len(x) < 2 else for_each( permute(x[1:]) , x[0])


perms = permute([1,2,3])
Karo Castro-Wunsch
fuente
1

Otra solución:

def permutation(flag, k =1 ):
    N = len(flag)
    for i in xrange(0, N):
        if flag[i] != 0:
            continue
        flag[i] = k 
        if k == N:
            print flag
        permutation(flag, k+1)
        flag[i] = 0

permutation([0, 0, 0])
anhldbk
fuente
0

Mi solución Python:

def permutes(input,offset):
    if( len(input) == offset ):
        return [''.join(input)]

    result=[]        
    for i in range( offset, len(input) ):
         input[offset], input[i] = input[i], input[offset]
         result = result + permutes(input,offset+1)
         input[offset], input[i] = input[i], input[offset]
    return result

# input is a "string"
# return value is a list of strings
def permutations(input):
    return permutes( list(input), 0 )

# Main Program
print( permutations("wxyz") )
abelenky
fuente
0
def permutation(word, first_char=None):
    if word == None or len(word) == 0: return []
    if len(word) == 1: return [word]

    result = []
    first_char = word[0]
    for sub_word in permutation(word[1:], first_char):
        result += insert(first_char, sub_word)
    return sorted(result)

def insert(ch, sub_word):
    arr = [ch + sub_word]
    for i in range(len(sub_word)):
        arr.append(sub_word[i:] + ch + sub_word[:i])
    return arr


assert permutation(None) == []
assert permutation('') == []
assert permutation('1')  == ['1']
assert permutation('12') == ['12', '21']

print permutation('abc')

Salida: ['abc', 'acb', 'bac', 'bca', 'cab', 'cba']

Ilgorbek Kuchkarov
fuente
0

Utilizando Counter

from collections import Counter

def permutations(nums):
    ans = [[]]
    cache = Counter(nums)

    for idx, x in enumerate(nums):
        result = []
        for items in ans:
            cache1 = Counter(items)
            for id, n in enumerate(nums):
                if cache[n] != cache1[n] and items + [n] not in result:
                    result.append(items + [n])

        ans = result
    return ans
permutations([1, 2, 2])
> [[1, 2, 2], [2, 1, 2], [2, 2, 1]]
Hola Mundo
fuente