1 /* Copyright (c) 1997-2021
2    Ewgenij Gawrilow, Michael Joswig, and the polymake team
3    Technische Universität Berlin, Germany
4    https://polymake.org
5 
6    This program is free software; you can redistribute it and/or modify it
7    under the terms of the GNU General Public License as published by the
8    Free Software Foundation; either version 2, or (at your option) any
9    later version: http://www.gnu.org/licenses/gpl.txt.
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
13    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
14    GNU General Public License for more details.
15 --------------------------------------------------------------------------------
16 */
17 
18 #pragma once
19 
20 #include "polymake/Array.h"
21 #include "polymake/hash_map"
22 #include "polymake/SparseMatrix.h"
23 #include "polymake/Rational.h"
24 
25 namespace polymake { namespace group {
26 
27 template <typename SetType>
28 class InducedAction {
29 protected:
30    Int degree;
31    const Array<SetType>& domain;
32    const hash_map<SetType, Int>& index_of;
33 
inverse_permutation(const Array<Int> & perm)34    Array<Int> inverse_permutation(const Array<Int>& perm) const
35    {
36       Array<Int> inv_perm(perm.size());
37       for (Int i = 0; i < perm.size(); ++i)
38          inv_perm[perm[i]] = i;
39       return inv_perm;
40    }
41 
42 public:
InducedAction(Int degree_,const Array<SetType> & domain_,const hash_map<SetType,Int> & index_of_)43    InducedAction(Int degree_,
44                  const Array<SetType>& domain_,
45                  const hash_map<SetType, Int>& index_of_)
46       : degree(degree_)
47       , domain(domain_)
48       , index_of(index_of_)
49    {}
50 
index_of_image(const Array<Int> & perm,const SetType & elt)51    Int index_of_image(const Array<Int>& perm,
52                       const SetType& elt) const
53    {
54       SetType image;
55       image.resize(perm.size());
56       for (auto sit = entire(elt); !sit.at_end(); ++sit)
57          image += perm[*sit];
58       return index_of.at(image);
59    }
60 
index_of_inverse_image(const Array<Int> & perm,const SetType & elt)61    Int index_of_inverse_image(const Array<Int>& perm,
62                               const SetType& elt) const
63    {
64       Array<Int> inv_perm(inverse_permutation(perm));
65       SetType inv_image;
66       inv_image.resize(inv_perm.size());
67       for (auto sit = entire(elt); !sit.at_end(); ++sit)
68          inv_image += inv_perm[*sit];
69       return index_of.at(inv_image);
70    }
71 
index_of_inverse_image(const Array<Int> & perm,const Int elt_index)72    Int index_of_inverse_image(const Array<Int>& perm,
73                               const Int elt_index) const
74    {
75       return index_of_inverse_image(perm, domain[elt_index]);
76    }
77 
induced_rep(const Array<Int> & perm)78    SparseMatrix<Rational> induced_rep(const Array<Int>& perm) const
79    {
80       SparseMatrix<Rational> induced_rep(degree, degree);
81       Int col_index = 0;
82       for (auto dit = entire(domain); !dit.at_end(); ++dit, ++col_index) {
83          induced_rep(index_of_image(perm, *dit), col_index) = 1;
84       }
85       return induced_rep;
86    }
87 };
88 
89 } }
90 
91 
92 
93 // Local Variables:
94 // mode:C++
95 // c-basic-offset:3
96 // indent-tabs-mode:nil
97 // End:
98 
99