Thanks, I will look at the source of itertools.permutations to learn how it is done. I want to learn more about how to write algorithms well. Looking at the source and asking questions as they come up is a great idea.
On Sat, Jul 10, 2010 at 3:37 PM, Shashwat Anand <[email protected]> wrote: > > > On Sat, Jul 10, 2010 at 10:18 PM, Isaac <[email protected]> wrote: >> >> This is my interpretation of an algorithm to generate all permutations >> of items in a list. I would appreciate any feedback regarding advice >> for improvements. > > Why not try itertools.permutation > >> >> Thank you, >> >> -Isaac >> >> #!/usr/bin/python >> >> def add_at_index(new_item, target_array, target_index): >> """ >> new_item is a single list item. >> target_array is a list or iterable. >> target_index is a number. >> >> This function returns a new list that inserts new_item inside >> target_array >> at target_array's target_index. The new list will be 1 element longer >> than before. >> """ >> >> new_list = target_array[:] >> >> new_list.insert(target_index, new_item) >> return new_list >> >> >> def append_lists(working_list, list_of_lists): >> # appends every list in list_of_lists to working_list; returns >> working_list >> for _list in list_of_lists: >> working_list.append(_list) >> return working_list >> >> >> def insert_each(orphan_item, target_array): >> """ >> orphan_item is a single list item. >> target_array is a list or iterable. >> >> This function returns a list of lists that place orphan_item in >> between and at >> the ends of each list element in target_array >> """ >> >> new_array_length = len(target_array) + 1 >> array_of_arrays = [] >> >> for count in range(new_array_length): >> array_of_arrays.append(add_at_index(orphan_item, target_array, >> count)) >> >> return array_of_arrays >> >> >> >> def permute(original_list, list_of_lists): >> """ >> accept a list of items, original_list, to insert one at a time >> into list_of_lists >> using the function insert_each. Called for the first time, >> new_list is a list containing an empty list. Then call recursively >> using >> an updated list_of_lists, called new_list_of_lists below, and the >> remaining >> items in original list. >> """ >> try: >> last_item = original_list.pop() >> except IndexError: >> # if the final iteration has been completed >> return list_of_lists >> >> if list_of_lists == [[]]: # it is the first iteration >> # call the next iteration recursively >> return permute(original_list, [[last_item]]) >> else: >> # placeholder for new permutations >> new_list_of_lists = [] >> for array in list_of_lists: >> permutation_set = insert_each(last_item, array) >> append_lists(new_list_of_lists, permutation_set) >> # call recursively >> return permute(original_list, new_list_of_lists) > _______________________________________________ Tutor maillist - [email protected] To unsubscribe or change subscription options: http://mail.python.org/mailman/listinfo/tutor
