# File: PermutationGenerator.py
# Author: Keith Schwarz (htiek@cs.stanford.edu)
#
# An application of Python coroutines to the iterative generation of
# permutations.  This code exports the permutations() function, which, given a
# list of elements, iteratively produces all permutations of that list.  The
# goal is to be able to write code to this effect:
#
#   for p in permutations([1, 2, 3]):
#       print p
#
# In order to generate all permutations, this code uses the following recursive
# procedure for exhaustively generating permutations:
#
#   - There is only one permutation of the empty list, which is [].
#   - Given a nonempty list of elements, we can form all permutations of that
#     list by, for each element in the list, prepending that element to all
#     permutations of the remaining elements.
#
# This recursive procedure will list all permutations, which is great in many
# contexts.  However, if we want to be able to generate those permutations
# iteratively, stopping whenever we choose, then this approach is not tenable.
# Given n elements, there are n! different permutations of those elements, and
# it's extraordinarily wasteful to generate all n! permutations if we only need
# a small number of them, say, only O(n).
#
# This program defines a coroutine permutations() that uses Python's yield
# facility to generate permutations one at a time.  That way, we can use the
# recursive strategy to generate permutations, but only run the recursion as
# much as is needed.

# Function: permutations(elems)
# Usage: for p in permutations([1, 2, 3]): ...
# -----------------------------------------------------------------------------
# A generator function that generates all permutations of the input elements.
# If the input contains duplicates, then some permutations may be visited with
# multiplicity greater than one.
def permutations(elems):
    # Our recursive algorithm requires two pieces of information, the elements
    # that have not yet been permuted and the partial permutation built up so
    # far.  We thus phrase this function as a wrapper around a recursive
    # function with extra parameters.
    for perm in recPermutations(elems, []):
        yield perm

# A helper function to recursively generate permutations.  The function takes
# in two arguments, the elements to permute and the partial permutation created
# so far, and then produces all permutations that start with the given sequence
# and end with some permutations of the unpermuted elements.
def recPermutations(elems, soFar):
    # Base case: If there are no more elements to permute, then the answer will
    # be the permutation we have created so far.
    if len(elems) == 0:
        yield soFar

    # Otherwise, try extending the permutation we have so far by each of the
    # elements we have yet to permute.
    else:
        for i in range(0, len(elems)):
            # Extend the current permutation by the ith element, then remove
            # the ith element from the set of elements we have not yet
            # permuted.  We then iterate across all the permutations that have
            # been generated this way and hand each one back to the caller.
            for perm in recPermutations(elems[0:i] + elems[i+1:], 
                                        soFar + [elems[i]]):
                yield perm