Line data Source code
1 : /*************************************************************************
2 : *
3 : * Project
4 : * _____ _____ __ __ _____
5 : * / ____| __ \| \/ | __ \
6 : * ___ _ __ ___ _ __ | | __| |__) | \ / | |__) |
7 : * / _ \| '_ \ / _ \ '_ \| | |_ | ___/| |\/| | ___/
8 : *| (_) | |_) | __/ | | | |__| | | | | | | |
9 : * \___/| .__/ \___|_| |_|\_____|_| |_| |_|_|
10 : * | |
11 : * |_|
12 : *
13 : * Copyright (C) Akiel Aries, <akiel@akiel.org>, et al.
14 : *
15 : * This software is licensed as described in the file LICENSE, which
16 : * you should have received as part of this distribution. The terms
17 : * among other details are referenced in the official documentation
18 : * seen here : https://akielaries.github.io/openGPMP/ along with
19 : * important files seen in this project.
20 : *
21 : * You may opt to use, copy, modify, merge, publish, distribute
22 : * and/or sell copies of the Software, and permit persons to whom
23 : * the Software is furnished to do so, under the terms of the
24 : * LICENSE file.
25 : *
26 : *
27 : *
28 : * This software is distributed on an AS IS basis, WITHOUT
29 : * WARRANTY OF ANY KIND, either express or implied.
30 : *
31 : ************************************************************************/
32 : #include <algorithm>
33 : #include <cmath>
34 : #include <cstdint>
35 : #include <numeric>
36 : #include <openGPMP/disct/comb.hpp>
37 : #include <string>
38 : #include <vector>
39 :
40 : // Function to calculate permutations (n P r)
41 0 : int64_t gpmp::Comb::permutation(int n, int r) {
42 0 : if (n < r)
43 0 : return 0; // Invalid input
44 0 : int64_t result = 1;
45 0 : for (int i = 0; i < r; ++i) {
46 0 : result *= (n - i);
47 : }
48 0 : return result;
49 : }
50 :
51 : // Function to calculate combinations (n C r)
52 0 : int64_t gpmp::Comb::combination(int n, int r) {
53 0 : if (n < r)
54 0 : return 0; // Invalid input
55 0 : r = std::min(r, n - r); // Optimization to reduce calculations
56 0 : int64_t result = 1;
57 0 : for (int i = 0; i < r; ++i) {
58 0 : result *= (n - i);
59 0 : result /= (i + 1);
60 : }
61 0 : return result;
62 : }
63 :
64 : // Function to calculate binomial coefficient (n choose r)
65 0 : int64_t gpmp::Comb::binom_coeff(int n, int r) {
66 0 : if (n < r)
67 0 : return 0; // Invalid input
68 0 : r = std::min(r, n - r); // Optimization to reduce calculations
69 0 : std::vector<int64_t> dp(r + 1, 0);
70 0 : dp[0] = 1;
71 0 : for (int i = 1; i <= n; ++i) {
72 0 : for (int j = std::min(i, r); j > 0; --j) {
73 0 : dp[j] = dp[j] + dp[j - 1];
74 : }
75 : }
76 0 : return dp[r];
77 0 : }
78 :
79 : // Function to calculate factorial (n!)
80 0 : int64_t gpmp::Comb::factorial(int n) {
81 0 : if (n < 0)
82 0 : return 0; // Invalid input
83 0 : int64_t result = 1;
84 0 : for (int i = 1; i <= n; ++i) {
85 0 : result *= i;
86 : }
87 0 : return result;
88 : }
89 :
90 : // Function to generate all partitions of an integer n
91 0 : std::vector<std::vector<int>> gpmp::Comb::partitions(int n) {
92 0 : std::vector<std::vector<int>> result;
93 0 : std::vector<int> partition;
94 0 : generatePartitions(n, n, partition, result);
95 0 : return result;
96 0 : }
97 :
98 : // Function to generate Bell numbers up to n
99 0 : std::vector<int64_t> gpmp::Comb::bell_num(int n) {
100 0 : std::vector<int64_t> bell(n + 1, 0);
101 0 : bell[0] = 1;
102 0 : for (int i = 1; i <= n; ++i) {
103 0 : for (int j = 0; j < i; ++j) {
104 0 : bell[i] += binom_coeff(i - 1, j) * bell[j];
105 : }
106 : }
107 0 : return bell;
108 0 : }
109 :
110 : // Function to calculate Stirling numbers of the second kind (S(n, k))
111 0 : int64_t gpmp::Comb::stirling_num(int n, int k) {
112 0 : if (n < k)
113 0 : return 0;
114 0 : if (n == 0 && k == 0)
115 0 : return 1;
116 0 : if (k == 0 || k == n)
117 0 : return 1;
118 0 : return k * stirling_num(n - 1, k) + stirling_num(n - 1, k - 1);
119 : }
120 :
121 : // Function to generate Gray codes of length n
122 0 : std::vector<int> gpmp::Comb::gray_code(int n) {
123 0 : std::vector<int> gray;
124 0 : for (int i = 0; i < (1 << n); ++i) {
125 0 : gray.push_back(i ^ (i >> 1));
126 : }
127 0 : return gray;
128 0 : }
129 :
130 : // Function to calculate the number of derangements (subfactorial)
131 0 : int64_t gpmp::Comb::subfactorial(int n) {
132 0 : if (n == 0)
133 0 : return 1;
134 0 : if (n == 1)
135 0 : return 0;
136 0 : return (n - 1) * (subfactorial(n - 1) + subfactorial(n - 2));
137 : }
138 :
139 : // Function to calculate the number of increasing subsequences of length k in a
140 : // permutation of length n
141 0 : int64_t gpmp::Comb::subsequences(int n, int k) {
142 0 : if (k > n)
143 0 : return 0;
144 0 : std::vector<int64_t> dp(n + 1, 0);
145 0 : dp[0] = 1;
146 0 : for (int i = 1; i <= n; ++i) {
147 0 : for (int j = i - 1; j >= 0; --j) {
148 0 : dp[i] += dp[j];
149 : }
150 : }
151 0 : int64_t result = 0;
152 0 : for (int i = n - k; i <= n; ++i) {
153 0 : result += dp[i];
154 : }
155 0 : return result;
156 0 : }
157 :
158 : // Function to generate all partitions of an integer n using distinct parts
159 0 : std::vector<std::vector<int>> gpmp::Comb::partition_distinct(int n) {
160 0 : std::vector<std::vector<int>> result;
161 0 : std::vector<int> partition;
162 0 : gen_partition_distinct(n, n, partition, result);
163 0 : return result;
164 0 : }
165 :
166 : // Function to generate all compositions of an integer n (ordered partitions)
167 0 : std::vector<std::vector<int>> gpmp::Comb::compositions(int n) {
168 0 : std::vector<std::vector<int>> result;
169 0 : std::vector<int> composition;
170 0 : gen_compositions(n, n, composition, result);
171 0 : return result;
172 0 : }
173 :
174 : // Function to calculate the number of Dyck words of length 2n
175 0 : int64_t gpmp::Comb::dyck_words(int n) {
176 0 : return binom_coeff(2 * n, n) / (n + 1);
177 : }
178 :
179 : // Function to generate all Dyck words of length 2n
180 0 : std::vector<std::string> gpmp::Comb::gen_dyck_words_until(int n) {
181 0 : std::vector<std::string> dyck_words;
182 0 : gen_dyck_words("", n, n, dyck_words);
183 0 : return dyck_words;
184 0 : }
185 :
186 : // Function to calculate the number of necklaces with n beads of k different
187 : // colors
188 0 : int64_t gpmp::Comb::necklaces(int n, int k) {
189 0 : if (n == 0)
190 0 : return 0;
191 0 : int64_t result = 0;
192 0 : for (int d : divisors(n)) {
193 0 : result += phi(n / d) * pow(k, d);
194 0 : }
195 0 : return result / n;
196 : }
197 :
198 : // Function to calculate Euler's totient function (phi)
199 0 : int gpmp::Comb::phi(int n) {
200 0 : int result = n;
201 0 : for (int p = 2; p * p <= n; ++p) {
202 0 : if (n % p == 0) {
203 0 : while (n % p == 0) {
204 0 : n /= p;
205 : }
206 0 : result -= result / p;
207 : }
208 : }
209 0 : if (n > 1) {
210 0 : result -= result / n;
211 : }
212 0 : return result;
213 : }
214 :
215 : // Function to generate all necklaces with n beads of k different colors
216 0 : std::vector<std::vector<int>> gpmp::Comb::generateNecklaces(int n, int k) {
217 0 : std::vector<std::vector<int>> necklaces;
218 0 : std::vector<int> necklace(n, 0);
219 0 : gen_necklaces(necklace, 0, n, k, necklaces);
220 0 : return necklaces;
221 0 : }
222 :
223 : // Function to calculate the number of Lyndon words of length n
224 0 : int64_t gpmp::Comb::lyndonWords(int n) {
225 0 : int64_t result = 0;
226 0 : for (int d : divisors(n)) {
227 0 : result += phi(n / d);
228 0 : }
229 0 : return result;
230 : }
231 :
232 : // Function to generate all Lyndon words of length n
233 0 : std::vector<std::string> gpmp::Comb::generateLyndonWords(int n) {
234 0 : std::vector<std::string> lyndonWords;
235 0 : gen_lyndon_words("", n, n, lyndonWords);
236 0 : return lyndonWords;
237 0 : }
238 :
239 : // Helper function for generating partitions recursively
240 0 : void gpmp::Comb::generatePartitions(int n,
241 : int max,
242 : std::vector<int> &partition,
243 : std::vector<std::vector<int>> &result) {
244 0 : if (n == 0) {
245 0 : result.push_back(partition);
246 0 : return;
247 : }
248 :
249 0 : for (int i = std::min(n, max); i >= 1; --i) {
250 0 : partition.push_back(i);
251 0 : generatePartitions(n - i, i, partition, result);
252 0 : partition.pop_back();
253 : }
254 : }
255 :
256 : // Helper function for generating partitions with distinct parts recursively
257 0 : void gpmp::Comb::gen_partition_distinct(int n,
258 : int max,
259 : std::vector<int> &partition,
260 : std::vector<std::vector<int>> &result) {
261 0 : if (n == 0) {
262 0 : result.push_back(partition);
263 0 : return;
264 : }
265 :
266 0 : for (int i = std::min(n, max); i >= 1; --i) {
267 0 : if (std::find(partition.begin(), partition.end(), i) ==
268 0 : partition.end()) {
269 0 : partition.push_back(i);
270 0 : gen_partition_distinct(n - i, i, partition, result);
271 0 : partition.pop_back();
272 : }
273 : }
274 : }
275 :
276 : // Helper function for generating compositions recursively
277 0 : void gpmp::Comb::gen_compositions(int n,
278 : int max,
279 : std::vector<int> &composition,
280 : std::vector<std::vector<int>> &result) {
281 0 : if (n == 0) {
282 0 : result.push_back(composition);
283 0 : return;
284 : }
285 :
286 0 : for (int i = std::min(n, max); i >= 1; --i) {
287 0 : composition.push_back(i);
288 0 : gen_compositions(n - i, i, composition, result);
289 0 : composition.pop_back();
290 : }
291 : }
292 :
293 : // Helper function for generating all Dyck words recursively
294 0 : void gpmp::Comb::gen_dyck_words(std::string prefix,
295 : int open,
296 : int close,
297 : std::vector<std::string> &dyck_words) {
298 0 : if (open == 0 && close == 0) {
299 0 : dyck_words.push_back(prefix);
300 0 : return;
301 : }
302 0 : if (open > 0) {
303 0 : gen_dyck_words(prefix + "(", open - 1, close, dyck_words);
304 : }
305 0 : if (close > open) {
306 0 : gen_dyck_words(prefix + ")", open, close - 1, dyck_words);
307 : }
308 : }
309 :
310 : // Helper function for generating all necklaces recursively
311 0 : void gpmp::Comb::gen_necklaces(std::vector<int> &necklace,
312 : int index,
313 : int n,
314 : int k,
315 : std::vector<std::vector<int>> &necklaces) {
316 0 : if (index == n) {
317 0 : necklaces.push_back(necklace);
318 0 : return;
319 : }
320 :
321 0 : for (int color = 1; color <= k; ++color) {
322 0 : necklace[index] = color;
323 0 : gen_necklaces(necklace, index + 1, n, k, necklaces);
324 : }
325 : }
326 :
327 : // Helper function for generating all Lyndon words recursively
328 0 : void gpmp::Comb::gen_lyndon_words(std::string prefix,
329 : int n,
330 : int max,
331 : std::vector<std::string> &lyndonWords) {
332 0 : if (static_cast<int>(prefix.size()) == n) {
333 0 : lyndonWords.push_back(prefix);
334 0 : return;
335 : }
336 :
337 0 : for (char c = (prefix.empty() ? 'a' : prefix.back() + 1);
338 0 : c <= 'z' && static_cast<int>(prefix.size()) < n;
339 : ++c) {
340 0 : if (n % (static_cast<int>(prefix.size()) + 1) == 0) {
341 0 : gen_lyndon_words(prefix + c, n, prefix.size() + 1, lyndonWords);
342 : } else {
343 0 : gen_lyndon_words(prefix + c, n, max, lyndonWords);
344 : }
345 : }
346 : }
347 :
348 : // Function to compute all divisors of a positive integer
349 0 : std::vector<int> gpmp::Comb::divisors(int n) {
350 0 : std::vector<int> divs;
351 0 : for (int i = 1; i * i <= n; ++i) {
352 0 : if (n % i == 0) {
353 0 : divs.push_back(i);
354 0 : if (i != n / i) {
355 0 : divs.push_back(n / i);
356 : }
357 : }
358 : }
359 0 : return divs;
360 0 : }
|
