CODEWITHSUNDEEP
pythonalgorithm
W.B
W.B

Reputation: 25

Permutations of a list using stack

I'm trying to find a way to enumerate all combinations of a list of numbers without recursion or using itertools. I came up with a solution that works but I think it turned into a recursive function after all. I'm new to Python and not sure how I would make this work without recursion.

Any help is appreciated as I think I'm still failing to see the difference between the two.

result = []

def permutation(li):
    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()    

permutation([1,2,3])

Upvotes: 2

Views: 1917

Answers (2)

גלעד ברקן
גלעד ברקן

Reputation: 23945

I always liked this method:

Until the length of each variation in the queue equals the input's length: place the next input element in all positions of each variation

input [1,2,3]

queue [[1]]
insert 2 in all positions of each variation
queue [[2,1],[1,2]]
insert 3 in all positions of each variation
queue [[3,2,1],[2,3,1],[2,1,3],[3,1,2],[1,3,2],[1,2,3]]

Upvotes: 1

trincot
trincot

Reputation: 350770

It is not that intuitive to come up with an algorithm "just like that" that produces all permutations without the use of recursion.

But there exist several different such algorithms. Have look at Heap's algorithm for example:

def permutation(li):
    n = len(li)
    c = [0] * n

    print(li)
    i = 1
    while i < n:
        if c[i] < i:
            j = c[i] if i % 2 else 0
            li[j], li[i] = li[i], li[j]
            print(li)
            c[i] += 1
            i = 1
        else:
            c[i] = 0
            i += 1

Upvotes: 4

Related Questions