Python permutations recursive

A recursive generator function that yields permutations in the expected order with regard to the original list:

def perm(a):
    if len(a) <= 1:
        yield a
    else:
        for i in xrange(len(a)):
            for p in perm(a[:i]+a[i+1:]):
                yield [a[i]]+p

a = [1, 2, 3]

for p in perm(a):
    print(p)

[1, 2, 3]
[1, 3, 2]
[2, 1, 3]
[2, 3, 1]
[3, 1, 2]
[3, 2, 1]

Here's one (suboptimal, because copying lists all the time) solution:

def perm(a, prev=[]):
    if not a:
        print(prev)
    for index, element in enumerate(a):
        perm(a[:index] + a[index+1:], prev + [element])

‌The order it is printed out:

>>> perm([1,2,3])
[1, 2, 3]
[1, 3, 2]
[2, 1, 3]
[2, 3, 1]
[3, 1, 2]
[3, 2, 1]

Let's say you have five elements ABCDE and you're in the top call, i.e., selecting the first element and recursing for permuting the remaining four. Your loop and swaps produce these:

ABCDE  (selected A as first, permute BCDE recursively)
BACDE
CBADE  (selected C as first, permute BADE recursively)
DBCAE
EBCDA

While the first position correctly goes through A to E, the remaining four aren't always in the original order. For example BADE instead of ABDE. What you want instead is these:

ABCDE
BACDE
CABDE
DABCE
EABCD

You can see that you get from one to the next with a single swap. Namely your a[k],a[i] = a[i],a[k] before the recursion. So remove your swap after the recursion. Instead restore the original order after the loop, by moving the E all the way back to the end:

def perm(a,k=0):
   if(k==len(a)):
      print(a)
   else:
      for i in range(k,len(a)):
         a[k],a[i] = a[i],a[k]
         perm(a, k+1)
      a.append(a.pop(k))

perm([*'123'])

Attempt This Online!

Interesting problem. Your approach is very efficient, with complexity O(n!*n), because it only swaps elements (no list copy, pop, insert, etc of O(n) complexity used) but the lexicographical order is lost. One easy way to keep the order is to sort the indices, but this is not efficient, with complexity O(n!*nlogn):

def perm(a,k=0):
   if k == len(a):
      print(a)
   else:
      sorted_indices = sorted(range(k, len(a)), key=lambda x: a[x])
      for i in sorted_indices:
         a[k],a[i] = a[i],a[k]
         perm(a, k+1)
         a[k],a[i] = a[i],a[k]

perm([1,2,3])

The best way I can think of is this, with complexity O(n!*n):

class Indices_List:
    """ List of indices 0,1,...,n that can be swapped.
    'sorted' keeps for each value at what index it is stored in 'indices'. 
    """

    def __init__(self, n):
        self.indices = [i for i in range(n)]
        self.sorted = self.indices.copy()

    def __repr__(self):
        return str(self.indices) + '\n' + str(self.sorted)

    def __len__(self):
        return len(self.indices)

    def get_indices(self):
        return self.indices
    
    def get_sorted(self):
        return self.sorted

    def swap(self, i, j):
        self.sorted[self.indices[i]] = j
        self.sorted[self.indices[j]] = i
        self.indices[i], self.indices[j] = self.indices[j], self.indices[i]

def perm(il, k=0):
   if k == len(il):
      yield il.get_indices()
   else:
      for i in il.get_sorted():
         if i >= k:
            il.swap(k, i)
            yield from perm(il, k+1)
            il.swap(k, i)

def get_permutation(values, indices):
    return [values[i] for i in indices]
            
values = ['a','b','c','d'] 
for p in perm(Indices_List(len(values))):
   print(get_permutation(values, p))

with this output in lexicographical order:

['a', 'b', 'c', 'd']
['a', 'b', 'd', 'c']
['a', 'c', 'b', 'd']
['a', 'c', 'd', 'b']
['a', 'd', 'b', 'c']
...
['d', 'a', 'c', 'b']
['d', 'b', 'a', 'c']
['d', 'b', 'c', 'a']
['d', 'c', 'a', 'b']
['d', 'c', 'b', 'a']

I read that the Steinhaus–Johnson–Trotter algorithm does it faster, but doesn't give lexicographical order.