Question

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

Answer 1

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