34 for (
size_t var = 1; var < variableCount; ++var) {
47 if (mpz_class(rowCount) * mpz_class(columnCount) >
48 numeric_limits<size_t>::max())
49 reportError(
"Number of positions on requested chess board too large.");
53 for (
size_t row = 0; row < rowCount; ++row) {
54 for (
size_t column = 0; column < columnCount; ++column) {
56 name <<
'r' << (row + 1) <<
'c' << (column + 1);
64 for (
size_t row = 0; row < rowCount; ++row) {
65 for (
size_t column = 0; column < columnCount; ++column) {
66 for (
size_t delta = 0; delta < deltaCount; ++delta) {
69 if (deltaRow[delta] == numeric_limits<int>::min() ||
70 (deltaRow[delta] < 0 &&
71 row < (size_t)-deltaRow[delta]) ||
72 (deltaRow[delta] > 0 &&
73 rowCount - row <= (size_t)deltaRow[delta]))
76 if (deltaColumn[delta] == numeric_limits<int>::min() ||
77 (deltaColumn[delta] < 0 &&
78 column < (size_t)-deltaColumn[delta]) ||
79 (deltaColumn[delta] > 0 &&
80 columnCount - column <= (size_t)deltaColumn[delta]))
83 Term chessMove(ideal.getVarCount());
84 chessMove[row * columnCount + column] = 1;
86 size_t targetRow = row + deltaRow[delta];
87 size_t targetColumn = column + deltaColumn[delta];
88 ASSERT(targetRow < rowCount);
89 ASSERT(targetColumn < columnCount);
91 chessMove[targetRow * columnCount + targetColumn] = 1;
92 ideal.insert(chessMove);
97 ideal.sortReverseLex();
102 int deltaRow[] = {-1, 0, 1, 1};
103 int deltaColumn[] = { 1, 1, 1, 0};
104 ASSERT(
sizeof(deltaRow) ==
sizeof(deltaColumn));
106 size_t deltaCount =
sizeof(deltaRow) /
sizeof(
int);
109 deltaRow, deltaColumn, deltaCount);
113 int deltaRow[] = {-1, 1, 2, 2};
114 int deltaColumn[] = { 2, 2, 1, -1};
115 ASSERT(
sizeof(deltaRow) ==
sizeof(deltaColumn));
117 size_t deltaCount =
sizeof(deltaRow) /
sizeof(
int);
120 deltaRow, deltaColumn, deltaCount);
127 bool nextBitPattern(vector<char>& pattern) {
128 typedef vector<char>::iterator iterator;
129 for (iterator it = pattern.begin(); it != pattern.end(); ++it) {
134 ASSERT(pattern != vector<char>(pattern.size()));
139 ASSERT(pattern == vector<char>(pattern.size()));
155 vector<char> pattern(varCount);
156 while (nextBitPattern(pattern)) {
158 typedef vector<char>::iterator iterator;
159 for (iterator it = pattern.begin(); it != pattern.end(); ++it)
160 setSize += (
size_t)*it;
162 exponent = varCount - setSize + 1;
164 for (
size_t var = 0; var < varCount; ++var)
171 if (n == 0 || k == 0)
172 reportError(
"One side of rook ideal has zero vertices.");
173 if (n > 1000 || k > 1000)
174 reportError(
"Number of variables in rook ideal too large.");
178 size_t varCount = n * k;
179 Ideal ideal(varCount);
182 vector<char> taken(k);
183 vector<size_t> choice(n);
186 if (choice[level] == k) {
190 ASSERT(static_cast<bool>(taken[choice[level]]) ==
true);
191 ASSERT(term[level * k + choice[level]] == 1);
192 taken[choice[level]] =
false;
193 term[level * k + choice[level]] = 0;
197 if (taken[choice[level]]) {
201 taken[choice[level]] =
true;
202 ASSERT(term[level * k + choice[level]] == 0);
203 term[level * k + choice[level]] = 1;
210 ASSERT(static_cast<bool>(taken[choice[level]]) ==
true);
211 ASSERT(term[level * k + choice[level]] == 1);
212 taken[choice[level]] =
false;
213 term[level * k + choice[level]] = 0;
225 reportError(
"Too few variables in matching ideal.");
226 if (n > 1000 || n > 1000)
227 reportError(
"Number of variables in matching ideal too large.");
231 State(
size_t nodeCount):
232 _notTaken(-1), _nodes(nodeCount), _isAnchor(nodeCount) {
233 std::fill(_nodes.begin(), _nodes.end(), _notTaken);
234 const size_t varCount = nodeCount * (nodeCount - 1) / 2;
235 _term.reset(varCount);
238 void takeEdge(
size_t anchor,
size_t other) {
239 ASSERT(anchor < _nodes.size());
240 ASSERT(other < _nodes.size());
243 _nodes[anchor] = other;
244 _nodes[other] = anchor;
245 _isAnchor[anchor] =
true;
247 const size_t var = edgeToVar(anchor, other);
252 void takeNode(
size_t node) {
253 ASSERT(node < getNodeCount());
259 void dropNode(
size_t node) {
260 ASSERT(node < getNodeCount());
263 ASSERT(_nodes[node] == node);
264 _nodes[node] = _notTaken;
267 void dropEdge(
size_t anchor) {
268 ASSERT(anchor < _nodes.size());
271 _isAnchor[anchor] =
false;
272 const size_t other = _nodes[anchor];
273 _nodes[other] = _notTaken;
274 _nodes[anchor] = _notTaken;
276 const size_t var = edgeToVar(anchor, other);
281 size_t getNeighbor(
size_t node)
const {
286 bool isAnchor(
size_t node)
const {
287 ASSERT(node < _nodes.size());
288 return _isAnchor[node];
291 bool isTaken(
size_t node)
const {
292 ASSERT(node < _nodes.size());
293 return _nodes[node] != _notTaken;
296 const Term& getTerm()
const {
return _term;}
297 size_t getNodeCount()
const {
return _nodes.size();}
301 size_t getAnchorLeft(
size_t node)
const {
302 ASSERT(node <= getNodeCount());
303 for (--node; node !=
static_cast<size_t>(-1); --node)
311 size_t getNotTakenRight(
size_t node)
const {
312 ASSERT(node < getNodeCount());
313 for (++node; node < getNodeCount(); ++node)
320 size_t edgeToVar(
size_t a,
size_t b)
const {
322 ASSERT(a < _nodes.size());
323 ASSERT(b < _nodes.size());
326 const size_t var = (a * (a - 1)) / 2 + b;
327 ASSERT(var < _term.getVarCount());
331 const size_t _notTaken;
332 std::vector<size_t> _nodes;
333 std::vector<size_t> _isAnchor;
338 Ideal ideal(state.getTerm().getVarCount());
342 size_t notUsed = state.getNodeCount();
343 if (state.getNodeCount() % 2 == 1) {
345 state.takeNode(notUsed);
349 if (node == static_cast<size_t>(-1)) {
350 if (notUsed < state.getNodeCount()) {
351 state.dropNode(notUsed);
354 if (notUsed == state.getNodeCount())
356 state.takeNode(notUsed);
359 ASSERT(node <= state.getNodeCount());
360 if (node == state.getNodeCount()) {
361 ideal.insert(state.getTerm());
362 node = state.getAnchorLeft(node);
363 }
else if (!state.isTaken(node)) {
364 const size_t neighbor = state.getNotTakenRight(node);
365 if (neighbor == state.getNodeCount()) {
366 node = state.getAnchorLeft(node);
368 state.takeEdge(node, neighbor);
369 node = state.getNotTakenRight(neighbor);
372 ASSERT(state.isTaken(node));
373 ASSERT(state.isAnchor(node));
374 const size_t neighbor = state.getNeighbor(node);
375 const size_t nextNeighbor = state.getNotTakenRight(neighbor);
376 state.dropEdge(node);
377 if (nextNeighbor == state.getNodeCount()) {
378 node = state.getAnchorLeft(node);
380 state.takeEdge(node, nextNeighbor);
381 node = state.getNotTakenRight(node);
386 VarNames names(state.getTerm().getVarCount());
392 (
BigIdeal& bigIdeal,
size_t variableCount,
size_t generatorCount) {
393 Ideal ideal(variableCount);
394 Term term(variableCount);
396 size_t generatorsToGo = generatorCount;
397 size_t triesLeft = (size_t)4 * 1000 * 1000;
398 while (generatorsToGo > 0 && triesLeft > 0) {
401 size_t a = rand() % variableCount;
402 size_t b = rand() % variableCount;
424 return generatorsToGo == 0;
429 size_t exponentRange,
430 size_t variableCount,
431 size_t generatorCount) {
432 Ideal ideal(variableCount);
433 Term term(variableCount);
435 size_t generatorsToGo = generatorCount;
436 size_t triesLeft = (size_t)4 * 1000 * 1000;
437 while (generatorsToGo > 0 && triesLeft > 0) {
440 for (
size_t var = 0; var < variableCount; ++var) {
442 if (exponentRange != numeric_limits<size_t>::max())
443 term[var] %= exponentRange + 1;
456 return generatorsToGo == 0;
461 const mpz_class& maxEntry) {
465 gmp_randclass random(gmp_randinit_default);
468 random.seed((
unsigned long)time(0) +
470 (
unsigned long)getpid() +
472 (
unsigned long)clock());
474 instance.resize(entryCount);
477 for (
size_t i = 0; i < entryCount; ++i)
478 instance[i] = random.get_z_range(maxEntry) + 1;
481 mpz_class
gcd = instance[0];
482 for (
size_t i = 1; i < entryCount; ++i)
483 mpz_gcd(gcd.get_mpz_t(), gcd.get_mpz_t(), instance[i].get_mpz_t());
486 instance.front() /=
gcd;
488 sort(instance.begin(), instance.end());
void clearAndSetNames(const VarNames &names)
bool isIncomparable(const Exponent *term) const
void insert(const Ideal &ideal)
mpz_class & getLastTermExponentRef(size_t var)
void generateKingChessIdeal(BigIdeal &ideal, size_t rowsAndColumns)
Generate an ideal where is a generator when and indicate coordinates on a square chessboard where ...
void reserve(size_t capacity)
Represents a monomial ideal with int exponents.
bool generateRandomEdgeIdeal(BigIdeal &bigIdeal, size_t variableCount, size_t generatorCount)
Generate a random ideal where every edge is a product of two different variables. ...
Defines the variables of a polynomial ring and facilities IO involving them.
bool addVar(const string &name)
Adds the variable and returns true if name is not already a variable.
size_t getVarCount() const
void gcd(Word *res, const Word *resEnd, const Word *a, const Word *b)
void generateTreeIdeal(BigIdeal &ideal, size_t varCount)
Generate an ideal in varCount variables with minimal generators given by i.e.
void generateRandomFrobeniusInstance(vector< mpz_class > &instance, size_t entryCount, const mpz_class &maxEntry)
Generate a random vector of numbers whose gcd is 1.
This file contains functions that generate data.
void generateRookChessIdeal(BigIdeal &bigIdeal, size_t n, size_t k)
Generate an ideal in n*k variables.
void generateLinkedListIdeal(BigIdeal &ideal, size_t variableCount)
Generate an ideal of the form , and so on.
bool generateRandomIdeal(BigIdeal &bigIdeal, size_t exponentRange, size_t variableCount, size_t generatorCount)
Generate a random ideal with exponents in the range [0, exponentRange].
void generateKnightChessIdeal(BigIdeal &ideal, size_t rowsAndColumns)
Generate an ideal where is a generator when and indicate coordinates on a square chessboard where ...
void generateChessIdeal(BigIdeal &bigIdeal, size_t rowCount, size_t columnCount, int deltaRow[], int deltaColumn[], size_t deltaCount)
void reportError(const string &errorMsg)
void insert(const Exponent *term)
A replacement for stringstream.
void generateMatchingIdeal(BigIdeal &bigIdeal, size_t n)
Generate an ideal whose facets are the maximum matchings in an n-clique.
Term represents a product of variables which does not include a coefficient.
void swap(hashtable< _Val, _Key, _HF, _Extract, _EqKey, _All > &__ht1, hashtable< _Val, _Key, _HF, _Extract, _EqKey, _All > &__ht2)