Lab 8 : Permutations and Combinations

0 Preliminaries

To run doctests, add the following to the bottom of your file:

if (__name__ == '__main__'):
  import doctest
  doctest.testmod(optionflags= doctest.NORMALIZE_WHITESPACE)

1 Counting permutations and combinations

Exercise 1 Write a function which computes factorial. Use a for or while loop.

def fact(n):
   """
   >>> fact(0)
   1
   >>> fact(1)
   1
   >>> fact(5)
   120

   """

Exercise 2 Write a function which computes factorial. This time do not use a loop. Rather, define fact_rec so that it calls itself on a “smaller” input.

def fact_rec(n):
    """
    >>> fact_rec(0)
    1
    >>> fact_rec(1)
    1
    >>> fact_rec(5)
    120

    """

Exercise 3 Write a function which counts how many permutations of length r there are in a collection of n elements. Use fact or fact_rec.

def perm(n, r):
    """
    >>> perm(4, 0)
    1
    >>> perm(4, 1)
    4
    >>> perm(4, 2)
    12
    >>> perm(4, 3)
    24

    """

Exercise 4 Write a function which counts how many combinations of length r there are in a collection of n elements. Use perm and either fact or fact_rec.

def comb(n, r):
    """
    >>> comb(3,0)
    1
    >>> comb(3,1)
    3
    >>> comb(3,2)
    3
    >>> comb(3,3)
    1

    """

2 Listing combinations

Exercise 5 Write a function which takes an element x and a list of lists lol and inserts x at the beginning of every list in lol.

def insert_first(x, lol):
    """
    >>> insert_first(1, [[2, 3], [2, 4], [3, 4]])
    [[1, 2, 3], [1, 2, 4], [1, 3, 4]]

    """

Exercise 6 Write a function which takes a list of elements l and lists out all the combinations of elements of l of size r.

Here is one way to approach this problem. We will define list_comb so that it calls itself (twice). First we want to explicitly handle the following cases: when r is 0, when l is empty and when r is 1. Then for larger l and r we will call list_comb on “smaller” inputs. Consider this example:

>>> list_comb([1, 2, 3, 4], 2)
[[1, 2], [1, 3], [1, 4], [2, 3], [2, 4], [3, 4]]

We can think of the desired output as two lists appended together:

[[1, 2], [1, 3], [1, 4]]

and

[[2, 3], [2, 4], [3, 4]]

Think about how you might produce each of these two lists using list_comb (assuming that it does what it is supposed to do).

1. Producing the first list requires a helper function: we start by calling list_comb on [2, 3, 4] and 1, which gives [[2], [3], [4]]; and then we apply insert_first to 1 and the result, [[2], [3], [4]].
2. Producing the second list is straightforward: we call list_comb on [2, 3, 4] and 2.
3. The final step is to append the results from steps 1 and 2 together.

def list_comb(l, r):
    """
    >>> list_comb([], 0)
    [[]]
    >>> list_comb([], 1)
    []
    >>> list_comb([1, 2, 3, 4], 0)
    [[]]
    >>> list_comb([1, 2, 3, 4], 1)
    [[1], [2], [3], [4]]
    >>> list_comb([1, 2, 3, 4], 2)
    [[1, 2], [1, 3], [1, 4], [2, 3], [2, 4], [3, 4]]
    >>> list_comb([1, 2, 3, 4], 3)
    [[1, 2, 3], [1, 2, 4], [1, 3, 4], [2, 3, 4]]
    >>> list_comb([1, 2, 3, 4], 4)
    [[1, 2, 3, 4]]

    """

3 Listing permutations

Exercise 7 Write a function which takes a list of lists and appends all of them together.

def append_lists(lol):
   """
   >>> append_lists([[1, 2, 3], [4, 5], [6]])
   [1, 2, 3, 4, 5, 6]
   >>> append_lists([])
   []
   >>> append_lists([[]])
   []

   """

Exercise 8 Write a function which takes an element x and a list l and returns a list of lists containing all of the possible ways of inserting x into l.

def insert_all(x, l):
    """
    >>> insert_all(1, [2, 3, 4])
    [[1, 2, 3, 4], [2, 1, 3, 4], [2, 3, 1, 4], [2, 3, 4, 1]]
    >>> insert_all(1, [])
    [[1]]

    """

Exercise 9 Write a function which takes an element x and a list of lists lol and returns a list of lists containing all of the possible ways of inserting x into a list in lol. Use append_lists and insert_all. (Hint: first apply insert_all to every element in lol; and then apply append_lists to the result.)

def insert_all_lists(x, lol):
    """
    >>> insert_all_lists(1, [[2, 3], [2, 4]])
    [[1, 2, 3], [2, 1, 3], [2, 3, 1], [1, 2, 4], [2, 1, 4], [2, 4, 1]]

    """

Exercise 10 Write a function which takes a list of elements l and lists out all the permutations of elements of l of size r. Use insert_all_lists. (Hint: the solution for list_comb can be adapted almost verbatim.)

def list_perm(l, r):
    """
    >>> list_perm([], 0)
    [[]]
    >>> list_perm([], 1)
    []
    >>> list_perm([7, 8, 9], 0)
    [[]]
    >>> list_perm([7, 8, 9], 1)
    [[7], [8], [9]]
    >>> list_perm([7, 8, 9], 2)
    [[7, 8], [8, 7], [7, 9], [9, 7], [8, 9], [9, 8]]
    >>> list_perm([7, 8, 9], 3)
    [[7, 8, 9], [8, 7, 9], [8, 9, 7], [7, 9, 8], [9, 7, 8], [9, 8, 7]]

    """