Python-algorithms/maths/derangement.py at master · bz-e/Python-algorithms · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
"""
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