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
|
package math_big
/*
With `n` items, calculate how many ways that `r` of them can be ordered.
*/
permutations_with_repetition :: int_pow_int
/*
With `n` items, calculate how many ways that `r` of them can be ordered without any repeats.
*/
permutations_without_repetition :: proc(dest: ^Int, n, r: int) -> (error: Error) {
if n == r {
return factorial(dest, n)
}
tmp := &Int{}
defer internal_destroy(tmp)
// n!
// --------
// (n - r)!
factorial(dest, n) or_return
factorial(tmp, n - r) or_return
div(dest, dest, tmp) or_return
return
}
/*
With `n` items, calculate how many ways that `r` of them can be chosen.
Also known as the multiset coefficient or (n multichoose k).
*/
combinations_with_repetition :: proc(dest: ^Int, n, r: int) -> (error: Error) {
// (n + r - 1)!
// ------------
// r! (n - 1)!
return combinations_without_repetition(dest, n + r - 1, r)
}
/*
With `n` items, calculate how many ways that `r` of them can be chosen without any repeats.
Also known as the binomial coefficient or (n choose k).
*/
combinations_without_repetition :: proc(dest: ^Int, n, r: int) -> (error: Error) {
tmp_a, tmp_b := &Int{}, &Int{}
defer internal_destroy(tmp_a, tmp_b)
// n!
// ------------
// r! (n - r)!
factorial(dest, n) or_return
factorial(tmp_a, r) or_return
factorial(tmp_b, n - r) or_return
mul(tmp_a, tmp_a, tmp_b) or_return
div(dest, dest, tmp_a) or_return
return
}
|
