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.

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.