forked from TheAlgorithms/Python
-
Notifications
You must be signed in to change notification settings - Fork 0
/
Copy pathcombinations.py
172 lines (151 loc) · 5.8 KB
/
combinations.py
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
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
from math import comb
from math import factorial
def validate_elements_count(total_elements_count: int, selected_elements_count: int) -> None:
""" Validate that the number of elements are positive and the total is greater than or equal to selected. """
if total_elements_count < selected_elements_count or selected_elements_count < 0:
raise ValueError(
"Please enter positive integers for total_elements_count and selected_elements_count "
"where total_elements_count >= selected_elements_count"
)
def combinations_iterative(total_elements_count: int, selected_elements_count: int) -> int:
"""
Returns the number of combinations that can be made from a total set of elements.
Examples:
>>> combinations_iterative(10, 5)
252
>>> combinations_iterative(6, 3)
20
>>> combinations_iterative(20, 5)
15504
>>> combinations_iterative(52, 5)
2598960
>>> combinations_iterative(0, 0)
1
>>> combinations_iterative(-4, -5)
Traceback (most recent call last):
...
ValueError: Please enter positive integers for total_elements_count and selected_elements_count where total_elements_count >= selected_elements_count
"""
validate_elements_count(total_elements_count, selected_elements_count)
combinations_count = 1
for i in range(selected_elements_count):
combinations_count *= (total_elements_count - i)
combinations_count //= (i + 1)
return combinations_count
def multiset_combinations(total_elements_count: int, selected_elements_count: int) -> int:
"""
Returns the number of combinations from a multiset of elements.
Examples:
>>> multiset_combinations(10, 5)
2002
>>> multiset_combinations(6, 3)
56
>>> multiset_combinations(20, 5)
42504
>>> multiset_combinations(52, 5)
3819816
>>> multiset_combinations(0, 0)
1
>>> multiset_combinations(-4, -5)
Traceback (most recent call last):
...
ValueError: n must be a non-negative integer
"""
validate_elements_count(total_elements_count, selected_elements_count)
return comb(total_elements_count + selected_elements_count - 1, selected_elements_count)
def combinations_formula(total_elements_count: int, selected_elements_count: int) -> int:
"""
Calculate combinations using the formula for n choose k.
Examples:
>>> combinations_formula(10, 5)
252
>>> combinations_formula(6, 3)
20
>>> combinations_formula(20, 5)
15504
>>> combinations_formula(52, 5)
2598960
>>> combinations_formula(0, 0)
1
>>> combinations_formula(-4, -5)
Traceback (most recent call last):
...
ValueError: Please enter positive integers for total_elements_count and selected_elements_count where total_elements_count >= selected_elements_count
"""
validate_elements_count(total_elements_count, selected_elements_count)
remaining_elements_count = total_elements_count - selected_elements_count
return int(
factorial(total_elements_count) /
(factorial(selected_elements_count) * factorial(remaining_elements_count))
)
def combinations_with_repetitions(total_elements_count: int, selected_elements_count: int) -> int:
"""
Calculate combinations with repetitions allowed.
Examples:
>>> combinations_with_repetitions(10, 5)
2002
>>> combinations_with_repetitions(6, 3)
56
>>> combinations_with_repetitions(20, 5)
42504
>>> combinations_with_repetitions(52, 5)
3819816
>>> combinations_with_repetitions(0, 0)
1
>>> combinations_with_repetitions(-4, -5)
Traceback (most recent call last):
...
ValueError: Please enter positive integers for total_elements_count and selected_elements_count where total_elements_count >= selected_elements_count
"""
validate_elements_count(total_elements_count, selected_elements_count)
if total_elements_count + selected_elements_count == 0:
return 1
return int(
factorial(total_elements_count + selected_elements_count - 1) /
(factorial(selected_elements_count) * factorial(total_elements_count - 1))
)
def permutations(total_elements_count: int, selected_elements_count: int) -> int:
"""
Calculate the number of permutations of selecting k elements from n elements.
Examples:
>>> permutations(10, 5)
30240
>>> permutations(6, 3)
120
>>> permutations(20, 5)
1860480
>>> permutations(52, 5)
311875200
>>> permutations(0, 0)
1
>>> permutations(-4, -5)
Traceback (most recent call last):
...
ValueError: Please enter positive integers for total_elements_count and selected_elements_count where total_elements_count >= selected_elements_count
"""
validate_elements_count(total_elements_count, selected_elements_count)
remaining_elements_count = total_elements_count - selected_elements_count
return int(factorial(total_elements_count) / factorial(remaining_elements_count))
def possible_selections(total_elements_count: int, selected_elements_count: int) -> int:
"""
Calculate the number of possible selections of k items from n available items, with replacement.
Examples:
>>> possible_selections(10, 5)
100000
>>> possible_selections(6, 3)
216
>>> possible_selections(20, 5)
3200000
>>> possible_selections(52, 5)
380204032
>>> possible_selections(0, 0)
1
>>> possible_selections(-4, -5)
Traceback (most recent call last):
...
ValueError: Please enter positive integers for total_elements_count and selected_elements_count where total_elements_count >= selected_elements_count
"""
validate_elements_count(total_elements_count, selected_elements_count)
return int(total_elements_count ** selected_elements_count)
if __name__ == "__main__":
__import__("doctest").testmod()