GiNaC  1.8.0
utils.h
Go to the documentation of this file.
1 
6 /*
7  * GiNaC Copyright (C) 1999-2020 Johannes Gutenberg University Mainz, Germany
8  *
9  * This program is free software; you can redistribute it and/or modify
10  * it under the terms of the GNU General Public License as published by
11  * the Free Software Foundation; either version 2 of the License, or
12  * (at your option) any later version.
13  *
14  * This program is distributed in the hope that it will be useful,
15  * but WITHOUT ANY WARRANTY; without even the implied warranty of
16  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
17  * GNU General Public License for more details.
18  *
19  * You should have received a copy of the GNU General Public License
20  * along with this program; if not, write to the Free Software
21  * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA
22  */
23 
24 #ifndef GINAC_UTILS_H
25 #define GINAC_UTILS_H
26 
27 #include "assertion.h"
28 
29 #include <functional>
30 #include <cstdint> // for uintptr_t
31 #include <string>
32 
33 namespace GiNaC {
34 
37 class dunno {};
38 
39 // some compilers (e.g. cygwin) define a macro log2, causing confusion
40 #ifdef log2
41 #undef log2
42 #endif
43 
44 unsigned log2(unsigned n);
45 
48 inline unsigned rotate_left(unsigned n)
49 {
50  return (n & 0x80000000U) ? (n << 1 | 0x00000001U) : (n << 1);
51 }
52 
55 template <class T>
56 inline int compare_pointers(const T * a, const T * b)
57 {
58  // '<' is not defined for pointers that don't point to the same array,
59  // but std::less is.
60  if (std::less<const T *>()(a, b))
61  return -1;
62  else if (std::less<const T *>()(b, a))
63  return 1;
64  return 0;
65 }
66 
68 inline unsigned golden_ratio_hash(uintptr_t n)
69 {
70  return n * UINT64_C(0x4f1bbcdd);
71 }
72 
73 /* Compute the sign of a permutation of a container, with and without an
74  explicitly supplied comparison function. If the sign returned is 1 or -1,
75  the container is sorted after the operation. */
76 template <class It>
77 int permutation_sign(It first, It last)
78 {
79  using std::swap;
80  if (first == last)
81  return 0;
82  --last;
83  if (first == last)
84  return 0;
85  It flag = first;
86  int sign = 1;
87 
88  do {
89  It i = last, other = last;
90  --other;
91  bool swapped = false;
92  while (i != first) {
93  if (*i < *other) {
94  swap(*other, *i);
95  flag = other;
96  swapped = true;
97  sign = -sign;
98  } else if (!(*other < *i))
99  return 0;
100  --i;
101  if (i != first)
102  --other;
103  }
104  if (!swapped)
105  return sign;
106  ++flag;
107  if (flag == last)
108  return sign;
109  first = flag;
110  i = first; other = first;
111  ++other;
112  swapped = false;
113  while (i != last) {
114  if (*other < *i) {
115  swap(*i, *other);
116  flag = other;
117  swapped = true;
118  sign = -sign;
119  } else if (!(*i < *other))
120  return 0;
121  ++i;
122  if (i != last)
123  ++other;
124  }
125  if (!swapped)
126  return sign;
127  last = flag;
128  --last;
129  } while (first != last);
130 
131  return sign;
132 }
133 
134 template <class It, class Cmp, class Swap>
135 int permutation_sign(It first, It last, Cmp comp, Swap swapit)
136 {
137  if (first == last)
138  return 0;
139  --last;
140  if (first == last)
141  return 0;
142  It flag = first;
143  int sign = 1;
144 
145  do {
146  It i = last, other = last;
147  --other;
148  bool swapped = false;
149  while (i != first) {
150  if (comp(*i, *other)) {
151  swapit(*other, *i);
152  flag = other;
153  swapped = true;
154  sign = -sign;
155  } else if (!comp(*other, *i))
156  return 0;
157  --i;
158  if (i != first)
159  --other;
160  }
161  if (!swapped)
162  return sign;
163  ++flag;
164  if (flag == last)
165  return sign;
166  first = flag;
167  i = first; other = first;
168  ++other;
169  swapped = false;
170  while (i != last) {
171  if (comp(*other, *i)) {
172  swapit(*i, *other);
173  flag = other;
174  swapped = true;
175  sign = -sign;
176  } else if (!comp(*i, *other))
177  return 0;
178  ++i;
179  if (i != last)
180  ++other;
181  }
182  if (!swapped)
183  return sign;
184  last = flag;
185  --last;
186  } while (first != last);
187 
188  return sign;
189 }
190 
191 /* Implementation of shaker sort, only compares adjacent elements. */
192 template <class It, class Cmp, class Swap>
193 void shaker_sort(It first, It last, Cmp comp, Swap swapit)
194 {
195  if (first == last)
196  return;
197  --last;
198  if (first == last)
199  return;
200  It flag = first;
201 
202  do {
203  It i = last, other = last;
204  --other;
205  bool swapped = false;
206  while (i != first) {
207  if (comp(*i, *other)) {
208  swapit(*other, *i);
209  flag = other;
210  swapped = true;
211  }
212  --i;
213  if (i != first)
214  --other;
215  }
216  if (!swapped)
217  return;
218  ++flag;
219  if (flag == last)
220  return;
221  first = flag;
222  i = first; other = first;
223  ++other;
224  swapped = false;
225  while (i != last) {
226  if (comp(*other, *i)) {
227  swapit(*i, *other);
228  flag = other;
229  swapped = true;
230  }
231  ++i;
232  if (i != last)
233  ++other;
234  }
235  if (!swapped)
236  return;
237  last = flag;
238  --last;
239  } while (first != last);
240 }
241 
242 /* In-place cyclic permutation of a container (no copying, only swapping). */
243 template <class It, class Swap>
244 void cyclic_permutation(It first, It last, It new_first, Swap swapit)
245 {
246  unsigned num = last - first;
247 again:
248  if (first == new_first || num < 2)
249  return;
250 
251  unsigned num1 = new_first - first, num2 = last - new_first;
252  if (num1 >= num2) {
253  It a = first, b = new_first;
254  while (b != last) {
255  swapit(*a, *b);
256  ++a; ++b;
257  }
258  if (num1 > num2) {
259  first += num2;
260  num = num1;
261  goto again;
262  }
263  } else {
264  It a = new_first, b = last;
265  do {
266  --a; --b;
267  swapit(*a, *b);
268  } while (a != first);
269  last -= num1;
270  num = num2;
271  goto again;
272  }
273 }
274 
279 protected:
280  // Partitions n into m parts, not including zero parts.
281  // (Cf. OEIS sequence A008284; implementation adapted from Jörg Arndt's
282  // FXT library)
283  struct mpartition2
284  {
285  // partition: x[1] + x[2] + ... + x[m] = n and sentinel x[0] == 0
286  std::vector<unsigned> x;
287  unsigned n; // n>0
288  unsigned m; // 0<m<=n
289  mpartition2(unsigned n_, unsigned m_)
290  : x(m_+1), n(n_), m(m_)
291  {
292  for (unsigned k=1; k<m; ++k)
293  x[k] = 1;
294  x[m] = n - m + 1;
295  }
297  {
298  unsigned u = x[m]; // last element
299  unsigned k = m;
300  unsigned s = u;
301  while (--k) {
302  s += x[k];
303  if (x[k] + 2 <= u)
304  break;
305  }
306  if (k==0)
307  return false; // current is last
308  unsigned f = x[k] + 1;
309  while (k < m) {
310  x[k] = f;
311  s -= f;
312  ++k;
313  }
314  x[m] = s;
315  return true;
316  }
317  };
319  basic_partition_generator(unsigned n_, unsigned m_)
320  : mpgen(n_, m_)
321  { }
322 };
323 
328 private:
329  unsigned m; // number of parts 0<m
330  mutable std::vector<unsigned> partition; // current partition
331  mutable bool current_updated; // whether partition vector has been updated
332 public:
333  partition_with_zero_parts_generator(unsigned n_, unsigned m_)
334  : basic_partition_generator(n_, 1), m(m_), partition(m_), current_updated(false)
335  { }
336  // returns current partition in non-decreasing order, padded with zeros
337  const std::vector<unsigned>& get() const
338  {
339  if (!current_updated) {
340  for (unsigned i = 0; i < m - mpgen.m; ++i)
341  partition[i] = 0; // pad with zeros
342 
343  for (unsigned i = m - mpgen.m; i < m; ++i)
344  partition[i] = mpgen.x[i - m + mpgen.m + 1];
345 
346  current_updated = true;
347  }
348  return partition;
349  }
350  bool next()
351  {
352  current_updated = false;
353  if (!mpgen.next_partition()) {
354  if (mpgen.m == m || mpgen.m == mpgen.n)
355  return false; // current is last
356  // increment number of parts
357  mpgen = mpartition2(mpgen.n, mpgen.m + 1);
358  }
359  return true;
360  }
361 };
362 
367 private:
368  mutable std::vector<unsigned> partition; // current partition
369  mutable bool current_updated; // whether partition vector has been updated
370 public:
371  partition_generator(unsigned n_, unsigned m_)
373  { }
374  // returns current partition in non-decreasing order, padded with zeros
375  const std::vector<unsigned>& get() const
376  {
377  if (!current_updated) {
378  for (unsigned i = 0; i < mpgen.m; ++i)
379  partition[i] = mpgen.x[i + 1];
380 
381  current_updated = true;
382  }
383  return partition;
384  }
385  bool next()
386  {
387  current_updated = false;
388  return mpgen.next_partition();
389  }
390 };
391 
396 private:
397  // Generates all distinct permutations of a multiset.
398  // (Based on Aaron Williams' algorithm 1 from "Loopless Generation of
399  // Multiset Permutations using a Constant Number of Variables by Prefix
400  // Shifts." <http://webhome.csc.uvic.ca/~haron/CoolMulti.pdf>)
401  struct coolmulti {
402  // element of singly linked list
403  struct element {
404  unsigned value;
406  element(unsigned val, element* n)
407  : value(val), next(n) {}
409  { // recurses down to the end of the singly linked list
410  delete next;
411  }
412  };
414  // NB: Partition must be sorted in non-decreasing order.
415  explicit coolmulti(const std::vector<unsigned>& partition)
416  : head(nullptr), i(nullptr), after_i(nullptr)
417  {
418  for (unsigned n = 0; n < partition.size(); ++n) {
419  head = new element(partition[n], head);
420  if (n <= 1)
421  i = head;
422  }
423  after_i = i->next;
424  }
426  { // deletes singly linked list
427  delete head;
428  }
430  {
431  element *before_k;
432  if (after_i->next != nullptr && i->value >= after_i->next->value)
433  before_k = after_i;
434  else
435  before_k = i;
436  element *k = before_k->next;
437  before_k->next = k->next;
438  k->next = head;
439  if (k->value < head->value)
440  i = k;
441  after_i = i->next;
442  head = k;
443  }
444  bool finished() const
445  {
446  return after_i->next == nullptr && after_i->value >= head->value;
447  }
448  } cmgen;
449  bool atend; // needed for simplifying iteration over permutations
450  bool trivial; // likewise, true if all elements are equal
451  mutable std::vector<unsigned> composition; // current compositions
452  mutable bool current_updated; // whether composition vector has been updated
453 public:
454  explicit composition_generator(const std::vector<unsigned>& partition)
455  : cmgen(partition), atend(false), trivial(true), composition(partition.size()), current_updated(false)
456  {
457  for (unsigned i=1; i<partition.size(); ++i)
458  trivial = trivial && (partition[0] == partition[i]);
459  }
460  const std::vector<unsigned>& get() const
461  {
462  if (!current_updated) {
464  size_t i = 0;
465  while (it != nullptr) {
466  composition[i] = it->value;
467  it = it->next;
468  ++i;
469  }
470  current_updated = true;
471  }
472  return composition;
473  }
474  bool next()
475  {
476  // This ugly contortion is needed because the original coolmulti
477  // algorithm requires code duplication of the payload procedure,
478  // one before the loop and one inside it.
479  if (trivial || atend)
480  return false;
482  current_updated = false;
483  atend = cmgen.finished();
484  return true;
485  }
486 };
487 
491 const numeric
492 multinomial_coefficient(const std::vector<unsigned> & p);
493 
494 
495 // Collection of `construct on first use' wrappers for safely avoiding
496 // internal object replication without running into the `static
497 // initialization order fiasco'. This chest of numbers helps speed up
498 // the library but should not be used outside it since it is
499 // potentially confusing.
500 
501 class ex;
502 
503 extern const numeric *_num_120_p;
504 extern const ex _ex_120;
505 extern const numeric *_num_60_p;
506 extern const ex _ex_60;
507 extern const numeric *_num_48_p;
508 extern const ex _ex_48;
509 extern const numeric *_num_30_p;
510 extern const ex _ex_30;
511 extern const numeric *_num_25_p;
512 extern const ex _ex_25;
513 extern const numeric *_num_24_p;
514 extern const ex _ex_24;
515 extern const numeric *_num_20_p;
516 extern const ex _ex_20;
517 extern const numeric *_num_18_p;
518 extern const ex _ex_18;
519 extern const numeric *_num_15_p;
520 extern const ex _ex_15;
521 extern const numeric *_num_12_p;
522 extern const ex _ex_12;
523 extern const numeric *_num_11_p;
524 extern const ex _ex_11;
525 extern const numeric *_num_10_p;
526 extern const ex _ex_10;
527 extern const numeric *_num_9_p;
528 extern const ex _ex_9;
529 extern const numeric *_num_8_p;
530 extern const ex _ex_8;
531 extern const numeric *_num_7_p;
532 extern const ex _ex_7;
533 extern const numeric *_num_6_p;
534 extern const ex _ex_6;
535 extern const numeric *_num_5_p;
536 extern const ex _ex_5;
537 extern const numeric *_num_4_p;
538 extern const ex _ex_4;
539 extern const numeric *_num_3_p;
540 extern const ex _ex_3;
541 extern const numeric *_num_2_p;
542 extern const ex _ex_2;
543 extern const numeric *_num_1_p;
544 extern const ex _ex_1;
545 extern const numeric *_num_1_2_p;
546 extern const ex _ex_1_2;
547 extern const numeric *_num_1_3_p;
548 extern const ex _ex_1_3;
549 extern const numeric *_num_1_4_p;
550 extern const ex _ex_1_4;
551 extern const numeric *_num0_p;
552 extern const basic *_num0_bp;
553 extern const ex _ex0;
554 extern const numeric *_num1_4_p;
555 extern const ex _ex1_4;
556 extern const numeric *_num1_3_p;
557 extern const ex _ex1_3;
558 extern const numeric *_num1_2_p;
559 extern const ex _ex1_2;
560 extern const numeric *_num1_p;
561 extern const ex _ex1;
562 extern const numeric *_num2_p;
563 extern const ex _ex2;
564 extern const numeric *_num3_p;
565 extern const ex _ex3;
566 extern const numeric *_num4_p;
567 extern const ex _ex4;
568 extern const numeric *_num5_p;
569 extern const ex _ex5;
570 extern const numeric *_num6_p;
571 extern const ex _ex6;
572 extern const numeric *_num7_p;
573 extern const ex _ex7;
574 extern const numeric *_num8_p;
575 extern const ex _ex8;
576 extern const numeric *_num9_p;
577 extern const ex _ex9;
578 extern const numeric *_num10_p;
579 extern const ex _ex10;
580 extern const numeric *_num11_p;
581 extern const ex _ex11;
582 extern const numeric *_num12_p;
583 extern const ex _ex12;
584 extern const numeric *_num15_p;
585 extern const ex _ex15;
586 extern const numeric *_num18_p;
587 extern const ex _ex18;
588 extern const numeric *_num20_p;
589 extern const ex _ex20;
590 extern const numeric *_num24_p;
591 extern const ex _ex24;
592 extern const numeric *_num25_p;
593 extern const ex _ex25;
594 extern const numeric *_num30_p;
595 extern const ex _ex30;
596 extern const numeric *_num48_p;
597 extern const ex _ex48;
598 extern const numeric *_num60_p;
599 extern const ex _ex60;
600 extern const numeric *_num120_p;
601 extern const ex _ex120;
602 
603 
604 // Helper macros for class implementations (mostly useful for trivial classes)
605 
606 #define DEFAULT_CTOR(classname) \
607 classname::classname() { setflag(status_flags::evaluated | status_flags::expanded); }
608 
609 #define DEFAULT_COMPARE(classname) \
610 int classname::compare_same_type(const basic & other) const \
611 { \
612  /* by default, the objects are always identical */ \
613  return 0; \
614 }
615 
616 #define DEFAULT_PRINT(classname, text) \
617 void classname::do_print(const print_context & c, unsigned level) const \
618 { \
619  c.s << text; \
620 }
621 
622 #define DEFAULT_PRINT_LATEX(classname, text, latex) \
623 DEFAULT_PRINT(classname, text) \
624 void classname::do_print_latex(const print_latex & c, unsigned level) const \
625 { \
626  c.s << latex; \
627 }
628 
629 } // namespace GiNaC
630 
631 #endif // ndef GINAC_UTILS_H
GiNaC::_num3_p
const numeric * _num3_p
Definition: utils.cpp:200
GiNaC::_ex_3
const ex _ex_3
Definition: utils.cpp:152
GiNaC::golden_ratio_hash
unsigned golden_ratio_hash(uintptr_t n)
Truncated multiplication with golden ratio, for computing hash values.
Definition: utils.h:68
GiNaC::composition_generator::composition_generator
composition_generator(const std::vector< unsigned > &partition)
Definition: utils.h:454
GiNaC::_ex120
const ex _ex120
Definition: utils.cpp:273
GiNaC::partition_with_zero_parts_generator::next
bool next()
Definition: utils.h:350
GiNaC::basic_partition_generator::mpartition2::n
unsigned n
Definition: utils.h:287
GiNaC::composition_generator::coolmulti::finished
bool finished() const
Definition: utils.h:444
GiNaC::_ex10
const ex _ex10
Definition: utils.cpp:229
GiNaC::composition_generator::trivial
bool trivial
Definition: utils.h:450
GiNaC::partition_generator::current_updated
bool current_updated
Definition: utils.h:369
GiNaC::composition_generator::coolmulti::coolmulti
coolmulti(const std::vector< unsigned > &partition)
Definition: utils.h:415
GiNaC::composition_generator::coolmulti::element::element
element(unsigned val, element *n)
Definition: utils.h:406
GiNaC::_ex30
const ex _ex30
Definition: utils.cpp:261
GiNaC::_ex_25
const ex _ex_25
Definition: utils.cpp:96
GiNaC::_ex24
const ex _ex24
Definition: utils.cpp:253
assertion.h
Assertion macro definition.
GiNaC::partition_with_zero_parts_generator::current_updated
bool current_updated
Definition: utils.h:331
GiNaC::_num10_p
const numeric * _num10_p
Definition: utils.cpp:228
GiNaC::_ex0
const ex _ex0
Definition: utils.cpp:177
GiNaC::compare_pointers
int compare_pointers(const T *a, const T *b)
Compare two pointers (just to establish some sort of canonical order).
Definition: utils.h:56
GiNaC::swap
void swap(ex &e1, ex &e2)
Definition: ex.h:823
GiNaC::_ex1_3
const ex _ex1_3
Definition: utils.cpp:185
GiNaC::_ex_1_4
const ex _ex_1_4
Definition: utils.cpp:172
GiNaC::_ex5
const ex _ex5
Definition: utils.cpp:209
GiNaC::_num_6_p
const numeric * _num_6_p
Definition: utils.cpp:139
GiNaC::_num5_p
const numeric * _num5_p
Definition: utils.cpp:208
GiNaC::basic_partition_generator::mpartition2::mpartition2
mpartition2(unsigned n_, unsigned m_)
Definition: utils.h:289
k
vector< int > k
Definition: factor.cpp:1466
GiNaC::_num4_p
const numeric * _num4_p
Definition: utils.cpp:204
GiNaC::_ex_30
const ex _ex_30
Definition: utils.cpp:92
GiNaC::_ex9
const ex _ex9
Definition: utils.cpp:225
GiNaC::partition_generator
Generate all bounded combinatorial partitions of an integer n with exactly m parts (not including zer...
Definition: utils.h:366
GiNaC::dunno
Exception class thrown by functions to signal unimplemented functionality so the expression may just ...
Definition: utils.h:37
GiNaC::partition_with_zero_parts_generator::m
unsigned m
Definition: utils.h:329
GiNaC::_num7_p
const numeric * _num7_p
Definition: utils.cpp:216
GiNaC::_num_5_p
const numeric * _num_5_p
Definition: utils.cpp:143
GiNaC::_ex1
const ex _ex1
Definition: utils.cpp:193
GiNaC::composition_generator::coolmulti::element::value
unsigned value
Definition: utils.h:404
GiNaC::_num_1_3_p
const numeric * _num_1_3_p
Definition: utils.cpp:167
GiNaC::_ex25
const ex _ex25
Definition: utils.cpp:257
GiNaC::_num11_p
const numeric * _num11_p
Definition: utils.cpp:232
GiNaC::_num_15_p
const numeric * _num_15_p
Definition: utils.cpp:111
GiNaC::_num_3_p
const numeric * _num_3_p
Definition: utils.cpp:151
GiNaC::_ex_9
const ex _ex_9
Definition: utils.cpp:128
GiNaC::_num1_4_p
const numeric * _num1_4_p
Definition: utils.cpp:180
GiNaC::_num1_3_p
const numeric * _num1_3_p
Definition: utils.cpp:184
GiNaC::_num30_p
const numeric * _num30_p
Definition: utils.cpp:260
GiNaC::_num_4_p
const numeric * _num_4_p
Definition: utils.cpp:147
GiNaC::_ex_5
const ex _ex_5
Definition: utils.cpp:144
GiNaC
Definition: add.cpp:38
GiNaC::_ex6
const ex _ex6
Definition: utils.cpp:213
GiNaC::_num8_p
const numeric * _num8_p
Definition: utils.cpp:220
GiNaC::basic_partition_generator::mpartition2::m
unsigned m
Definition: utils.h:288
GiNaC::_num_12_p
const numeric * _num_12_p
Definition: utils.cpp:115
GiNaC::_ex_12
const ex _ex_12
Definition: utils.cpp:116
GiNaC::partition_generator::partition
std::vector< unsigned > partition
Definition: utils.h:368
GiNaC::cyclic_permutation
void cyclic_permutation(It first, It last, It new_first, Swap swapit)
Definition: utils.h:244
GiNaC::_ex7
const ex _ex7
Definition: utils.cpp:217
GiNaC::_num120_p
const numeric * _num120_p
Definition: utils.cpp:272
GiNaC::_ex_7
const ex _ex_7
Definition: utils.cpp:136
GiNaC::_num_48_p
const numeric * _num_48_p
Definition: utils.cpp:87
GiNaC::basic_partition_generator::mpartition2::next_partition
bool next_partition()
Definition: utils.h:296
GiNaC::_num48_p
const numeric * _num48_p
Definition: utils.cpp:264
GiNaC::_num_9_p
const numeric * _num_9_p
Definition: utils.cpp:127
last
size_t last
Definition: factor.cpp:1465
GiNaC::_num_2_p
const numeric * _num_2_p
Definition: utils.cpp:155
GiNaC::composition_generator::atend
bool atend
Definition: utils.h:449
GiNaC::_ex_2
const ex _ex_2
Definition: utils.cpp:156
GiNaC::_ex48
const ex _ex48
Definition: utils.cpp:265
GiNaC::_ex_60
const ex _ex_60
Definition: utils.cpp:84
GiNaC::composition_generator::coolmulti::element::next
element * next
Definition: utils.h:405
GiNaC::_num_1_4_p
const numeric * _num_1_4_p
Definition: utils.cpp:171
GiNaC::_ex2
const ex _ex2
Definition: utils.cpp:197
GiNaC::_num_60_p
const numeric * _num_60_p
Definition: utils.cpp:83
GiNaC::_ex4
const ex _ex4
Definition: utils.cpp:205
GiNaC::_ex_10
const ex _ex_10
Definition: utils.cpp:124
GiNaC::_num6_p
const numeric * _num6_p
Definition: utils.cpp:212
GiNaC::partition_with_zero_parts_generator::get
const std::vector< unsigned > & get() const
Definition: utils.h:337
GiNaC::basic_partition_generator::mpartition2::x
std::vector< unsigned > x
Definition: utils.h:286
GiNaC::_num_1_2_p
const numeric * _num_1_2_p
Definition: utils.cpp:163
GiNaC::_num_7_p
const numeric * _num_7_p
Definition: utils.cpp:135
GiNaC::composition_generator::coolmulti::~coolmulti
~coolmulti()
Definition: utils.h:425
GiNaC::_num_30_p
const numeric * _num_30_p
Definition: utils.cpp:91
GiNaC::_num_10_p
const numeric * _num_10_p
Definition: utils.cpp:123
GiNaC::partition_generator::next
bool next()
Definition: utils.h:385
GiNaC::composition_generator::coolmulti::head
element * head
Definition: utils.h:413
GiNaC::composition_generator
Generate all compositions of a partition of an integer n, starting with the compositions which has no...
Definition: utils.h:395
GiNaC::composition_generator::coolmulti::i
element * i
Definition: utils.h:413
GiNaC::_num_11_p
const numeric * _num_11_p
Definition: utils.cpp:119
GiNaC::_ex_4
const ex _ex_4
Definition: utils.cpp:148
GiNaC::_ex8
const ex _ex8
Definition: utils.cpp:221
GiNaC::composition_generator::cmgen
struct GiNaC::composition_generator::coolmulti cmgen
GiNaC::_ex11
const ex _ex11
Definition: utils.cpp:233
GiNaC::_num_24_p
const numeric * _num_24_p
Definition: utils.cpp:99
GiNaC::composition_generator::get
const std::vector< unsigned > & get() const
Definition: utils.h:460
GiNaC::_ex3
const ex _ex3
Definition: utils.cpp:201
GiNaC::_num_18_p
const numeric * _num_18_p
Definition: utils.cpp:107
GiNaC::partition_generator::partition_generator
partition_generator(unsigned n_, unsigned m_)
Definition: utils.h:371
GiNaC::_ex15
const ex _ex15
Definition: utils.cpp:241
GiNaC::_num1_2_p
const numeric * _num1_2_p
Definition: utils.cpp:188
GiNaC::multinomial_coefficient
const numeric multinomial_coefficient(const std::vector< unsigned > &p)
Compute the multinomial coefficient n!/(p1!*p2!*...*pk!) where n = p1+p2+...+pk, i....
Definition: utils.cpp:60
GiNaC::_num20_p
const numeric * _num20_p
Definition: utils.cpp:248
GiNaC::_ex_24
const ex _ex_24
Definition: utils.cpp:100
GiNaC::composition_generator::current_updated
bool current_updated
Definition: utils.h:452
GiNaC::_ex_120
const ex _ex_120
Definition: utils.cpp:80
GiNaC::_ex1_4
const ex _ex1_4
Definition: utils.cpp:181
GiNaC::_ex_48
const ex _ex_48
Definition: utils.cpp:88
GiNaC::rotate_left
unsigned rotate_left(unsigned n)
Rotate bits of unsigned value by one bit to the left.
Definition: utils.h:48
GiNaC::partition_with_zero_parts_generator::partition
std::vector< unsigned > partition
Definition: utils.h:330
GiNaC::_num_1_p
const numeric * _num_1_p
Definition: utils.cpp:159
GiNaC::basic_partition_generator::mpartition2
Definition: utils.h:284
GiNaC::_num18_p
const numeric * _num18_p
Definition: utils.cpp:244
GiNaC::permutation_sign
int permutation_sign(It first, It last)
Definition: utils.h:77
GiNaC::_ex20
const ex _ex20
Definition: utils.cpp:249
GiNaC::shaker_sort
void shaker_sort(It first, It last, Cmp comp, Swap swapit)
Definition: utils.h:193
GiNaC::_ex_8
const ex _ex_8
Definition: utils.cpp:132
GiNaC::_ex_20
const ex _ex_20
Definition: utils.cpp:104
GiNaC::_num_25_p
const numeric * _num_25_p
Definition: utils.cpp:95
GiNaC::_ex1_2
const ex _ex1_2
Definition: utils.cpp:189
GiNaC::_ex12
const ex _ex12
Definition: utils.cpp:237
GiNaC::partition_generator::get
const std::vector< unsigned > & get() const
Definition: utils.h:375
n
size_t n
Definition: factor.cpp:1463
GiNaC::_ex_15
const ex _ex_15
Definition: utils.cpp:112
GiNaC::_num12_p
const numeric * _num12_p
Definition: utils.cpp:236
GiNaC::_ex_6
const ex _ex_6
Definition: utils.cpp:140
GiNaC::_num_20_p
const numeric * _num_20_p
Definition: utils.cpp:103
GiNaC::partition_with_zero_parts_generator::partition_with_zero_parts_generator
partition_with_zero_parts_generator(unsigned n_, unsigned m_)
Definition: utils.h:333
GiNaC::_num_120_p
const numeric * _num_120_p
Definition: utils.cpp:79
GiNaC::_num15_p
const numeric * _num15_p
Definition: utils.cpp:240
GiNaC::basic_partition_generator::mpgen
mpartition2 mpgen
Definition: utils.h:318
GiNaC::_num0_p
const numeric * _num0_p
Definition: utils.cpp:175
GiNaC::_ex60
const ex _ex60
Definition: utils.cpp:269
GiNaC::_ex_1_3
const ex _ex_1_3
Definition: utils.cpp:168
std::swap
void swap(GiNaC::ex &a, GiNaC::ex &b)
Specialization of std::swap() for ex objects.
Definition: ex.h:976
GiNaC::composition_generator::coolmulti::element::~element
~element()
Definition: utils.h:408
GiNaC::log2
unsigned log2(unsigned n)
Integer binary logarithm.
Definition: utils.cpp:48
GiNaC::_num_8_p
const numeric * _num_8_p
Definition: utils.cpp:131
GiNaC::composition_generator::next
bool next()
Definition: utils.h:474
GiNaC::composition_generator::coolmulti
Definition: utils.h:401
GiNaC::composition_generator::composition
std::vector< unsigned > composition
Definition: utils.h:451
GiNaC::_num1_p
const numeric * _num1_p
Definition: utils.cpp:192
GiNaC::composition_generator::coolmulti::next_permutation
void next_permutation()
Definition: utils.h:429
GiNaC::_ex_18
const ex _ex_18
Definition: utils.cpp:108
GiNaC::_num9_p
const numeric * _num9_p
Definition: utils.cpp:224
GiNaC::basic_partition_generator::basic_partition_generator
basic_partition_generator(unsigned n_, unsigned m_)
Definition: utils.h:319
GiNaC::_ex_1_2
const ex _ex_1_2
Definition: utils.cpp:164
GiNaC::partition_with_zero_parts_generator
Generate all bounded combinatorial partitions of an integer n with exactly m parts (including zero pa...
Definition: utils.h:327
GiNaC::_num60_p
const numeric * _num60_p
Definition: utils.cpp:268
GiNaC::_num24_p
const numeric * _num24_p
Definition: utils.cpp:252
GiNaC::_num25_p
const numeric * _num25_p
Definition: utils.cpp:256
GiNaC::_ex_1
const ex _ex_1
Definition: utils.cpp:160
GiNaC::composition_generator::coolmulti::after_i
element * after_i
Definition: utils.h:413
GiNaC::_ex_11
const ex _ex_11
Definition: utils.cpp:120
GiNaC::_ex18
const ex _ex18
Definition: utils.cpp:245
GiNaC::composition_generator::coolmulti::element
Definition: utils.h:403
GiNaC::_num2_p
const numeric * _num2_p
Definition: utils.cpp:196
GiNaC::_num0_bp
const basic * _num0_bp
Definition: utils.cpp:176
GiNaC::basic_partition_generator
Base class for generating all bounded combinatorial partitions of an integer n with exactly m parts i...
Definition: utils.h:278

This page is part of the GiNaC developer's reference. It was generated automatically by doxygen. For an introduction, see the tutorial.