Frobby 0.9.5
dynamicFrobeniusAlgorithm.cpp
Go to the documentation of this file.
1/* Frobby: Software for monomial ideal computations.
2 Copyright (C) 2007 Bjarke Hammersholt Roune (www.broune.com)
3
4 This program is free software; you can redistribute it and/or modify
5 it under the terms of the GNU General Public License as published by
6 the Free Software Foundation; either version 2 of the License, or
7 (at your option) any later version.
8
9 This program is distributed in the hope that it will be useful,
10 but WITHOUT ANY WARRANTY; without even the implied warranty of
11 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
12 GNU General Public License for more details.
13
14 You should have received a copy of the GNU General Public License
15 along with this program. If not, see http://www.gnu.org/licenses/.
16*/
17#include "stdinc.h"
19
20#include <set>
21#include <algorithm>
22
23mpz_class dynamicFrobeniusAlgorithm(const vector<mpz_class>& numbers) {
24 if (numbers.size() == 2)
25 return numbers[0] * numbers[1] - numbers[0] - numbers[1];
26
27 set<mpz_class> representable;
28 representable.insert(0);
29 mpz_class minNumber = *min_element(numbers.begin(), numbers.end());
30
31 mpz_class maximumNotRepresentable = 0;
32 int representableRun = 0;
33 mpz_class number = 1;
34
35 while (representableRun < minNumber) {
36 bool isNumberRepresentable = false;
37
38 for (size_t i = 0; i < numbers.size(); ++i) {
39 if (representable.find(number - numbers[i]) !=
40 representable.end()) {
41 isNumberRepresentable = true;
42 break;
43 }
44 }
45
46 if (isNumberRepresentable) {
47 representable.insert(number);
48 ++representableRun;
49 } else {
50 maximumNotRepresentable = number;
51 representableRun = 0;
52 }
53
54 ++number;
55 }
56
57 return maximumNotRepresentable;
58}
mpz_class dynamicFrobeniusAlgorithm(const vector< mpz_class > &numbers)
This header file includes common definitions and is included as the first line of code in every imple...