Given a list of unique elements, a permutation of the list is a reordering of th

Question

Given a list of unique elements, a permutation of the list is a reordering of the elements. For example, [2, 1, 3], [1, 3, 2], and [3, 2, 1] are all permutations of the list [1, 2, 3].

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.

Hint: If you had the permutations of lst minus one element, how could you use that to generate the permutations of the full lst?

Note that in the provided code, the return statement acts like a raise StopIteration. The point of this is so that the returned generator doesn't enter the rest of the body on any calls to next after the first if the input list is empty. Note that this return statement does not affect the fact that the function will still return a generator object because the body contains yield statements.

"*** YOUR CODE HERE ***"

Explanation / Answer

def permutations(lst): if not lst: yield [] return 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

Related Questions

Navigate

• Browse (All)
• Browse G
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.