Lab #3: Combinatorics

Description

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

NOTE 1: The files developed so far in class for this lab are available in the course’s GitHub repository.

NOTE 2: 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,
        k: int) -> list[list]:

   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,
        k: int) -> list[list]:

   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 (18 tests in total). Make sure your code has no failures and no errors.

Also, verify that your editor has basic type checking enabled. All your code should use type hints adequately.

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: 01-Oct-2024
# Authors:
#           A01770771 James Howlett
#           A01777771 Wade Wilson
#----------------------------------------------------------

Only one team member needs to upload the file.

Due date is Tuesday, October 1.