Permutations of a list using stack

Question

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

Seems like a homework problem? Otherwise I can't see why you would not use the itertools. — cadolphs, Sep 30 '16 at 23:39
My initial thought was to just create a set of generators (each with an offset indicating when they spit out the next value), but I am not certain that's in the spirit of the question. There are some interesting ideas over here: http://stackoverflow.com/questions/2710713/algorithm-to-generate-all-possible-permutations-of-a-list — ǝɲǝɲbρɯͽ, Oct 01 '16 at 00:34

score 4 · Accepted Answer · answered Sep 30 '16 at 23:56

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

Thanks for sharing this. This is what I was trying for but couldn't quite get there. — W.B, Oct 01 '16 at 13:31

גלעד ברקן · Answer 2 · 2016-10-01T12:42:58.413

1

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

edited Oct 01 '16 at 12:42

answered Oct 01 '16 at 04:41

גלעד ברקן

23,602
3
25
61

Permutations of a list using stack

2 Answers2