mirror of
https://github.com/TheAlgorithms/Python.git
synced 2026-09-28 13:33:11 +08:00
Achal Jainpre-commit-ci[bot] <66853113+pre-commit-ci[bot]@users.noreply.github.com>Christian Clausscclauss* Added Derangement calculator * Updated derangement.py * [pre-commit.ci] auto fixes from pre-commit.com hooks for more information, see https://pre-commit.ci * Updated derangement.py * updating DIRECTORY.md * Apply suggestion from @cclauss --------- Co-authored-by: pre-commit-ci[bot] <66853113+pre-commit-ci[bot]@users.noreply.github.com> Co-authored-by: Christian Clauss <cclauss@me.com> Co-authored-by: cclauss <cclauss@users.noreply.github.com>
43 lines
1023 B
Python
43 lines
1023 B
Python
"""
|
|
A Python implementation for finding number of
|
|
derangements possible for k objects
|
|
https://en.wikipedia.org/wiki/Derangement
|
|
"""
|
|
|
|
|
|
def derangement(objects: int) -> int:
|
|
"""
|
|
Calculates the number of derangements of k objects.
|
|
:param objects:the number of objects ( -1 < objects < 1560 )
|
|
:return :the number of derangements
|
|
:raises :ValueError: If objects is negative.
|
|
|
|
Examples:
|
|
>>> derangement(3)
|
|
2
|
|
>>> derangement(5)
|
|
44
|
|
>>> derangement(10)
|
|
1334961
|
|
"""
|
|
if objects < 0:
|
|
raise ValueError("k must be a non-negative integer. Retry")
|
|
|
|
# Base cases
|
|
if objects in (0, 1):
|
|
return 0
|
|
|
|
# Initialize the derangement counts
|
|
derange_1 = 1
|
|
derange_2 = 0
|
|
answer = 1
|
|
|
|
# Calculate derangements using dynamic programming
|
|
# Answer: F(n) = (n - 1) * ( F(n - 1) + F(n - 2) )
|
|
for i in range(3, objects + 1):
|
|
answer = (i - 1) * (derange_1 + derange_2)
|
|
derange_2 = derange_1
|
|
derange_1 = answer
|
|
|
|
return answer
|