Primeira vez aqui? Seja bem vindo e cheque o FAQ!
x

Como gerar todas as permutações de um conjunto usando uma pilha?

0 votos
76 visitas
perguntada Abr 15, 2016 em Ciência da Computação por danielcajueiro (5,226 pontos)  
Compartilhe

1 Resposta

0 votos
respondida Abr 15, 2016 por danielcajueiro (5,226 pontos)  

De uma forma geral, uma pilha é um tipo abstrato de dados que permite implementar recursões. Logo, para gerar as permutações de um conjunto precisamos apenas adaptar um algoritmo recursivo.

Considere que desejamos gerar todas as permutações do conjunto 1,2,3.

Considere o seguinte algoritmo, que obviamente pode ser implementado recursivamente:

[Root 0] 1

[Root 00] 12
[Root 01] 21

[Root 000] 123
[Root 001] 132
[Root 002] 312

[Root 010] 213
[Root 011] 231
[Root 012] 321

Abaixo adapto esse algoritmo para uma pilha:

if __name__ == '__main__':

    myList=[1,2,3] #It will generate all permutations of the set {1,2,...,n}
    n=len(myList)
    stack = [[myList[0]]]
    while len(stack)!=0:
        u=stack.pop()
        sizeu=len(u)
        if(sizeu==n):
            print  u
        else:
            u.append(myList[sizeu])
            stack.append(u[:]) # Discover the reason I am using u[:] instead of u
            for j in range(sizeu,0,-1):
                aux=u[j]
                u[j]=u[j-1]
                u[j-1]=aux
                stack.append(u[:])
...