diff options
| -rw-r--r-- | core/math/big/combinatorics.odin | 60 | ||||
| -rw-r--r-- | tests/core/math/big/test.odin | 2 | ||||
| -rw-r--r-- | tests/core/math/big/test_core_math_big.odin | 37 |
3 files changed, 98 insertions, 1 deletions
diff --git a/core/math/big/combinatorics.odin b/core/math/big/combinatorics.odin new file mode 100644 index 000000000..87c76d830 --- /dev/null +++ b/core/math/big/combinatorics.odin @@ -0,0 +1,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 +} diff --git a/tests/core/math/big/test.odin b/tests/core/math/big/test.odin index e0762a66d..f35f0b72b 100644 --- a/tests/core/math/big/test.odin +++ b/tests/core/math/big/test.odin @@ -8,7 +8,7 @@ This file exports procedures for use with the test.py test suite. */ -package math_big_tests +package test_core_math_big /* TODO: Write tests for `internal_*` and test reusing parameters with the public implementations. diff --git a/tests/core/math/big/test_core_math_big.odin b/tests/core/math/big/test_core_math_big.odin new file mode 100644 index 000000000..9a1e7b01b --- /dev/null +++ b/tests/core/math/big/test_core_math_big.odin @@ -0,0 +1,37 @@ +package test_core_math_big + +import "core:math/big" +import "core:testing" + +@(test) +test_permutations_and_combinations :: proc(t: ^testing.T) { + { + calc, exp := &big.Int{}, &big.Int{} + defer big.destroy(calc, exp) + big.permutations_without_repetition(calc, 9000, 10) + big.int_atoi(exp, "3469387884476822917768284664849390080000") + equals, error := big.equals(calc, exp) + testing.expect(t, equals) + testing.expect_value(t, error, nil) + } + + { + calc, exp := &big.Int{}, &big.Int{} + defer big.destroy(calc, exp) + big.combinations_with_repetition(calc, 9000, 10) + big.int_atoi(exp, "965678962435231708695393645683400") + equals, error := big.equals(calc, exp) + testing.expect(t, equals) + testing.expect_value(t, error, nil) + } + + { + calc, exp := &big.Int{}, &big.Int{} + defer big.destroy(calc, exp) + big.combinations_without_repetition(calc, 9000, 10) + big.int_atoi(exp, "956070294443568925751842114431600") + equals, error := big.equals(calc, exp) + testing.expect(t, equals) + testing.expect_value(t, error, nil) + } +} |