Lab #3: Combinatorics

Description

This activity must be developed in the pre-assigned teams of two.

NOTE: You may NOT use the functions defined in the itertools module to solve these problems.

Add to the file combinatorics.py developed in class the code required to solve the following two problems.

1. A \(k\)-permutation with repetition of \(n\) objects is a way of selecting \(k\) objects from a list of size \(n\). The selection rules are:

   1. The order of selection matters (the same \(k\) objects selected in different orders are regarded as different \(k\)-permutations).

   2. Each object can be selected more than once.

   Thus, the difference between \(k\)-permutations without repetition and \(k\)-permutations with repetition is that objects can be selected more than once in the latter, while they can be selected only once in the former.

   The number of permutations with repetition can be computed with this formula:

   $$ _{n}\,P’\,_{k} = n^k $$

   Source: StatLect.com

   Write a function with the following signature:

   def permutations_with_repetition(
        s: list[C],
        k: int) -> list[list[C]]:

   The function returns a list with all possible \(k\)-permutations with repetitions taken from the elements contained in list \(s\). Examples:

   >>> from combinatorics import permutations_with_repetition
   >>> sorted(permutations_with_repetition([0, 1], 4))
   [[0, 0, 0, 0],
    [0, 0, 0, 1],
    [0, 0, 1, 0],
    [0, 0, 1, 1],
    [0, 1, 0, 0],
    [0, 1, 0, 1],
    [0, 1, 1, 0],
    [0, 1, 1, 1],
    [1, 0, 0, 0],
    [1, 0, 0, 1],
    [1, 0, 1, 0],
    [1, 0, 1, 1],
    [1, 1, 0, 0],
    [1, 1, 0, 1],
    [1, 1, 1, 0],
    [1, 1, 1, 1]]
   >>> sorted(
           permutations_with_repetition(['a', 'b', 'c'], 2))
   [['a', 'a'],
    ['a', 'b'],
    ['a', 'c'],
    ['b', 'a'],
    ['b', 'b'],
    ['b', 'c'],
    ['c', 'a'],
    ['c', 'b'],
    ['c', 'c']]
   

2. A combination with repetition of \(k\) objects from \(n\) is a way of selecting \(k\) objects from a list of size \(n\). The selection rules are:

   1. The order of selection does not matter (the same objects selected in different orders are regarded as the same combination).

   2. Each object can be selected more than once.

   Thus, the difference between simple combinations and combinations with repetition is that objects can be selected only once in the former, while they can be selected more than once in the latter.

   The number of combinations with repetitions can be computed with this formula:

   $$ _{n}\,C’\,_{k} = \frac{(n + k - 1)!}{k! (n - 1)!} $$

   Source: StatLect.com

   Write a function with the following signature:

   def combinations_with_repetition(
        s: list[C],
        k: int) -> list[list[C]]:

   The function returns a list with all possible combinations of size \(k\) with repetitions taken from the elements contained in list \(s\). The nested lists inside the resulting list should be sorted in ascending order. Examples:

   >>> from combinatorics import combinations_with_repetition
   >>> sorted(combinations_with_repetition([0, 1], 4))
   [[0, 0, 0, 0],
    [0, 0, 0, 1],
    [0, 0, 1, 1],
    [0, 1, 1, 1],
    [1, 1, 1, 1]]
   >>> sorted(
           combinations_with_repetition(['a', 'b', 'c'], 2))
   [['a', 'a'],
    ['a', 'b'],
    ['a', 'c'],
    ['b', 'b'],
    ['b', 'c'],
    ['c', 'c']]
   

Test your code using the tests in the file test_combinatorics.py. Finally, make sure no type or PEP 8 style errors are produced by using the mypy and pycodestyle linters. You can run them at the terminal like this:

mypy combinatorics.py

pycodestyle combinatorics.py

Deliverables

Place in a comment at the top of the combinatorics.py source file the authors’ personal information (student ID and name), for example:

#----------------------------------------------------------
# Lab #3: Combinatorics
# Permutations and combinations with repetitions.
#
# Date: 29-Sep-2022
# Authors:
#           A01770771 Kamala Khan
#           A01777771 Carol Danvers
#----------------------------------------------------------

Only one team member needs to upload the file.

Due date is Friday, September 29.