Permutations without repetition without using itertools

Question

I need to get all the permutations of an iterable of length n in a brute force algorithm. I dont want to use itertools or any other external packages.

I figured I could use Heap's algorithm but my code only returns one permutation repeated for n! times:

def permutations(l):
    n = len(l)
    result = []
    c = n * [0]
    result.append(l)
    i = 0;
    while i < n:
        if c[i] < i:
            if i % 2 == 0:
                tmp = l[0]
                l[0] = l[i]
                l[i] = tmp
            else:
                tmp = l[c[i]]
                l[c[i]] = l[i]
                l[i] = tmp
            result.append(l)
            c[i] += 1
            i = 0
        else:
            c[i] = 0
            i += 1
    return result

I can't figure out why this happens. I'm also trying to figure out if there is a more efficient way to do this, maybe with a recursive function.

Answer 1

You can use the following, this is without the use of other internal function but it uses a recursion:

def permutation(lst):
    if len(lst) == 0:
        return []
    if len(lst) == 1:
        return [lst]

    l = [] # empty list that will store current permutation

    for i in range(len(lst)):
       m = lst[i]

       # Extract lst[i] or m from the list. remainderLst is remaining list
       remainderLst = lst[:i] + lst[i+1:]

       # Generating all permutations where m is first element
       for p in permutation(remainderLst):
           l.append([m] + p)
    return l


data = list('12345')
for p in permutation(data):
    print(p)