Repository navigation
Expand file tree
/
Copy pathfactorial.ts
More file actions
134 lines (107 loc) · 3.45 KB
/
Copy pathfactorial.ts
File metadata and controls
134 lines (107 loc) · 3.45 KB
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
import multiply from "./multiply";
import compare, { isEqual } from "./compare";
import { parseStringNumber, isInteger, isZero, addOne } from "./utils";
/**
* Calculates factorial of a non-negative integer
* n! = n × (n-1) × (n-2) × ... × 2 × 1
* Special cases: 0! = 1, 1! = 1
* @param n Non-negative integer as string
* @returns Factorial as string
*/
export function factorial(n: string): string {
if (!isInteger(n)) {
throw new Error("Factorial is only defined for integers");
}
const parsed = parseStringNumber(n);
if (parsed.sign === -1) {
throw new Error("Factorial is not defined for negative numbers");
}
if (isZero(n) || isEqual(n, "1")) {
return "1";
}
// Calculate n! = n × (n-1) × (n-2) × ... × 2 × 1
let result = "1";
let current = "2";
while (compare(current, n) <= 0) {
result = multiply(result, current);
current = addOne(current);
}
return result;
}
/**
* Calculates the number of ways to choose r items from n items (combinations)
* C(n,r) = n! / (r! × (n-r)!)
* @param n Total number of items
* @param r Number of items to choose
* @returns Number of combinations as string
*/
export function combination(n: string, r: string): string {
if (!isInteger(n) || !isInteger(r)) {
throw new Error("Combination requires integer arguments");
}
const nParsed = parseStringNumber(n);
const rParsed = parseStringNumber(r);
if (nParsed.sign === -1 || rParsed.sign === -1) {
throw new Error("Combination is not defined for negative numbers");
}
if (compare(r, n) > 0) {
return "0"; // C(n,r) = 0 when r > n
}
if (isZero(r) || isEqual(r, n)) {
return "1"; // C(n,0) = C(n,n) = 1
}
// Optimize: C(n,r) = C(n,n-r), use the smaller value
const nMinusR = require("./subtract").default(n, r);
if (compare(r, nMinusR) > 0) {
r = nMinusR;
}
// Calculate C(n,r) = n! / (r! × (n-r)!)
// But we can optimize this to avoid calculating large factorials:
// C(n,r) = (n × (n-1) × ... × (n-r+1)) / (r × (r-1) × ... × 1)
let numerator = "1";
let denominator = "1";
let i = "0";
while (compare(i, r) < 0) {
// numerator *= (n - i)
const nMinusI = require("./subtract").default(n, i);
numerator = multiply(numerator, nMinusI);
// denominator *= (i + 1)
const iPlus1 = addOne(i);
denominator = multiply(denominator, iPlus1);
i = addOne(i);
}
return require("./divide").default(numerator, denominator, 0);
}
/**
* Calculates the number of ways to arrange r items from n items (permutations)
* P(n,r) = n! / (n-r)!
* @param n Total number of items
* @param r Number of items to arrange
* @returns Number of permutations as string
*/
export function permutation(n: string, r: string): string {
if (!isInteger(n) || !isInteger(r)) {
throw new Error("Permutation requires integer arguments");
}
const nParsed = parseStringNumber(n);
const rParsed = parseStringNumber(r);
if (nParsed.sign === -1 || rParsed.sign === -1) {
throw new Error("Permutation is not defined for negative numbers");
}
if (compare(r, n) > 0) {
return "0"; // P(n,r) = 0 when r > n
}
if (isZero(r)) {
return "1"; // P(n,0) = 1
}
// Calculate P(n,r) = n × (n-1) × ... × (n-r+1)
let result = "1";
let i = "0";
while (compare(i, r) < 0) {
// result *= (n - i)
const nMinusI = require("./subtract").default(n, i);
result = multiply(result, nMinusI);
i = addOne(i);
}
return result;
}