Como gerar todas as permutações de uma lista?

592

Como você gera todas as permutações de uma lista no Python, independentemente do tipo de elementos nessa lista?

Por exemplo:

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
fonte
5
Concordo com a resposta recursiva e aceita - HOJE. No entanto, isso ainda existe como um enorme problema de ciência da computação. A resposta aceita resolve esse problema com complexidade exponencial (2 ^ NN = len (lista)) Resolva-o (ou prove que não pode) em tempo polinomial :) Veja "problema do vendedor ambulante"
FlipMcF 26/09/09
38
@FlipMcF Será difícil "resolvê-lo" em tempo polinomial, já que leva tempo fatorial para apenas enumerar a saída ... então, não, não é possível.
Thomas

Respostas:

489

Começando com Python 2.6 (e se você estiver em Python 3) você tem um padrão da biblioteca ferramenta para isso: itertools.permutations.

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

Se você estiver usando um Python mais antigo (<2.6) por algum motivo ou estiver curioso para saber como ele funciona, aqui está uma boa abordagem, feita em 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:]

Algumas abordagens alternativas estão listadas na documentação de itertools.permutations. Aqui está um:

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

E outro, baseado em 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
fonte
14
Esta e outras soluções recursiva tem um potencial perigo de comer toda a RAM se a lista permutated é grande o suficiente
Boris Gorelik
3
Eles também atingir o limite de recursividade (e morrer) com grandes listas
DBR
58
bgbg, dbr: Está usando um gerador, para que a função em si não consuma memória. É deixado para você como consumir o iterador retornado por all_perms (digamos que você possa gravar cada iteração no disco e não se preocupar com memória). Eu sei que este post é antigo, mas estou escrevendo isso para o benefício de todos que o lêem agora. Também agora, a melhor maneira seria usar itertools.permutations (), como apontado por muitos.
Jagtesh Chadha
18
Não é apenas um gerador. Ele está usando geradores aninhados, que cada um gera o anterior na pilha de chamadas, caso isso não esteja claro. Ele usa memória O (n), o que é bom.
cdunn2001
1
PS: Eu consertei, em for i in range(len(elements))vez de for i in range(len(elements)+1). De fato, o elemento destacado elements[0:1]pode estar em len(elements)posições diferentes; no resultado, não len(elements)+1.
Eric O Lebigot
339

E no Python 2.6 em diante:

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

(retornado como um gerador. Use list(permutations(l))para retornar como uma lista.)

Brian
fonte
15
Funciona em Python 3 também
wheleph
10
Observe que existe um rparâmetro, por exemplo itertools.permutations([1,2,3], r=2), que irá gerar todas as permutações possíveis selecionando 2 elementos:[(1, 2), (1, 3), (2, 1), (2, 3), (3, 1), (3, 2)]
toto_tico
278

O código a seguir com o Python 2.6 e acima SOMENTE

Primeiro, importe itertools:

import itertools

Permutação (ordem 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)]

Combinação (a ordem NÃO importa):

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

Produto cartesiano (com várias iteráveis):

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

Produto cartesiano (com um iterável e ele próprio):

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
fonte
`print list (itertools.permutations ([1,2,3,4], 2)) ^` SyntaxError: sintaxe inválida` Apenas começando com o código VS O que fiz de errado? O ponteiro está apontando sob o "t" da "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])

chamado como:

permutations('abc')
kx2k
fonte
Por que imprimir cauda e depois retornar Nenhum? Por que não retornar a cauda? Por que não devolver nada de qualquer maneira?
precisa
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])

Resultado:

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

Como estou trocando o conteúdo da lista, é necessário um tipo de sequência mutável como entrada. Por exemplo perm(list("ball")), funcionará e perm("ball")não funcionará porque você não pode alterar uma string.

Essa implementação em Python é inspirada no algoritmo apresentado no livro Computer Algorithms by Horowitz, Sahni and Rajasekeran .

Silveira Neto
fonte
Presumo que k é o comprimento ou permutações. Para k = 2 saídas [1, 2, 3]. Não deveria ser (1, 2) (1, 3) (2, 1) (2, 3) (3, 1) (3, 2) ??
Konstantinos Monachopoulos
k é o índice do elemento que você deseja trocar
sf8193
22

Esta solução implementa um gerador, para evitar reter todas as permutações na memória:

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
fonte
16

Em um 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)])

O resultado:

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

O código a seguir é uma permutação no local de uma determinada lista, implementada como um gerador. Como ele retorna apenas referências à lista, a lista não deve ser modificada fora do gerador. A solução não é recursiva, portanto, usa pouca memória. Trabalhe bem também com várias cópias de elementos na 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
fonte
15

Uma maneira bastante óbvia na minha opinião pode ser também:

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

Resultado:

[
    [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
fonte
2
Embora tecnicamente produza a saída desejada, você está resolvendo algo que pode ser O (n lg n) em O (n ^ n) - "levemente" ineficiente para conjuntos grandes.
James
3
@ James: Estou um pouco confuso com o O (n log n) que você fornece: o número de permutações é n !, que já é muito maior que O (n log n); então, não consigo ver como uma solução poderia ser O (n log n). No entanto, é verdade que esta solução está em O (n ^ n), que é muito maior que n !, como fica claro na aproximação de Stirling.
Eric O Lebigot
9

Usei um algoritmo baseado no sistema de números fatoriais - Para obter uma lista de comprimento n, você pode montar cada item de permutação por item, selecionando os itens deixados em cada estágio. Você tem n opções para o primeiro item, n-1 para o segundo e apenas uma para o último, para poder usar os dígitos de um número no sistema de números fatoriais como índices. Dessa forma, os números de 0 a n! -1 correspondem a todas as permutações possíveis em ordem lexicográfica.

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

resultado:

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

Este método não é recursivo, mas é um pouco mais lento no meu computador e o xrange gera um erro quando n! é muito grande para ser convertido em um inteiro C longo (n = 13 para mim). Foi o suficiente quando eu precisei, mas não há nenhum problema.

timeeeee
fonte
3
Olá, bem-vindo ao Stack Overflow. Embora a publicação do método de força bruta tenha seus méritos, se você não acha que sua solução é melhor que a solução aceita, provavelmente não deve publicá-la (especialmente em uma pergunta antiga que já tem tantas respostas).
Hannele 8/08/13
1
Na verdade, eu estava procurando uma abordagem de não-biblioteca de força bruta, então obrigada!
Jay Taylor
8

Observe que esse algoritmo tem uma n factorialcomplexidade de tempo, onde né o comprimento da lista de entrada

Imprima os resultados na execução:

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

Exemplo:

permutation([1,2,3])

Resultado:

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

Na verdade, pode-se iterar sobre o primeiro elemento de cada permutação, como na resposta de tzwenn. No entanto, é mais eficiente escrever esta solução desta maneira:

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 solução é cerca de 30% mais rápida, aparentemente graças à recursão que termina em len(elements) <= 1vez de 0. Também é muito mais eficiente em termos de memória, pois utiliza uma função de gerador (através yield), como na solução de Riccardo Reyes.

Eric O Lebigot
fonte
6

Isso é inspirado na implementação de Haskell usando a compreensão da 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
porquinho
fonte
6

Implementação regular (sem rendimento - fará tudo na memória):

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

Implementação de rendimento:

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]

A idéia básica é revisar todos os elementos da matriz para a 1ª posição e, em seguida, na 2ª posição, revisar todos os outros elementos sem o elemento escolhido para a 1ª, etc. Você pode fazer isso com recursão , onde O critério de parada está chegando a uma matriz de 1 elemento - nesse caso, você retorna essa matriz.

insira a descrição da imagem aqui

David Refaeli
fonte
Isso não funciona para mim _> ValueError: os operandos não puderam ser transmitidos junto com as formas (0,) (2,) para esta linha:perms = getPermutations(array[:i] + array[i+1:])
RK1
@ RK1 qual foi a entrada?
David Refaeli
Estou passando em uma numpymatriz _> getPermutations(np.array([1, 2, 3])), vejo que funciona para uma lista, só fiquei confuso como a função arg é array:)
RK1
@ RK1 feliz que funcione :-) list é uma palavra-chave em python, por isso geralmente não é uma boa idéia chamar seu parâmetro de palavra-chave, pois isso a "sombreará". Então, eu uso a palavra matriz, pois essa é a funcionalidade real da lista que estou usando - sua matriz como maneira. Eu acho que se eu escrevesse documentação, eu a esclareceria. Também acredito que questões básicas de "entrevista" devem ser resolvidas sem pacotes externos, como numpy.
David Refaeli
Haha isso é verdade, sim, estava tentando usá-lo numbae ficou ganancioso com velocidade, então tentei usá-lo exclusivamente com numpymatrizes
RK1
4

Para desempenho, uma solução numpy inspirada em 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 blocos de memória economiza tempo - é 20x mais 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
fonte
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
fonte
3

Aqui está um algoritmo que funciona em uma lista sem criar novas listas intermediárias semelhantes à solução de Ber em 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

Você pode experimentar o código aqui: http://repl.it/J9v

cdiggins
fonte
3

A beleza da recursão:

>>> 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
fonte
3

Este algoritmo é o mais eficaz, evita a passagem e manipulação de array em chamadas recursivas, funciona em 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
fonte
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:]))
manish kumar
fonte
3

Outra abordagem (sem 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

A entrada pode ser uma sequência ou uma lista

print(permutation('abcd'))
print(permutation(['a', 'b', 'c', 'd']))
Tatsu
fonte
Isso não funciona para uma lista com números inteiros, por exemplo. [1, 2, 3]retorna[6, 6, 6, 6, 6, 6]
RK1 6/02
@ RK1, você pode tentar issoprint(permutation(['1','2','3']))
Tatsu
Obrigado que funciona
RK1
3

Isenção de responsabilidade: plugue sem forma por autor do pacote :)

O pacote trotter é diferente da maioria das implementações, pois gera pseudo-listas que na verdade não contêm permutações, mas descreve mapeamentos entre permutações e respectivas posições em uma ordem, tornando possível trabalhar com 'listas' muito grandes de permutações, como mostrado em esta demonstração que executa muito instantânea operações e look-ups em uma pseudo-lista 'contendo' todas as permutações das letras no alfabeto, sem o uso de mais memória ou processamento de uma página web típico.

De qualquer forma, para gerar uma lista de permutações, podemos fazer o seguinte.

import trotter

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

print(my_permutations)

for p in my_permutations:
    print(p)

Resultado:

Uma pseudo-lista contendo 6 3 permutações de [1, 2, 3].
[1, 2, 3]
[1, 3, 2]
[3, 1, 2]
[3, 2, 1]
[2, 3, 1]
[2, 1, 3]
Richard Ambler
fonte
2

Gere todas as permutações possíveis

Estou 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 teste:

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

Para poupar a você horas possíveis de pesquisa e experimentação, aqui está a solução de permutações não recursivas no Python, que também funciona com o Numba (a partir da versão 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 uma impressão sobre desempenho:

%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

Portanto, use esta versão apenas se você precisar chamá-la da função njitted, caso contrário, prefira a implementação de ferramentas.

Anatoly Alekseev
fonte
1

Eu vejo muita iteração acontecendo dentro dessas funções recursivas, não exatamente recursão pura ...

Portanto, para aqueles que não conseguem cumprir nem um único ciclo, aqui está uma solução totalmente recursiva bruta e totalmente desnecessária

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
fonte
1

Outra solução:

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
fonte
0

Minha solução 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
fonte
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')

Saída: ['abc', 'acb', 'bac', 'bca', 'cab', 'cba']

Ilgorbek Kuchkarov
fonte
0

Usando 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]]
Olá Mundo
fonte