Cadabra
Computer algebra system for field theory problems
Loading...
Searching...
No Matches
YoungTab.hh
Go to the documentation of this file.
1/*
2
3Cadabra: a field-theory motivated computer algebra system.
4Copyright (C) 2001-2011 Kasper Peeters <kasper.peeters@aei.mpg.de>
5
6 This program is free software: you can redistribute it and/or
7modify it under the terms of the GNU General Public License as
8published by the Free Software Foundation, either version 3 of the
9License, or (at your option) any later version.
10
11 This program is distributed in the hope that it will be useful,
12 but WITHOUT ANY WARRANTY; without even the implied warranty of
13MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
14General Public License for more details.
15
16 You should have received a copy of the GNU General Public License
17 along with this program. If not, see <http://www.gnu.org/licenses/>.
18
19*/
20
21/*
22- TODO: has_nullifying trace is wrong, but needs to be merged with the
23 input_asym code in order to be more useful.
24
25*/
26
27#pragma once
28
29#include <cstddef>
30#include <iostream>
31#include <iterator>
32#include <vector>
33#include <list>
34#include <gmpxx.h>
35#include "Combinatorics.hh"
36#include <cstddef>
37
38typedef mpz_class yngint_t;
39typedef mpq_class yngrat_t;
40
42namespace yngtab {
43
44 // The tableau_base is the abstract interface; does not depend on the
45 // actual storage format.
46
48 public:
50 virtual ~tableau_base();
51 virtual unsigned int number_of_rows() const=0;
52 virtual unsigned int row_size(unsigned int row) const=0;
53 virtual unsigned int column_size(unsigned int col) const; // FIXME: maybe make pure virt too
54 virtual void add_box(unsigned int row)=0;
55 virtual void remove_box(unsigned int row)=0;
56 virtual void add_row(unsigned int row_size);
57 virtual void clear()=0;
58
59 yngrat_t multiplicity; // also keeps track of signs
60 int selfdual_column; // -n, 0, n for antiselfdual, no, selfdual (count from 1)
61 yngint_t dimension(unsigned int) const;
62 unsigned long hook_length(unsigned int row, unsigned int col) const;
64 };
65
66 class tableau : public tableau_base {
67 public:
68 virtual ~tableau();
69 virtual unsigned int number_of_rows() const;
70 virtual unsigned int row_size(unsigned int row) const;
71 virtual void add_box(unsigned int row);
72 virtual void remove_box(unsigned int row);
73 virtual void clear();
74
75 tableau& operator=(const tableau&);
76 private:
77 std::vector<int> rows;
78 };
79
80 template<class T>
81 class tableaux;
82
83 template<class T>
84 class filled_tableau : public tableau {
85 public:
86 typedef T value_type;
87
88 virtual ~filled_tableau();
89 virtual unsigned int number_of_rows() const;
90 virtual unsigned int row_size(unsigned int row) const;
91 virtual void add_box(unsigned int row);
92 virtual void remove_box(unsigned int row);
93 std::pair<int, int> find(const T&) const;
94 virtual void clear();
95
96 void copy_shape(const tableau&);
97
98 T& operator()(unsigned int row, unsigned int col);
99 const T& operator()(unsigned int row, unsigned int col) const;
100 const T& operator[](unsigned int boxnum) const;
101 void add_box(unsigned int rownum, T val);
102 void swap_columns(unsigned int c1, unsigned int c2);
103
110 std::pair<int, int> nonstandard_loc() const;
111 template<class StrictWeakOrdering> void sort_within_columns(StrictWeakOrdering comp);
112 template<class StrictWeakOrdering> void sort_columns(StrictWeakOrdering comp);
113 template<class StrictWeakOrdering> void canonicalise(StrictWeakOrdering comp, bool only_col_ex=false);
114 void projector(combin::symmetriser<T>&, bool modulo_monoterm=false) const;
117
119
121 public:
122 typedef T value_type;
123 typedef T* pointer;
124 typedef T& reference;
125 typedef size_t size_type;
126 typedef ptrdiff_t difference_type;
127 typedef std::random_access_iterator_tag iterator_category;
128 };
129
131 public:
132 typedef T value_type;
133 typedef const T* pointer;
134 typedef const T& reference;
135 typedef size_t size_type;
136 typedef ptrdiff_t difference_type;
137 typedef std::random_access_iterator_tag iterator_category;
138 };
139
140 class const_iterator;
141 class in_column_iterator;
143 class in_row_iterator;
145
148 public:
149 in_column_iterator(unsigned int r, unsigned int c, filled_tableau<T> *);
150 T& operator*() const;
151 T* operator->() const;
152 in_column_iterator& operator++();
153 in_column_iterator operator++(int);
154 in_column_iterator& operator--();
155 in_column_iterator operator--(int);
156 in_column_iterator operator+(unsigned int);
157 in_column_iterator operator-(unsigned int);
158 in_column_iterator& operator+=(unsigned int);
159 in_column_iterator& operator-=(unsigned int);
160 T& operator[](int n) const;
161 bool operator<(const in_column_iterator& other) const;
162 bool operator>(const in_column_iterator& other) const;
163 bool operator<=(const in_column_iterator& other) const;
164 bool operator>=(const in_column_iterator& other) const;
165 ptrdiff_t operator-(const in_column_iterator&) const;
166 bool operator==(const in_column_iterator&) const;
167 bool operator!=(const in_column_iterator&) const;
168
169 friend class filled_tableau<T>;
171 private:
174 };
175
178 public:
179 in_column_const_iterator(unsigned int r, unsigned int c, const filled_tableau<T>*);
181 const T& operator*() const;
182 const T* operator->() const;
183 in_column_const_iterator& operator++();
184 in_column_const_iterator operator++(int);
185 in_column_const_iterator& operator--();
186 in_column_const_iterator operator--(int);
187 in_column_const_iterator operator+(unsigned int);
188 in_column_const_iterator operator-(unsigned int);
189 in_column_const_iterator& operator+=(unsigned int);
190 in_column_const_iterator& operator-=(unsigned int);
191 bool operator<(const in_column_const_iterator& other) const;
192 bool operator>(const in_column_const_iterator& other) const;
193 bool operator<=(const in_column_const_iterator& other) const;
194 bool operator>=(const in_column_const_iterator& other) const;
195 ptrdiff_t operator-(const in_column_const_iterator&) const;
196 bool operator==(const in_column_const_iterator&) const;
197 bool operator!=(const in_column_const_iterator&) const;
198
199 friend class filled_tableau<T>;
200 private:
202 unsigned int column_number, row_number;
203 };
204
207 public:
208 in_row_iterator(unsigned int r, unsigned int c, filled_tableau<T>*);
209 T& operator*() const;
210 T* operator->() const;
211 in_row_iterator& operator++();
212 in_row_iterator operator++(int);
213 in_row_iterator& operator--();
214 in_row_iterator operator--(int);
215 in_row_iterator operator+(unsigned int);
216 in_row_iterator operator-(unsigned int);
217 in_row_iterator& operator+=(unsigned int);
218 in_row_iterator& operator-=(unsigned int);
219 bool operator<(const in_row_iterator& other) const;
220 bool operator>(const in_row_iterator& other) const;
221 bool operator<=(const in_row_iterator& other) const;
222 bool operator>=(const in_row_iterator& other) const;
223 ptrdiff_t operator-(const in_row_iterator&) const;
224 bool operator==(const in_row_iterator&) const;
225 bool operator!=(const in_row_iterator&) const;
226
227 friend class filled_tableau<T>;
229 private:
231 unsigned int column_number, row_number;
232 };
233
235 public:
236 in_row_const_iterator(unsigned int r, unsigned int c, const filled_tableau<T>*);
238 const T& operator*() const;
239 const T* operator->() const;
240 in_row_const_iterator& operator++();
241 in_row_const_iterator operator++(int);
242 in_row_const_iterator& operator--();
243 in_row_const_iterator operator--(int);
244 in_row_const_iterator operator+(unsigned int);
245 in_row_const_iterator operator-(unsigned int);
246 in_row_const_iterator& operator+=(unsigned int);
247 in_row_const_iterator& operator-=(unsigned int);
248 bool operator<(const in_row_const_iterator& other) const;
249 bool operator>(const in_row_const_iterator& other) const;
250 bool operator<=(const in_row_const_iterator& other) const;
251 bool operator>=(const in_row_const_iterator& other) const;
252 ptrdiff_t operator-(const in_row_const_iterator&) const;
253 bool operator==(const in_row_const_iterator&) const;
254 bool operator!=(const in_row_const_iterator&) const;
255
256 friend class filled_tableau<T>;
257 private:
259 unsigned int column_number, row_number;
260 };
261
263 class iterator : public iterator_base {
264 public:
265 iterator(unsigned int r, unsigned int c, filled_tableau<T> *);
266 T& operator*() const;
267 T* operator->() const;
268 iterator& operator++();
269 iterator operator++(int);
270 iterator& operator--();
271 iterator operator--(int);
272 iterator operator+(unsigned int);
273 iterator operator-(unsigned int);
274 iterator& operator+=(unsigned int);
275 iterator& operator-=(unsigned int);
276 bool operator<(const iterator& other) const;
277 bool operator>(const iterator& other) const;
278 ptrdiff_t operator-(const iterator&) const;
279 bool operator==(const iterator&) const;
280 bool operator!=(const iterator&) const;
281
282 friend class filled_tableau<T>;
284 private:
286 unsigned int column_number, row_number;
287 };
288
290 public:
291 const_iterator(unsigned int r, unsigned int c, const filled_tableau<T>*);
293 const T& operator*() const;
294 const T* operator->() const;
295 const_iterator& operator++();
296 const_iterator operator++(int);
297 const_iterator& operator--();
298 const_iterator operator--(int);
299 const_iterator operator+(unsigned int);
300 const_iterator operator-(unsigned int);
301 const_iterator& operator+=(unsigned int);
302 const_iterator& operator-=(unsigned int);
303 bool operator<(const const_iterator& other) const;
304 bool operator>(const const_iterator& other) const;
305 ptrdiff_t operator-(const const_iterator&) const;
306 bool operator==(const const_iterator&) const;
307 bool operator!=(const const_iterator&) const;
308
309 friend class filled_tableau<T>;
310 private:
312 unsigned int column_number, row_number;
313 };
314
315
316 in_column_iterator begin_column(unsigned int column_number);
317 in_column_iterator end_column(unsigned int column_number);
318 in_column_const_iterator begin_column(unsigned int column_number) const;
319 in_column_const_iterator end_column(unsigned int column_number) const;
320 in_column_const_iterator cbegin_column(unsigned int column_number) const;
321 in_column_const_iterator cend_column(unsigned int column_number) const;
322 in_row_iterator begin_row(unsigned int row_number);
323 in_row_iterator end_row(unsigned int row_number);
324 in_row_const_iterator begin_row(unsigned int row_number) const;
325 in_row_const_iterator end_row(unsigned int row_number) const;
326 in_row_const_iterator cbegin_row(unsigned int row_number) const;
327 in_row_const_iterator cend_row(unsigned int row_number) const;
328 iterator begin();
329 iterator end();
330 const_iterator begin() const;
331 const_iterator end() const;
332 const_iterator cbegin() const;
333 const_iterator cend() const;
334
335 template<class OutputIterator>
336 OutputIterator Garnir_set(OutputIterator, unsigned int, unsigned int) const;
337 private:
338 typedef std::vector<T> box_row;
339 typedef std::vector<box_row> row_stack;
341 };
342
343 template<class T>
344 class tableaux {
345 public:
346 yngint_t total_dimension(unsigned int dim);
347 void remove_nullifying_traces();
350 bool standard_form();
351 void add_tableau(const T&);
352 void symmetrise(const T& tabsym);
353
354 typedef std::list<T> tableau_container_t;
356
357 typedef std::back_insert_iterator<tableau_container_t> back_insert_iterator;
358
359 back_insert_iterator get_back_insert_iterator();
360 };
361
362 bool legal_box(const std::vector<std::pair<int,int> >& prev,
363 const std::vector<std::pair<int,int> >& ths,
364 int colpos, int trypos);
365
366 // --------------------------------------
367
368
369 template<class T>
374
375 template<class T>
377 {
378 typename tableau_container_t::iterator it=storage.begin();
379 while(it!=storage.end()) {
380 if(it->has_nullifying_trace())
381 it=storage.erase(it);
382 else ++it;
383 }
384 }
385
386 template<class T>
388 {
389 //
390 // typename tableau_container_t::iterator thetab=storage.begin();
391 // while(thetab!=storage.end()) {
392 // (*thetab).sort_columns();
393 // std::pair<int,int> where=(*thetab).nonstandard_loc();
394 // if(where.first!=-1) {
395 // combinations<typename T::value_type> com;
396 //
397
398 /*
399 FIXME: we should have two LR_tensor routines, because if you do 'alltabs', you should
400 keep track of which boxes came from tableau 2. So do a LR_tensor with numbered boxes,
401 and then after the LR_tensor apply the symmetries of the original tableaux, put back
402 the original index names, sort columns and determine whether the tableau is identically
403 non-zero. Then add to the product.
404
405 Another issue: adding to tableaux should have an option to not insert doubles.
406
407 There was something third, forgotten...
408 */
409 }
410
411 template<class T>
413 {
414 rows.clear();
415 for(unsigned int r=0; r<other.number_of_rows(); ++r) {
416 rows.push_back(box_row(other.row_size(r)));
417 }
418 tableau::operator=(other);
419 }
420
421 template<class T>
423 {
424 return (rows==other.rows);
425 }
426
427 template<class T>
429 {
430 return false;
431
432 // Old, probably incorrect code:
433 //
434 // for(unsigned int r1=0; r1<number_of_rows(); ++r1) {
435 // for(unsigned c1=0; c1<row_size(r1); ++c1) {
436 // for(unsigned int c2=c1+1; c2<row_size(r1); ++c2) {
437 // // (r1,c1) and (r1,c2)
438 // for(unsigned int c3=0; c3<row_size(0); ++c3) {
439 // unsigned int r3=0;
440 // while(r3<number_of_rows()-1 && c3<row_size(r3)) {
441 // unsigned int r4=r3+1;
442 // while(r4<number_of_rows() && c3<row_size(r4)) {
443 // if((rows[r1][c1]==rows[r3][c3] && rows[r1][c2]==rows[r4][c3]) ||
444 // (rows[r1][c1]==rows[r4][c3] && rows[r1][c2]==rows[r3][c3]) )
445 // return true;
446 // ++r4;
447 // }
448 // ++r3;
449 // }
450 // }
451 // }
452 // }
453 // }
454 // return false;
455 }
456
457 template<class T>
458 std::pair<int, int> filled_tableau<T>::find(const T& obj) const
459 {
460 for(unsigned int ir=0; ir<rows.size(); ++ir) {
461 for(unsigned int ic=0; ic<rows[ir].size(); ++ic) {
462 if(rows[ir][ic]==obj)
463 return std::pair<int,int>(ir, ic);
464 }
465 }
466 return std::pair<int,int>(-1,-1);
467 }
468
469 template<class T>
471 {
472 std::less<T> comp;
473 sort_within_columns(comp);
474 }
475
476 template<class T>
478 {
479 std::less<T> comp;
480 sort_columns(comp);
481 }
482
483 template<class T>
485 {
486 std::less<T> comp;
487 canonicalise(comp);
488 }
489
490 template<class T>
491 template<class StrictWeakOrdering>
492 void filled_tableau<T>::sort_within_columns(StrictWeakOrdering comp)
493 {
494 filled_tableau<T> tmp(*this);
495 if(number_of_rows()==0) return;
496 for(unsigned int c=0; c<row_size(0); ++c) {
497 std::sort(begin_column(c), end_column(c), comp);
498 multiplicity*=combin::ordersign(begin_column(c), end_column(c), tmp.begin_column(c), tmp.end_column(c));
499 }
500 }
501
502 template<class T>
503 template<class StrictWeakOrdering>
504 void filled_tableau<T>::sort_columns(StrictWeakOrdering comp)
505 {
506 for(unsigned int c1=0; c1<row_size(0); ++c1) {
507 for(unsigned int c2=c1; c2<row_size(0); ++c2) {
508 if(column_size(c1)==column_size(c2)) {
509 if(comp((*this)(0,c2), (*this)(0,c1)))
510 swap_columns(c1,c2);
511 }
512 }
513 }
514 }
515
516 template<class T>
517 template<class StrictWeakOrdering>
518 void filled_tableau<T>::canonicalise(StrictWeakOrdering comp, bool only_col_ex)
519 {
520 if(!only_col_ex)
521 sort_within_columns(comp);
522 sort_columns(comp);
523 }
524
525 //---------------------------------------------------------------------------
526 // in_column_iterator
527
528 template<class T>
530 : tab(t), column_number(c), row_number(r)
531 {
532 }
533
534 template<class T>
536 {
537 typename filled_tableau<T>::in_column_iterator it2(*this);
538 it2+=n;
539 return it2;
540 }
541
542 template<class T>
544 {
545 typename filled_tableau<T>::in_column_iterator it2(*this);
546 it2-=n;
547 return it2;
548 }
549
550 template<class T>
552 {
553 return row_number-other.row_number;
554 }
555
556 template<class T>
558 {
559 return (*tab)(row_number + n, column_number);
560 }
561
562 template<class T>
564 {
565 return (*tab)(row_number,column_number);
566 }
567
568 template<class T>
570 {
571 return &((*tab)(row_number,column_number));
572 }
573
574 template<class T>
576 {
577 ++row_number;
578 return (*this);
579 }
580
581 template<class T>
583 {
584 row_number+=n;
585 return (*this);
586 }
587
588 template<class T>
590 {
591 --row_number;
592 return (*this);
593 }
594
595 template<class T>
597 {
598 in_column_iterator tmp(*this);
599 --row_number;
600 return tmp;
601 }
602
603 template<class T>
605 {
606 in_column_iterator tmp(*this);
607 ++row_number;
608 return tmp;
609 }
610
611 template<class T>
613 {
614 row_number-=n;
615 return (*this);
616 }
617
618 template<class T>
620 {
621 if(tab==other.tab && row_number==other.row_number && column_number==other.column_number)
622 return true;
623 return false;
624 }
625
626 template<class T>
628 {
629 if(row_number<=other.row_number) return true;
630 return false;
631 }
632
633 template<class T>
635 {
636 if(row_number>=other.row_number) return true;
637 return false;
638 }
639
640 template<class T>
642 {
643 if(row_number<other.row_number) return true;
644 return false;
645 }
646
647 template<class T>
649 {
650 if(row_number>other.row_number) return true;
651 return false;
652 }
653
654 template<class T>
656 {
657 return !((*this)==other);
658 }
659
660 //---------------------------------------------------------------------------
661// in_column_const_iterator
662
663 template<class T>
665 : tab(t), column_number(c), row_number(r)
666 {
667 }
668
669 template<class T>
671 : tab(other.tab), column_number(other.column_number), row_number(other.row_number)
672 {
673 }
674
675 template<class T>
677 {
679 it2 += n;
680 return it2;
681 }
682
683 template<class T>
685 {
687 it2 -= n;
688 return it2;
689 }
690
691 template<class T>
693 {
694 return row_number - other.row_number;
695 }
696
697 template<class T>
699 {
700 return (*tab)(row_number, column_number);
701 }
702
703 template<class T>
705 {
706 return &((*tab)(row_number, column_number));
707 }
708
709 template<class T>
715
716 template<class T>
718 {
719 row_number += n;
720 return (*this);
721 }
722
723 template<class T>
729
730 template<class T>
737
738 template<class T>
745
746 template<class T>
748 {
749 row_number -= n;
750 return (*this);
751 }
752
753 template<class T>
755 {
756 if (tab == other.tab && row_number == other.row_number && column_number == other.column_number)
757 return true;
758 return false;
759 }
760
761 template<class T>
763 {
764 if (row_number <= other.row_number) return true;
765 return false;
766 }
767
768 template<class T>
770 {
771 if (row_number >= other.row_number) return true;
772 return false;
773 }
774
775 template<class T>
777 {
778 if (row_number < other.row_number) return true;
779 return false;
780 }
781
782 template<class T>
784 {
785 if (row_number > other.row_number) return true;
786 return false;
787 }
788
789 template<class T>
791 {
792 return !((*this) == other);
793 }
794
795
796 //---------------------------------------------------------------------------
797 // in_row_iterator
798
799 template<class T>
801 : tab(t), column_number(c), row_number(r)
802 {
803 }
804
805 template<class T>
807 {
808 typename filled_tableau<T>::in_row_iterator it2(*this);
809 it2 += n;
810 return it2;
811 }
812
813 template<class T>
815 {
816 typename filled_tableau<T>::in_row_iterator it2(*this);
817 it2 -= n;
818 return it2;
819 }
820
821 template<class T>
823 {
824 return column_number - other.column_number;
825 }
826
827 template<class T>
829 {
830 return (*tab)(row_number, column_number);
831 }
832
833 template<class T>
835 {
836 return &((*tab)(row_number, column_number));
837 }
838
839 template<class T>
841 {
842 ++column_number;
843 return (*this);
844 }
845
846 template<class T>
848 {
849 column_number += n;
850 return (*this);
851 }
852
853 template<class T>
855 {
856 --column_number;
857 return (*this);
858 }
859
860 template<class T>
862 {
863 in_row_iterator tmp(*this);
864 --column_number;
865 return tmp;
866 }
867
868 template<class T>
870 {
871 in_row_iterator tmp(*this);
872 ++column_number;
873 return tmp;
874 }
875
876 template<class T>
878 {
879 column_number -= n;
880 return (*this);
881 }
882
883 template<class T>
885 {
886 if (tab == other.tab && row_number == other.row_number && column_number == other.column_number)
887 return true;
888 return false;
889 }
890
891 template<class T>
893 {
894 if (column_number <= other.column_number) return true;
895 return false;
896 }
897
898 template<class T>
900 {
901 if (column_number >= other.column_number) return true;
902 return false;
903 }
904
905 template<class T>
907 {
908 if (column_number < other.column_number) return true;
909 return false;
910 }
911
912 template<class T>
914 {
915 if (column_number > other.column_number) return true;
916 return false;
917 }
918
919 template<class T>
921 {
922 return !((*this) == other);
923 }
924
925 //---------------------------------------------------------------------------
926// in_row_const_iterator
927
928 template<class T>
930 : tab(t), column_number(c), row_number(r)
931 {
932 }
933
934 template<class T>
936 : tab(other.tab), column_number(other.column_number), row_number(other.row_number)
937 {
938 }
939
940
941 template<class T>
943 {
945 it2 += n;
946 return it2;
947 }
948
949 template<class T>
951 {
953 it2 -= n;
954 return it2;
955 }
956
957 template<class T>
959 {
960 return column_number - other.column_number;
961 }
962
963 template<class T>
965 {
966 return (*tab)(row_number, column_number);
967 }
968
969 template<class T>
971 {
972 return &((*tab)(row_number, column_number));
973 }
974
975 template<class T>
977 {
978 ++column_number;
979 return (*this);
980 }
981
982 template<class T>
984 {
985 column_number += n;
986 return (*this);
987 }
988
989 template<class T>
991 {
992 --column_number;
993 return (*this);
994 }
995
996 template<class T>
998 {
999 in_row_const_iterator tmp(*this);
1000 --column_number;
1001 return tmp;
1002 }
1003
1004 template<class T>
1006 {
1007 in_row_const_iterator tmp(*this);
1008 ++column_number;
1009 return tmp;
1010 }
1011
1012 template<class T>
1014 {
1015 column_number -= n;
1016 return (*this);
1017 }
1018
1019 template<class T>
1021 {
1022 if (tab == other.tab && row_number == other.row_number && column_number == other.column_number)
1023 return true;
1024 return false;
1025 }
1026
1027 template<class T>
1029 {
1030 if (column_number <= other.column_number) return true;
1031 return false;
1032 }
1033
1034 template<class T>
1036 {
1037 if (column_number >= other.column_number) return true;
1038 return false;
1039 }
1040
1041 template<class T>
1043 {
1044 if (column_number < other.column_number) return true;
1045 return false;
1046 }
1047
1048 template<class T>
1050 {
1051 if (column_number > other.column_number) return true;
1052 return false;
1053 }
1054
1055 template<class T>
1057 {
1058 return !((*this) == other);
1059 }
1060
1061
1062
1063 //---------------------------------------------------------------------------
1064 // iterator
1065
1066 template<class T>
1068 : tab(t), column_number(c), row_number(r)
1069 {
1070 }
1071
1072 template<class T>
1074 {
1075 typename filled_tableau<T>::iterator it2(*this);
1076 it2+=n;
1077 return it2;
1078 }
1079
1080 template<class T>
1082 {
1083 typename filled_tableau<T>::iterator it2(*this);
1084 it2-=n;
1085 return it2;
1086 }
1087
1088 template<class T>
1090 {
1091 return row_number-other.row_number;
1092 }
1093
1094 template<class T>
1096 {
1097 return (*tab)(row_number,column_number);
1098 }
1099
1100 template<class T>
1102 {
1103 return &((*tab)(row_number,column_number));
1104 }
1105
1106 template<class T>
1108 {
1109 if(++column_number==tab->rows[row_number].size()) {
1110 column_number=0;
1111 ++row_number;
1112 }
1113 return (*this);
1114 }
1115
1116 template<class T>
1118 {
1119 while(n>0) {
1120 if(++column_number==tab->rows[row_number]) {
1121 column_number=0;
1122 ++row_number;
1123 }
1124 --n;
1125 }
1126 return (*this);
1127 }
1128
1129 template<class T>
1131 {
1132 if(column_number==0) {
1133 --row_number;
1134 column_number=tab->rows[row_number].size()-1;
1135 }
1136 else --column_number;
1137 return (*this);
1138 }
1139
1140 template<class T>
1142 {
1143 iterator tmp(*this);
1144 if(column_number==0) {
1145 --row_number;
1146 column_number=tab->rows[row_number].size()-1;
1147 }
1148 else --column_number;
1149 return tmp;
1150 }
1151
1152 template<class T>
1154 {
1155 iterator tmp(*this);
1156 while(this->n>0) {
1157 if(++column_number==tab->rows[row_number]) {
1158 column_number=0;
1159 ++row_number;
1160 }
1161 --this->n;
1162 }
1163 return tmp;
1164 }
1165
1166 template<class T>
1168 {
1169 while(n>0) {
1170 if(column_number==0) {
1171 --row_number;
1172 column_number=tab->rows[row_number].size()-1;
1173 }
1174 else --column_number;
1175 --n;
1176 }
1177 return (*this);
1178 }
1179
1180 template<class T>
1182 {
1183 if(tab==other.tab && row_number==other.row_number && column_number==other.column_number)
1184 return true;
1185 return false;
1186 }
1187
1188 template<class T>
1190 {
1191 if(row_number<other.row_number) return true;
1192 return false;
1193 }
1194
1195 template<class T>
1197 {
1198 if(row_number>other.row_number) return true;
1199 return false;
1200 }
1201
1202 template<class T>
1204 {
1205 return !((*this)==other);
1206 }
1207
1208
1209
1210 //---------------------------------------------------------------------------
1211 // const_iterator
1212
1213 template<class T>
1215 : tab(t), column_number(c), row_number(r)
1216 {
1217 }
1218
1219 template<class T>
1221 : tab(other.tab), column_number(other.column_number), row_number(other.row_number)
1222 {
1223 }
1224
1225 template<class T>
1227 {
1228 typename filled_tableau<T>::const_iterator it2(*this);
1229 it2 += n;
1230 return it2;
1231 }
1232
1233 template<class T>
1235 {
1236 typename filled_tableau<T>::const_iterator it2(*this);
1237 it2 -= n;
1238 return it2;
1239 }
1240
1241 template<class T>
1243 {
1244 return row_number - other.row_number;
1245 }
1246
1247 template<class T>
1249 {
1250 return (*tab)(row_number, column_number);
1251 }
1252
1253 template<class T>
1255 {
1256 return &((*tab)(row_number, column_number));
1257 }
1258
1259 template<class T>
1261 {
1262 if (++column_number == tab->rows[row_number].size()) {
1263 column_number = 0;
1264 ++row_number;
1265 }
1266 return (*this);
1267 }
1268
1269 template<class T>
1271 {
1272 while (n > 0) {
1273 if (++column_number == tab->rows[row_number]) {
1274 column_number = 0;
1275 ++row_number;
1276 }
1277 --n;
1278 }
1279 return (*this);
1280 }
1281
1282 template<class T>
1284 {
1285 if (column_number == 0) {
1286 --row_number;
1287 column_number = tab->rows[row_number].size() - 1;
1288 }
1289 else --column_number;
1290 return (*this);
1291 }
1292
1293 template<class T>
1295 {
1296 const_iterator tmp(*this);
1297 if (column_number == 0) {
1298 --row_number;
1299 column_number = tab->rows[row_number].size() - 1;
1300 }
1301 else --column_number;
1302 return tmp;
1303 }
1304
1305 template<class T>
1307 {
1308 const_iterator tmp(*this);
1309 while (this->n > 0) {
1310 if (++column_number == tab->rows[row_number]) {
1311 column_number = 0;
1312 ++row_number;
1313 }
1314 --this->n;
1315 }
1316 return tmp;
1317 }
1318
1319 template<class T>
1321 {
1322 while (n > 0) {
1323 if (column_number == 0) {
1324 --row_number;
1325 column_number = tab->rows[row_number].size() - 1;
1326 }
1327 else --column_number;
1328 --n;
1329 }
1330 return (*this);
1331 }
1332
1333 template<class T>
1335 {
1336 if (tab == other.tab && row_number == other.row_number && column_number == other.column_number)
1337 return true;
1338 return false;
1339 }
1340
1341 template<class T>
1343 {
1344 if (row_number < other.row_number) return true;
1345 return false;
1346 }
1347
1348 template<class T>
1350 {
1351 if (row_number > other.row_number) return true;
1352 return false;
1353 }
1354
1355 template<class T>
1357 {
1358 return !((*this) == other);
1359 }
1360
1361
1362 //---
1363 // other
1364
1365 template<class T>
1367 {
1368 return iterator(0, 0, this);
1369 }
1370
1371 template<class T>
1373 {
1374 return iterator(rows.size(), 0, this);
1375 }
1376
1377
1378 template<class T>
1380 {
1381 return const_iterator(0,0,this);
1382 }
1383
1384 template<class T>
1386 {
1387 return const_iterator(rows.size(), 0, this);
1388 }
1389
1390 template<class T>
1392 {
1393 return cbegin();
1394 }
1395
1396 template<class T>
1398 {
1399 return cend();
1400 }
1401
1402 template<class T>
1404 {
1405 typename filled_tableau<T>::in_column_iterator it(0,column,this);
1406 assert(number_of_rows()>0);
1407 assert(column<row_size(0));
1408 return it;
1409 }
1410
1411 template<class T>
1413 {
1414 unsigned int r=0;
1415 while(r<number_of_rows()) {
1416 if(row_size(r)<=column)
1417 break;
1418 ++r;
1419 }
1420 typename filled_tableau<T>::in_column_iterator it(r,column,this);
1421 return it;
1422 }
1423
1424 template<class T>
1426 {
1427 typename filled_tableau<T>::in_column_const_iterator it(0, column, this);
1428 assert(number_of_rows() > 0);
1429 assert(column < row_size(0));
1430 return it;
1431 }
1432
1433 template<class T>
1435 {
1436 unsigned int r = 0;
1437 while (r < number_of_rows()) {
1438 if (row_size(r) <= column)
1439 break;
1440 ++r;
1441 }
1442 typename filled_tableau<T>::in_column_const_iterator it(r, column, this);
1443 return it;
1444 }
1445
1446 template<class T>
1448 {
1449 return cbegin_column(column);
1450 }
1451
1452 template<class T>
1454 {
1455 return cend_column(column);
1456 }
1457
1458 template<class T>
1460 {
1461 return in_row_iterator{ row, 0, this };
1462 }
1463
1464 template<class T>
1466 {
1467 return in_row_iterator{ row, row_size(row), this };
1468 }
1469
1470 template<class T>
1472 {
1473 return in_row_const_iterator{ row, 0, this };
1474 }
1475
1476 template<class T>
1478 {
1479 return in_row_const_iterator{ row, row_size(row), this };
1480 }
1481
1482 template<class T>
1484 {
1485 return cbegin_row(row);
1486 }
1487
1488 template<class T>
1490 {
1491 return cend_row(row);
1492 }
1493
1494
1495
1496
1497 template<class T>
1498 template<class OutputIterator>
1499 OutputIterator filled_tableau<T>::Garnir_set(OutputIterator it, unsigned int row, unsigned int col) const
1500 {
1501 assert(col>0);
1502 unsigned int r=row, c=col;
1503 *it=(*this)(r,c);
1504 ++it;
1505 while(r>0) {
1506 --r;
1507 *it=(*this)(r,c);
1508 ++it;
1509 }
1510 r=row;
1511 --c;
1512 *it=(*this)(r,c);
1513 ++it;
1514 while(r+1<column_size(c)) {
1515 ++r;
1516 *it=(*this)(r,c);
1517 ++it;
1518 }
1519 return it;
1520 }
1521
1522 template<class T>
1523 std::pair<int, int> filled_tableau<T>::nonstandard_loc() const
1524 {
1525 unsigned int r=number_of_rows();
1526 assert(r>0);
1527 do {
1528 --r;
1529 for(unsigned int c=0; c<row_size(r)-1; ++c) {
1530 if((*this)(r,c) > (*this)(r,c+1) )
1531 return std::pair<int, int>(r,c);
1532 }
1533 }
1534 while(r>0);
1535 return std::pair<int,int>(-1,-1);
1536 }
1537
1538 template<class T>
1540 {
1541 bool already_standard=true;
1542
1543 typename tableau_container_t::iterator thetab=storage.begin();
1544 while(thetab!=storage.end()) {
1545 (*thetab).sort_within_columns();
1546 std::pair<int,int> where=(*thetab).nonstandard_loc();
1547 if(where.first!=-1) {
1548 already_standard=false;
1550 for(unsigned int i1=where.first; i1<(*thetab).column_size(where.second); ++i1)
1551 com.original.push_back((*thetab)(i1,where.second));
1552 for(unsigned int i1=0; i1<=(unsigned int)(where.first); ++i1)
1553 com.original.push_back((*thetab)(i1,where.second+1));
1554 com.sublengths.push_back((*thetab).column_size(where.second)-where.first);
1555 com.sublengths.push_back(where.first+1);
1556 com.permute();
1557 for(unsigned int tabi=1; tabi<com.size(); ++tabi) {
1558 T ntab((*thetab));
1559 unsigned int offset=0;
1560 for(unsigned int i1=where.first; i1<(*thetab).column_size(where.second); ++i1, ++offset)
1561 ntab(i1,where.second)=com[tabi][offset];
1562 for(unsigned int i1=0; i1<=(unsigned int)(where.first); ++i1, ++offset)
1563 ntab(i1,where.second+1)=com[tabi][offset];
1564 ntab.multiplicity*=-1*com.ordersign(tabi);
1565 add_tableau(ntab);
1566 }
1567 thetab=storage.erase(thetab);
1568 }
1569 else ++thetab;
1570 }
1571 return already_standard;
1572 }
1573
1574 template<class T>
1575 void tableaux<T>::add_tableau(const T& ntab)
1576 {
1577 typename tableau_container_t::iterator it=storage.begin();
1578 while(it!=storage.end()) {
1579 if((*it).compare_without_multiplicity(ntab)) {
1580 (*it).multiplicity+=ntab.multiplicity;
1581 if((*it).multiplicity==0)
1582 storage.erase(it);
1583 return;
1584 }
1585 ++it;
1586 }
1587 storage.push_back(ntab);
1588 }
1589
1590
1591 template<class T>
1593 {
1594 yngrat_t norm=1;
1595 norm/=hook_length_prod();
1596 return norm;
1597 }
1598
1599 template<class T>
1600 void filled_tableau<T>::projector(combin::symmetriser<T>& sym, bool modulo_monoterm) const
1601 {
1602 for(unsigned int r=0; r<number_of_rows(); ++r)
1603 for(unsigned int c=0; c<row_size(r); ++c)
1604 sym.original.push_back(rows[r][c]);
1605
1606 unsigned int offset=0;
1607 // symmetrise over boxes in rows
1608 for(unsigned int r=0; r<number_of_rows(); ++r) {
1609 sym.permutation_sign=1;
1610 sym.permute_blocks.clear();
1611 sym.block_length=1;
1612 sym.input_asym.clear();
1613 for(unsigned int c=0; c<row_size(r); ++c)
1614 sym.permute_blocks.push_back(offset++);
1615 sym.apply_symmetry();
1616 }
1617 // sym.collect();
1618 // anti-symmetrise over boxes in columns
1619 if(modulo_monoterm) {
1620 int newmult=1;
1621 for(unsigned int c=0; c<row_size(0); ++c)
1622 newmult*=combin::factorial(column_size(c));
1623 for(unsigned int i=0; i<sym.size(); ++i)
1624 sym.set_multiplicity(i, sym.signature(i)*newmult);
1625 }
1626 else {
1627 sym.permute_blocks.clear();
1628 for(unsigned int c=0; c<row_size(0); ++c) {
1629 unsigned int r=0;
1630 sym.value_permute.clear();
1631 sym.permutation_sign=-1;
1632 sym.input_asym.clear();
1633 while(r<number_of_rows() && c<row_size(r))
1634 sym.value_permute.push_back(rows[r++][c]);
1635 if(sym.value_permute.size()>1)
1636 sym.apply_symmetry();
1637 }
1638 }
1639 // sym.collect();
1640 }
1641
1642 template<class T>
1644 combin::range_vector_t& sublengths_scattered) const
1645 {
1646 for(unsigned int r=0; r<number_of_rows(); ++r)
1647 for(unsigned int c=0; c<row_size(r); ++c)
1648 sym.original.push_back(rows[r][c]);
1649
1650 unsigned int offset=0;
1651 // symmetrise over boxes in rows
1652 for(unsigned int r=0; r<number_of_rows(); ++r) {
1653 sym.permutation_sign=1;
1654 sym.permute_blocks.clear();
1655 sym.block_length=1;
1656 sym.input_asym.clear();
1657 for(unsigned int c=0; c<row_size(r); ++c)
1658 sym.permute_blocks.push_back(offset++);
1659 sym.apply_symmetry();
1660 }
1662 sym.permute_blocks.clear();
1663 for(unsigned int c=0; c<row_size(0); ++c) {
1664 unsigned int r=0;
1665 sym.value_permute.clear();
1666 sym.permutation_sign=-1;
1667 while(r<number_of_rows() && c<row_size(r))
1668 sym.value_permute.push_back(rows[r++][c]);
1669
1670 sym.sublengths_scattered=sublengths_scattered;
1671
1672 // // Now setup sublengths_scattered to take into account
1673 // // asym_ranges. These asym_ranges refer to values stored in the
1674 // // boxes of the full tableau. We need to find the locations of
1675 // // these values inside the full original, as that is what goes
1676 // // into sublengths_scattered.
1677 //
1678 // sym.input_asym.clear();
1679 // sym.sublengths.clear();
1680 // sym.sublengths_scattered.clear();
1681 // for(unsigned int m=0; m<sym.value_permute.size(); ++m) {
1682 // // Try to find this value in an asym range.
1683 // unsigned int overlap=0;
1684 // for(unsigned int n=0; n<asym_ranges.size(); ++n) {
1685 // for(unsigned int nn=0; nn<asym_ranges[n].size(); ++nn) {
1686 // if(sym.value_permute[m]==asym_ranges[n][nn]) {
1687 // std::cout << "found " << sym.value_permute[m] << " in range" << std::endl;
1688 // // FIXME: this assumes that even though asym_ranges[n] is a superset
1689 // // of the current part of value_permute, elements are in the same order.
1690 // ++m; ++nn;
1691 // while(nn<asym_ranges[n].size()) {
1692 // if(sym.value_permute[m]==asym_ranges[n][nn]) {
1693 // std::cout << "same range: " << sym.value_permute[m] << std::endl;
1694 // ++m;
1695 // ++overlap;
1696 // }
1697 // ++nn;
1698 // }
1699 // break;
1700 // }
1701 // }
1702 // }
1703 // if(overlap>0) --m;
1704 // sym.sublengths.push_back(overlap+1);
1705 // }
1706 // unsigned int sum=0;
1707 // for(unsigned int m=0; m<sym.sublengths.size(); ++m)
1708 // sum+=sym.sublengths[m];
1709 //
1710 // std::cout << sum << " " << sym.value_permute.size() << std::endl;
1711 // assert(sum==sym.value_permute.size());
1712
1713 // All set to run...
1714 if(sym.value_permute.size()>1)
1715 sym.apply_symmetry();
1716 }
1717 }
1718
1719 template<class T>
1721 {
1722 rows=other.rows;
1723 tableau::operator=(other);
1724 return (*this);
1725 }
1726
1727 template<class T>
1729 {
1730 yngint_t totdim=0;
1731 typename tableau_container_t::const_iterator it=storage.begin();
1732 while(it!=storage.end()) {
1733 totdim+=(*it).dimension(dim);
1734 ++it;
1735 }
1736 return totdim;
1737 }
1738
1739 template<class T, class OutputIterator>
1740 void LR_tensor(const tableaux<T>& tabs1, const T& tab2, unsigned int maxrows,
1741 OutputIterator out, bool alltabs=false)
1742 {
1744 while(it!=tabs1.storage.end()) {
1745 LR_tensor((*it), tab2, maxrows, out, alltabs);
1746 ++it;
1747 }
1748 }
1749
1750 template<class T1, class T2>
1751 void add_box(T1& tab1, unsigned int row1,
1752 const T2& tab2, unsigned int row2, unsigned int col2)
1753 {
1754 tab1.add_box(row1, tab2(row2,col2));
1755 }
1756
1757 template<class T1>
1758 void add_box(T1& tab1, unsigned int row1,
1759 const tableau&, unsigned int, unsigned int)
1760 {
1761 tab1.add_box(row1);
1762 }
1763
1765
1766 template<class Tab, class OutputIterator>
1767 void LR_add_box(const Tab& tab2, Tab& newtab,
1768 unsigned int currow2, unsigned int curcol2, unsigned int startrow,
1769 unsigned int maxrows,
1770 OutputIterator outit,
1771 keeptrack_tab_t& Ycurrent,
1772 bool alltabs)
1773 {
1774 // Are we at the end of the current row of boxes in tab2 ?
1775 if((++curcol2)==tab2.row_size(currow2)) {
1776 // Are we at the end of tab2 altogether?
1777 if((++currow2)==tab2.number_of_rows()) {
1778 *outit=newtab; // Store the product tableau just created.
1779 return;
1780 }
1781 curcol2=0;
1782 startrow=0;
1783 }
1784
1785 // Rule "row_by_row".
1786 for(unsigned int rowpos=startrow; rowpos<std::min(newtab.number_of_rows()+1,maxrows); ++rowpos) {
1787 // Rule "always_young".
1788 if(rowpos>0 && rowpos<newtab.number_of_rows())
1789 if(newtab.row_size(rowpos-1)==newtab.row_size(rowpos))
1790 continue; // No, would lead to non-Young tableau shape.
1791
1792 // The column where the box will be added.
1793 unsigned int colpos=(rowpos==newtab.number_of_rows())?0:newtab.row_size(rowpos);
1794
1795 // Rule "avoid_sym2asym".
1796 for(unsigned int rr=0; rr<rowpos; ++rr)
1797 if(Ycurrent(rr,colpos).first==(int)(currow2))
1798 goto rule_violated;
1799
1800 // Rule "avoid_asym2sym".
1801 if(alltabs) // if not generating all tabs, ordered will take care of this already.
1802 for(unsigned int cc=0; cc<colpos; ++cc)
1803 if(Ycurrent(rowpos,cc).second==(int)(curcol2))
1804 goto rule_violated;
1805
1806 // Rule "ordered".
1807 if(!alltabs && currow2>0) {
1808 int numi=0, numimin1=0;
1809 if(rowpos>0) {
1810 for(unsigned int sr=0; sr<rowpos; ++sr) // top to bottom
1811 for(unsigned int sc=0; sc<Ycurrent.row_size(sr); ++sc) { // right to left
1812 // Count all boxes from currow2 and from currow2-1.
1813 if(Ycurrent(sr,sc).first==(int)(currow2)) ++numi;
1814 if(Ycurrent(sr,sc).first==(int)(currow2)-1) ++numimin1;
1815 }
1816 }
1817 ++numi; // the box to be added
1818 if(numi>numimin1)
1819 goto rule_violated;
1820
1821 // continue counting to see whether a previously valid box is now invalid
1822 for(unsigned int sr=rowpos; sr<Ycurrent.number_of_rows(); ++sr) // top to bottom
1823 for(int sc=Ycurrent.row_size(sr)-1; sc>=0; --sc) { // right to left
1824 if(Ycurrent(sr,sc).first==(int)(currow2)) ++numi;
1825 if(Ycurrent(sr,sc).first==(int)(currow2)-1) ++numimin1;
1826 if(numi>numimin1)
1827 goto rule_violated;
1828 }
1829 }
1830
1831 // Put the box at row 'rowpos' and call LR_add_box recursively
1832 // to add the other boxes.
1833 Ycurrent.add_box(rowpos, std::pair<int,int>(currow2, curcol2));
1834 add_box(newtab, rowpos, tab2, currow2, curcol2);
1835 LR_add_box(tab2, newtab, currow2, curcol2, alltabs?0:rowpos, maxrows,
1836 outit, Ycurrent, alltabs);
1837
1838 // Remove the box again in preparation for trying to add it to other rows.
1839 newtab.remove_box(rowpos);
1840 Ycurrent.remove_box(rowpos);
1841
1842rule_violated:
1843 ;
1844 }
1845 }
1846
1847 template<class Tab, class OutputIterator>
1848 void LR_tensor(const Tab& tab1, const Tab& tab2, unsigned int maxrows,
1849 OutputIterator outit, bool alltabs=false)
1850 {
1851 // Make a copy of tab1 because LR_add_box has to change it and
1852 // tab1 is const here.
1853 Tab newtab(tab1);
1854
1855 // Tableau which keeps track of the LR rules. It contains the
1856 // current (incomplete) shape of the tensor product, and for all boxes
1857 // which come from tab2 we store the row and column of tab2
1858 // from which they originated. Tab1 boxes have (-2,-2) stored.
1859 keeptrack_tab_t Ycurrent;
1860 Ycurrent.copy_shape(tab1);
1861 keeptrack_tab_t::iterator yi=Ycurrent.begin();
1862 while(yi!=Ycurrent.end()) {
1863 (*yi)=std::pair<int,int>(-2,-2);
1864 ++yi;
1865 }
1866
1867 LR_add_box(tab2, newtab, 0, -1, 0, maxrows, outit, Ycurrent, alltabs);
1868 }
1869
1870 template<class T, class OutputIterator>
1871 void LR_tensor(const tableaux<T>&, bool, unsigned int, OutputIterator )
1872 {
1873 assert(1==0);
1874 }
1875
1876
1877
1878 std::ostream& operator<<(std::ostream&, const tableau& );
1879
1880 template<class T>
1881 std::ostream& operator<<(std::ostream&, const tableaux<T>& );
1882
1883 template<class T>
1884 std::ostream& operator<<(std::ostream&, const filled_tableau<T>& );
1885
1886 template<class T>
1888 {
1889 return rows.size();
1890 }
1891
1892 template<class T>
1893 unsigned int filled_tableau<T>::row_size(unsigned int num) const
1894 {
1895 assert(num<rows.size());
1896 return rows[num].size();
1897 }
1898
1899 template<class T>
1900 T& filled_tableau<T>::operator()(unsigned int row, unsigned int col)
1901 {
1902 assert(row<rows.size());
1903 assert(col<rows[row].size());
1904 return rows[row][col];
1905 }
1906
1907 template<class T>
1908 const T& filled_tableau<T>::operator()(unsigned int row, unsigned int col) const
1909 {
1910 assert(row<rows.size());
1911 assert(col<rows[row].size());
1912 return rows[row][col];
1913 }
1914
1915 template<class T>
1916 const T& filled_tableau<T>::operator[](unsigned int boxnum) const
1917 {
1918 unsigned int row = 0;
1919 while (true) {
1920 if (boxnum < row_size(row))
1921 break;
1922 boxnum -= row_size(row);
1923 ++row;
1924 }
1925 return rows[row][boxnum];
1926 }
1927
1928 template<class T>
1932
1933 template<class T>
1934 void filled_tableau<T>::add_box(unsigned int rownum)
1935 {
1936 if(rownum>=rows.size())
1937 rows.resize(rownum+1);
1938 assert(rownum<rows.size());
1939 rows[rownum].push_back(T());
1940 }
1941
1942 template<class T>
1943 void filled_tableau<T>::add_box(unsigned int rownum, T val)
1944 {
1945 if(rownum>=rows.size())
1946 rows.resize(rownum+1);
1947 assert(rownum<rows.size());
1948 rows[rownum].push_back(val);
1949 }
1950
1951 template<class T>
1952 void filled_tableau<T>::swap_columns(unsigned int c1, unsigned int c2)
1953 {
1954 assert(c1<row_size(0) && c2<row_size(0));
1955 assert(column_size(c1)==column_size(c2));
1956 for(unsigned int r=0; r<column_size(c1); ++r) {
1957 T tmp=(*this)(r,c1);
1958 (*this)(r,c1)=(*this)(r,c2);
1959 (*this)(r,c2)=tmp;
1960 }
1961 }
1962
1963 template<class T>
1964 void filled_tableau<T>::remove_box(unsigned int rownum)
1965 {
1966 assert(rownum<rows.size());
1967 assert(rows[rownum].size()>0);
1968 rows[rownum].pop_back();
1969 if(rows[rownum].size()==0)
1970 rows.pop_back();
1971 }
1972
1973 template<class T>
1975 {
1976 rows.clear();
1978 }
1979
1980 template<class T>
1981 std::ostream& operator<<(std::ostream& str, const tableaux<T>& tabs)
1982 {
1984 while(it!=tabs.storage.end()) {
1985 str << (*it) << std::endl << std::endl;
1986 ++it;
1987 }
1988 return str;
1989 }
1990
1991 template<class T>
1992 std::ostream& operator<<(std::ostream& str, const filled_tableau<T>& tab)
1993 {
1994 for(unsigned int i=0; i<tab.number_of_rows(); ++i) {
1995 for(unsigned int j=0; j<tab.row_size(i); ++j) {
1996 // str << "|" << tab(i,j) << "|";
1997 str << tab(i,j);
1998 }
1999 if(i==0) {
2000 str << " " << tab.dimension(10);
2001 if(tab.has_nullifying_trace()) str << " null";
2002 }
2003 if(i!=tab.number_of_rows()-1)
2004 str << std::endl;
2005 else
2006 str << " (" << tab.multiplicity << ")" << std::endl;
2007 }
2008 return str;
2009 }
2010
2011 };
2012
2013
bool operator<(const cadabra::Ex::iterator &i1, const cadabra::Ex::iterator &i2)
Definition Compare.cc:1761
mpq_class yngrat_t
Definition YoungTab.hh:39
mpz_class yngint_t
Definition YoungTab.hh:38
std::vector< unsigned int > sublengths
Definition Combinatorics.hh:74
std::vector< T > original
Definition Combinatorics.hh:76
void permute(long start=-1, long end=-1)
Definition Combinatorics.hh:351
Definition Combinatorics.hh:101
int ordersign(unsigned int) const
Definition Combinatorics.hh:458
unsigned int size() const
Definition Combinatorics.hh:429
Definition Combinatorics.hh:154
unsigned int size() const
Definition Combinatorics.hh:906
void apply_symmetry(long start=-1, long end=-1)
Definition Combinatorics.hh:695
int permutation_sign
Definition Combinatorics.hh:163
range_vector_t sublengths_scattered
Definition Combinatorics.hh:167
std::vector< unsigned int > permute_blocks
Definition Combinatorics.hh:161
std::vector< T > original
Definition Combinatorics.hh:159
range_vector_t input_asym
Definition Combinatorics.hh:166
std::vector< T > value_permute
Definition Combinatorics.hh:162
void set_multiplicity(unsigned int pos, int val)
Definition Combinatorics.hh:1003
unsigned int block_length
Definition Combinatorics.hh:160
int signature(unsigned int) const
Definition Combinatorics.hh:996
size_t size_type
Definition YoungTab.hh:135
T value_type
Definition YoungTab.hh:132
const T * pointer
Definition YoungTab.hh:133
const T & reference
Definition YoungTab.hh:134
ptrdiff_t difference_type
Definition YoungTab.hh:136
std::random_access_iterator_tag iterator_category
Definition YoungTab.hh:137
Definition YoungTab.hh:289
const T & operator*() const
Definition YoungTab.hh:1248
bool operator==(const const_iterator &) const
Definition YoungTab.hh:1334
bool operator<(const const_iterator &other) const
Definition YoungTab.hh:1342
bool operator!=(const const_iterator &) const
Definition YoungTab.hh:1356
const_iterator & operator++()
Definition YoungTab.hh:1260
const_iterator(unsigned int r, unsigned int c, const filled_tableau< T > *)
Definition YoungTab.hh:1214
const T * operator->() const
Definition YoungTab.hh:1254
const_iterator(const iterator &other)
bool operator>(const const_iterator &other) const
Definition YoungTab.hh:1349
const_iterator & operator+=(unsigned int)
Definition YoungTab.hh:1270
unsigned int column_number
Definition YoungTab.hh:312
const_iterator operator+(unsigned int)
Definition YoungTab.hh:1226
unsigned int row_number
Definition YoungTab.hh:312
const_iterator & operator-=(unsigned int)
Definition YoungTab.hh:1320
const filled_tableau< T > * tab
Definition YoungTab.hh:311
const_iterator operator-(unsigned int)
Definition YoungTab.hh:1234
const_iterator & operator--()
Definition YoungTab.hh:1283
A const iterator which stays inside a given column of a tableau.
Definition YoungTab.hh:177
in_column_const_iterator & operator+=(unsigned int)
Definition YoungTab.hh:717
bool operator<(const in_column_const_iterator &other) const
Definition YoungTab.hh:776
const T * operator->() const
Definition YoungTab.hh:704
in_column_const_iterator(unsigned int r, unsigned int c, const filled_tableau< T > *)
Definition YoungTab.hh:664
in_column_const_iterator & operator--()
Definition YoungTab.hh:724
unsigned int column_number
Definition YoungTab.hh:202
bool operator<=(const in_column_const_iterator &other) const
Definition YoungTab.hh:762
in_column_const_iterator & operator-=(unsigned int)
Definition YoungTab.hh:747
bool operator>(const in_column_const_iterator &other) const
Definition YoungTab.hh:783
bool operator!=(const in_column_const_iterator &) const
Definition YoungTab.hh:790
unsigned int row_number
Definition YoungTab.hh:202
const filled_tableau< T > * tab
Definition YoungTab.hh:201
const T & operator*() const
Definition YoungTab.hh:698
in_column_const_iterator operator+(unsigned int)
Definition YoungTab.hh:676
in_column_const_iterator operator-(unsigned int)
Definition YoungTab.hh:684
bool operator>=(const in_column_const_iterator &other) const
Definition YoungTab.hh:769
in_column_const_iterator(const in_column_iterator &other)
bool operator==(const in_column_const_iterator &) const
Definition YoungTab.hh:754
in_column_const_iterator & operator++()
Definition YoungTab.hh:710
An iterator which stays inside a given column of a tableau.
Definition YoungTab.hh:147
T * operator->() const
Definition YoungTab.hh:569
in_column_iterator operator-(unsigned int)
Definition YoungTab.hh:543
in_column_iterator operator+(unsigned int)
Definition YoungTab.hh:535
filled_tableau< T > * tab
Definition YoungTab.hh:172
in_column_iterator & operator--()
Definition YoungTab.hh:589
bool operator>(const in_column_iterator &other) const
Definition YoungTab.hh:648
bool operator>=(const in_column_iterator &other) const
Definition YoungTab.hh:634
T & operator*() const
Definition YoungTab.hh:563
unsigned int row_number
Definition YoungTab.hh:173
bool operator==(const in_column_iterator &) const
Definition YoungTab.hh:619
bool operator<(const in_column_iterator &other) const
Definition YoungTab.hh:641
T & operator[](int n) const
Definition YoungTab.hh:557
in_column_iterator & operator++()
Definition YoungTab.hh:575
bool operator!=(const in_column_iterator &) const
Definition YoungTab.hh:655
in_column_iterator & operator-=(unsigned int)
Definition YoungTab.hh:612
in_column_iterator(unsigned int r, unsigned int c, filled_tableau< T > *)
Definition YoungTab.hh:529
unsigned int column_number
Definition YoungTab.hh:173
in_column_iterator & operator+=(unsigned int)
Definition YoungTab.hh:582
bool operator<=(const in_column_iterator &other) const
Definition YoungTab.hh:627
bool operator<(const in_row_const_iterator &other) const
Definition YoungTab.hh:1042
bool operator<=(const in_row_const_iterator &other) const
Definition YoungTab.hh:1028
in_row_const_iterator operator+(unsigned int)
Definition YoungTab.hh:942
in_row_const_iterator operator-(unsigned int)
Definition YoungTab.hh:950
in_row_const_iterator & operator+=(unsigned int)
Definition YoungTab.hh:983
bool operator>=(const in_row_const_iterator &other) const
Definition YoungTab.hh:1035
in_row_const_iterator(unsigned int r, unsigned int c, const filled_tableau< T > *)
Definition YoungTab.hh:929
bool operator==(const in_row_const_iterator &) const
Definition YoungTab.hh:1020
in_row_const_iterator & operator--()
Definition YoungTab.hh:990
const T & operator*() const
Definition YoungTab.hh:964
unsigned int column_number
Definition YoungTab.hh:259
const T * operator->() const
Definition YoungTab.hh:970
bool operator>(const in_row_const_iterator &other) const
Definition YoungTab.hh:1049
in_row_const_iterator & operator++()
Definition YoungTab.hh:976
in_row_const_iterator(const in_row_iterator &other)
bool operator!=(const in_row_const_iterator &) const
Definition YoungTab.hh:1056
in_row_const_iterator & operator-=(unsigned int)
Definition YoungTab.hh:1013
const filled_tableau< T > * tab
Definition YoungTab.hh:258
unsigned int row_number
Definition YoungTab.hh:259
An iterator which stays inside a given row of a tableau.
Definition YoungTab.hh:206
in_row_iterator operator-(unsigned int)
Definition YoungTab.hh:814
bool operator==(const in_row_iterator &) const
Definition YoungTab.hh:884
T * operator->() const
Definition YoungTab.hh:834
in_row_iterator operator+(unsigned int)
Definition YoungTab.hh:806
T & operator*() const
Definition YoungTab.hh:828
bool operator>(const in_row_iterator &other) const
Definition YoungTab.hh:913
in_row_iterator(unsigned int r, unsigned int c, filled_tableau< T > *)
Definition YoungTab.hh:800
bool operator<=(const in_row_iterator &other) const
Definition YoungTab.hh:892
bool operator>=(const in_row_iterator &other) const
Definition YoungTab.hh:899
bool operator<(const in_row_iterator &other) const
Definition YoungTab.hh:906
unsigned int column_number
Definition YoungTab.hh:231
in_row_iterator & operator+=(unsigned int)
Definition YoungTab.hh:847
unsigned int row_number
Definition YoungTab.hh:231
filled_tableau< T > * tab
Definition YoungTab.hh:230
in_row_iterator & operator++()
Definition YoungTab.hh:840
in_row_iterator & operator--()
Definition YoungTab.hh:854
bool operator!=(const in_row_iterator &) const
Definition YoungTab.hh:920
in_row_iterator & operator-=(unsigned int)
Definition YoungTab.hh:877
Definition YoungTab.hh:120
ptrdiff_t difference_type
Definition YoungTab.hh:126
T & reference
Definition YoungTab.hh:124
T * pointer
Definition YoungTab.hh:123
size_t size_type
Definition YoungTab.hh:125
std::random_access_iterator_tag iterator_category
Definition YoungTab.hh:127
T value_type
Definition YoungTab.hh:122
An iterator over all boxes of a tableau, left to right, top to bottom.
Definition YoungTab.hh:263
filled_tableau< T > * tab
Definition YoungTab.hh:285
unsigned int column_number
Definition YoungTab.hh:286
T * operator->() const
Definition YoungTab.hh:1101
iterator & operator--()
Definition YoungTab.hh:1130
bool operator>(const iterator &other) const
Definition YoungTab.hh:1196
iterator & operator+=(unsigned int)
Definition YoungTab.hh:1117
bool operator<(const iterator &other) const
Definition YoungTab.hh:1189
iterator & operator-=(unsigned int)
Definition YoungTab.hh:1167
iterator(unsigned int r, unsigned int c, filled_tableau< T > *)
Definition YoungTab.hh:1067
iterator operator-(unsigned int)
Definition YoungTab.hh:1081
iterator & operator++()
Definition YoungTab.hh:1107
iterator operator+(unsigned int)
Definition YoungTab.hh:1073
unsigned int row_number
Definition YoungTab.hh:286
T & operator*() const
Definition YoungTab.hh:1095
bool operator==(const iterator &) const
Definition YoungTab.hh:1181
bool operator!=(const iterator &) const
Definition YoungTab.hh:1203
Definition YoungTab.hh:84
const T & operator()(unsigned int row, unsigned int col) const
Definition YoungTab.hh:1908
virtual ~filled_tableau()
Definition YoungTab.hh:1929
void projector(combin::symmetriser< T > &, combin::range_vector_t &) const
Definition YoungTab.hh:1643
void canonicalise(StrictWeakOrdering comp, bool only_col_ex=false)
Definition YoungTab.hh:518
T value_type
Definition YoungTab.hh:86
in_row_iterator end_row(unsigned int row_number)
Definition YoungTab.hh:1465
std::vector< T > box_row
Definition YoungTab.hh:338
const_iterator begin() const
Definition YoungTab.hh:1391
void sort_columns()
Definition YoungTab.hh:477
void add_box(unsigned int rownum, T val)
Definition YoungTab.hh:1943
in_column_const_iterator begin_column(unsigned int column_number) const
Definition YoungTab.hh:1447
in_row_const_iterator cbegin_row(unsigned int row_number) const
Definition YoungTab.hh:1471
const_iterator cbegin() const
Definition YoungTab.hh:1379
void projector(combin::symmetriser< T > &, bool modulo_monoterm=false) const
Definition YoungTab.hh:1600
in_column_const_iterator cbegin_column(unsigned int column_number) const
Definition YoungTab.hh:1425
virtual unsigned int number_of_rows() const
Definition YoungTab.hh:1887
const_iterator cend() const
Definition YoungTab.hh:1385
void sort_within_columns(StrictWeakOrdering comp)
Definition YoungTab.hh:492
bool compare_without_multiplicity(const filled_tableau< T > &other) const
Definition YoungTab.hh:422
filled_tableau< T > & operator=(const filled_tableau< T > &)
Definition YoungTab.hh:1720
in_column_iterator begin_column(unsigned int column_number)
Definition YoungTab.hh:1403
void sort_within_columns()
Definition YoungTab.hh:470
iterator end()
Definition YoungTab.hh:1372
in_row_const_iterator cend_row(unsigned int row_number) const
Definition YoungTab.hh:1477
void canonicalise()
Sort equal-length columns and sort within columns.
Definition YoungTab.hh:484
void copy_shape(const tableau &)
Definition YoungTab.hh:412
std::pair< int, int > find(const T &) const
Definition YoungTab.hh:458
std::vector< box_row > row_stack
Definition YoungTab.hh:339
in_row_iterator begin_row(unsigned int row_number)
Definition YoungTab.hh:1459
void sort_columns(StrictWeakOrdering comp)
Definition YoungTab.hh:504
row_stack rows
Definition YoungTab.hh:340
T & operator()(unsigned int row, unsigned int col)
Definition YoungTab.hh:1900
const T & operator[](unsigned int boxnum) const
Definition YoungTab.hh:1916
yngrat_t projector_normalisation() const
Definition YoungTab.hh:1592
OutputIterator Garnir_set(OutputIterator, unsigned int, unsigned int) const
Definition YoungTab.hh:1499
in_column_iterator end_column(unsigned int column_number)
Definition YoungTab.hh:1412
in_row_const_iterator end_row(unsigned int row_number) const
Definition YoungTab.hh:1489
iterator begin()
Definition YoungTab.hh:1366
bool has_nullifying_trace() const
Definition YoungTab.hh:428
void swap_columns(unsigned int c1, unsigned int c2)
Definition YoungTab.hh:1952
std::pair< int, int > nonstandard_loc() const
Definition YoungTab.hh:1523
in_column_const_iterator end_column(unsigned int column_number) const
Definition YoungTab.hh:1453
in_column_const_iterator cend_column(unsigned int column_number) const
Definition YoungTab.hh:1434
virtual unsigned int row_size(unsigned int row) const
Definition YoungTab.hh:1893
virtual void clear()
Definition YoungTab.hh:1974
virtual void add_box(unsigned int row)
Definition YoungTab.hh:1934
const_iterator end() const
Definition YoungTab.hh:1397
virtual void remove_box(unsigned int row)
Definition YoungTab.hh:1964
in_row_const_iterator begin_row(unsigned int row_number) const
Definition YoungTab.hh:1483
Definition YoungTab.hh:47
unsigned long hook_length(unsigned int row, unsigned int col) const
Definition YoungTab.cc:72
yngint_t hook_length_prod() const
Definition YoungTab.cc:82
virtual ~tableau_base()
Definition YoungTab.cc:31
virtual unsigned int number_of_rows() const =0
yngint_t dimension(unsigned int) const
Definition YoungTab.cc:47
tableau_base()
Definition YoungTab.cc:26
virtual void clear()=0
virtual unsigned int row_size(unsigned int row) const =0
virtual void add_row(unsigned int row_size)
Definition YoungTab.cc:39
yngrat_t multiplicity
Definition YoungTab.hh:59
virtual void add_box(unsigned int row)=0
int selfdual_column
Definition YoungTab.hh:60
virtual unsigned int column_size(unsigned int col) const
Definition YoungTab.cc:61
virtual void remove_box(unsigned int row)=0
Definition YoungTab.hh:66
virtual unsigned int number_of_rows() const
Definition YoungTab.cc:110
tableau & operator=(const tableau &)
Definition YoungTab.cc:126
virtual unsigned int row_size(unsigned int row) const
Definition YoungTab.cc:115
virtual void add_box(unsigned int row)
Definition YoungTab.cc:91
virtual void clear()
Definition YoungTab.cc:121
virtual void remove_box(unsigned int row)
Definition YoungTab.cc:102
std::vector< int > rows
Definition YoungTab.hh:77
virtual ~tableau()
Definition YoungTab.cc:35
Definition YoungTab.hh:344
std::list< T > tableau_container_t
Definition YoungTab.hh:354
tableau_container_t storage
Definition YoungTab.hh:355
void add_tableau(const T &)
Definition YoungTab.hh:1575
bool standard_form()
Put the set of tableaux into standard form by using Garnir symmetries.
Definition YoungTab.hh:1539
std::back_insert_iterator< tableau_container_t > back_insert_iterator
Definition YoungTab.hh:357
yngint_t total_dimension(unsigned int dim)
Definition YoungTab.hh:1728
std::vector< range_t > range_vector_t
Definition Combinatorics.hh:40
unsigned long factorial(unsigned int x)
Definition Combinatorics.cc:23
int ordersign(iterator1 b1, iterator1 e1, iterator2 b2, iterator2 e2, int stepsize=1)
Definition Combinatorics.hh:224
Generic Young tableaux routines.
Definition YoungTab.cc:24
std::ostream & operator<<(std::ostream &str, const tableau &tab)
Definition YoungTab.cc:132
bool legal_box(const std::vector< std::pair< int, int > > &prev, const std::vector< std::pair< int, int > > &ths, int colpos, int trypos)
filled_tableau< std::pair< int, int > > keeptrack_tab_t
Definition YoungTab.hh:1764
void LR_tensor(const tableaux< T > &tabs1, const T &tab2, unsigned int maxrows, OutputIterator out, bool alltabs=false)
Definition YoungTab.hh:1740
void LR_add_box(const Tab &tab2, Tab &newtab, unsigned int currow2, unsigned int curcol2, unsigned int startrow, unsigned int maxrows, OutputIterator outit, keeptrack_tab_t &Ycurrent, bool alltabs)
Definition YoungTab.hh:1767