During this activity, students will be able to:
For this programming assignment, students are required to complete all work independently and are not permitted to use AI-assisted tools, such as GitHub Copilot, ChatGPT, Gemini, or similar platforms, to automatically generate code. Using AI tools in this way undermines the learning process and violates academic integrity policies. The purpose of this assignment is to assess your understanding and application of the concepts covered in the course. Failure to comply with these guidelines may result in academic penalties, including but not limited to a lower grade.
If you have any questions about the assignment or need clarification on any concepts, please do not hesitate to visit your instructor during office hours. Rely solely on your own knowledge, the course materials, and any authorized resources provided by the instructor.
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.
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:
The order of selection matters (the same \(k\) objects selected in different orders are regarded as different \(k\)-permutations).
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']]
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:
The order of selection does not matter (the same objects selected in different orders are regarded as the same combination).
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.
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 #----------------------------------------------------------
To deliver the combinatorics.py
file, please provide the following information:
Only one team member needs to upload the file.
Due date is Tuesday, October 1.