Permutations in Python

Question

Question 2 of Homework 11 from Berkeley's CS6 1A says:

Implement permutations, a generator function that takes in a lst and outputs all permutations of lst, each as a list (see doctest for an example). The order in which you generate permutations is irrelevant.

This is my solution:

def permutations(lst):
 if not lst:
 yield []
 return
 "*** YOUR CODE HERE ***"
 if type(lst)==tuple:
 t=lst
 lst=[]
 for elem in t:
 lst+=[elem]
 if type(lst)==str:
 lst=list(lst)
 for elem in lst:
 if elem:
 l_temp=[lst[0]]
 lst=lst[1:]
 lst.extend(l_temp)
 temp=list(lst[1:])
 r_list=[]
 lst_of_lst=[]
 r_list+=[lst[0]]
 while len(lst_of_lst)!=len(lst)-1:
 holder=temp[1:]
 t_holder=[temp[0]]
 temp=[]
 temp.extend(holder)
 temp.extend(t_holder)
 if len(r_list)==1:
 r_list.extend([e for e in temp])
 lst_of_lst+=[r_list,]
 r_list=[]
 r_list+=[lst[0]]
 yield lst_of_lst

Test cases:

>>> sorted(permutations([1, 2, 3]))
[[1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2], [3, 2, 1]]
>>> type(permutations([1, 2, 3]))
<class 'generator'>
>>> sorted(permutations((10, 20, 30)))
[[10, 20, 30], [10, 30, 20], [20, 10, 30], [20, 30, 10], [30, 10, 20], [30, 20, 10]]
>>> sorted(permutations("ab"))
[['a', 'b'], ['b', 'a']]

I need some suggestions in order to improve my code.

• Gareth Rees: Can you explain why you didn't use itertools.permutations? Is this an exercise for a programming class?
• user7724050: itertools.permutations is a built in function. We were supposed to develop the logic using "yield" and "iter" and yes, it is an exercise for a programming class (you may click the reference link for more details).Thanks for referring to itertools.permutations as they gave a rough equivalent code for explanation. Thanks!

Answer 1

 if type(lst)==tuple:
 t=lst
 lst=[]
 for elem in t:
 lst+=[elem]
 if type(lst)==str:
 lst=list(lst)

It's worth knowing that list works on tuples too. (Online demo).

---

 for elem in lst:
 if elem:

What purpose does this if serve? It seems to me to introduce a bug, because the spec does not ask for falsy elements of lst to be ignored.

---

 l_temp=[lst[0]]
 lst=lst[1:]

[lst[0]] would be more Pythonic as lst[:1]. Spot the symmetry with the second line.

The reuse of names is not particularly helpful, especially given that lst is a bad name. How about this?

 first, rest = lst[:1], lst[1:]

---

 lst.extend(l_temp)

Wait, that was just to rotate the list? Why? At this point I'm seriously in need of some comments to explain what you're trying to do.

---

 temp=list(lst[1:])
 r_list=[]
 lst_of_lst=[]
 r_list+=[lst[0]]

lst_of_lst? That sounds like a bad name for a 2D array, but the spec doesn't ask for a 2D array and I can't see why you'd need one.

r_list is again just lst[:1].

---

 holder=temp[1:]
 t_holder=[temp[0]]
 temp=[]
 temp.extend(holder)
 temp.extend(t_holder)

Or in other words temp = temp[1:] + temp[:1]. You're rotating lists often enough that maybe it's worth factoring out a function to make the flow of logic clearer.

---

 if len(r_list)==1:
 r_list.extend([e for e in temp])
 lst_of_lst+=[r_list,]
 r_list=[]
 r_list+=[lst[0]]
 yield lst_of_lst

---

There is no way this algorithm can be correct. Have you tested your code?

print len(list(permutations([1, 2, 3])))
print len(list(permutations([0, 1, 2, 3])))

should output

6
24

---

Once your code works, given that it's Python you should run it through an automated PEP8 checker. It should be easy to find one online.

• user7724050: Thanks for all the suggestions, I would improve upon all of my mistakes.
• user7724050: what I was trying to accomplish is as follows: for permutations of the list [1,2,3] for instance. In order to generate all possible combinations, I tried to fix one of the elements of the list let's say 1, so all of the possible combinations can be obtained by rotating the rest of the elements of the list so [1,2,3] would be first, [1,3,2]. And repeating the same procedure for the rest of the elements of the list.