MattWeber.Org

Here is a homework question from my Problem Solving Strategies class, along with my answer written as a python generator.

Design and code a decrease and conquer algorithm for generating all permutations of N elements in an array. Use the decrease-by-one method given in class where the parameters are: a prefix string, the number of elements whose permutations are to be concatenated with the prefix string, and the set of those elements. Turn in the code and the results for running it with a 4 element set containing A, B, C, and D.

def AllPermutations(elements, numElem=None, prefix=[]):
     if not numElem: numElem = len(elements)
     if numElem == 0:
         yield prefix
     else:
         for index in xrange(numElem):
             newPrefix = prefix[:]
             newPrefix.append(elements[index])
             newElements = elements[:index] + elements[index+1:]
             for perms in AllPermutations(newElements, numElem - 1, newPrefix):
                 yield perms

 if __name__ == ‘__main__‘:
     for perm in AllPermutations(list(’ABCD‘)):
         print perm

Files:
http://www.mattweber.org/files/perms.py