permlib 0.2.9
Library for permutation computations
Loading...
Searching...
No Matches
abstract_symmetric_product.h
1// ---------------------------------------------------------------------------
2//
3// This file is part of PermLib.
4//
5// Copyright (c) 2009-2012 Thomas Rehn <thomas@carmen76.de>
6// All rights reserved.
7//
8// Redistribution and use in source and binary forms, with or without
9// modification, are permitted provided that the following conditions
10// are met:
11// 1. Redistributions of source code must retain the above copyright
12// notice, this list of conditions and the following disclaimer.
13// 2. Redistributions in binary form must reproduce the above copyright
14// notice, this list of conditions and the following disclaimer in the
15// documentation and/or other materials provided with the distribution.
16// 3. The name of the author may not be used to endorse or promote products
17// derived from this software without specific prior written permission.
18//
19// THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
20// IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
21// OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
22// IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,
23// INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
24// NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
25// DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
26// THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
27// (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
28// THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
29//
30// ---------------------------------------------------------------------------
31
32#include <boost/shared_ptr.hpp>
33
34#include <algorithm>
35#include <map>
36#include <permlib/abstract_permutation_group.h>
37
38#ifndef ABSTRACT_SYMMETRIC_PRODUCT_H_
39#define ABSTRACT_SYMMETRIC_PRODUCT_H_
40
41namespace permlib {
42
45public:
47
54 template<typename InputIterator>
55 AbstractSymmetricProduct(InputIterator begin, InputIterator end) {
56 for (InputIterator it = begin; it != end; ++it) {
57 m_indices.push_back(std::set<dom_int>((*it).begin(), (*it).end()));
58 }
59 }
60
61 virtual AbstractPermutationGroup* setStabilizer(const std::vector<dom_int>& s) const;
62 virtual OrbitList* orbits() const;
63 // TODO: must s be sorted?
64 virtual OrbitList* orbits(const std::vector<dom_int>& s) const;
65
66 virtual bool isLexMinSet(const std::vector<dom_int>& setIndices, const std::vector<dom_int>& rankIndices) const;
67
68 virtual AbstractGroupType type() const { return AGT_SymmetricProduct; }
69protected:
70 virtual void transversalSizes(std::vector<unsigned long>& sizes) const;
71
72private:
74
75 typedef std::list<std::set<dom_int> > IndexList;
76 std::list<std::set<dom_int> > m_indices;
77 mutable std::map<dom_int, dom_int> m_indicesReverse;
78
79 int getOrbitRank(dom_int x) const;
80};
81
82inline void AbstractSymmetricProduct::transversalSizes(std::vector<unsigned long>& sizes) const {
83 sizes.clear();
84 sizes.reserve(m_indices.size());
85 BOOST_FOREACH(const std::set<dom_int>& ind, m_indices) {
86 for (unsigned long x = ind.size(); x > 1; --x)
87 sizes.push_back(x);
88 }
89}
90
91inline AbstractPermutationGroup* AbstractSymmetricProduct::setStabilizer(const std::vector<dom_int>& svec) const {
92 std::set<dom_int> s(svec.begin(), svec.end());
93
95 BOOST_FOREACH(const std::set<dom_int>& ind, m_indices) {
96 std::set<dom_int> sA, sB;
97 std::set_difference(ind.begin(), ind.end(), s.begin(), s.end(), std::inserter(sA, sA.begin()));
98 if (sA.size() > 1) {
99 stabilizer->m_indices.push_back(sA);
100 }
101 std::set_intersection(ind.begin(), ind.end(), s.begin(), s.end(), std::inserter(sB, sB.begin()));
102 if (sB.size() > 1) {
103 stabilizer->m_indices.push_back(sB);
104 }
105 }
106 return stabilizer;
107}
108
110 OrbitList* retList = new OrbitList(m_indices);
111 return retList;
112}
113
114inline AbstractPermutationGroup::OrbitList* AbstractSymmetricProduct::orbits(const std::vector<dom_int>& s) const {
115 OrbitList* retList = new OrbitList();
116 BOOST_FOREACH(const std::set<dom_int>& ind, m_indices) {
117 std::set<dom_int>::const_iterator indIt = std::find_first_of(ind.begin(), ind.end(), s.begin(), s.end());
118 if (indIt != ind.end()) {
119 retList->push_back(ind);
120 }
121 }
122 return retList;
123}
124
125inline bool AbstractSymmetricProduct::isLexMinSet(const std::vector<dom_int>& setIndices, const std::vector<dom_int>& rankIndices) const {
126 std::vector<unsigned int> expectedPosition(m_indices.size());
127
128 BOOST_FOREACH(dom_int x, setIndices) {
129 // if x is not at expectedPosition of its orbit
130 // return false
131 const int rank = getOrbitRank(x);
132 if (rank < 0)
133 continue;
134
135 dom_int position = 0;
136 BOOST_FOREACH(dom_int el, rankIndices) {
137 if (el == x)
138 break;
139 if (getOrbitRank(el) == rank)
140 ++position;
141 }
142
143 if (expectedPosition[rank] != position)
144 return false;
145
146 ++expectedPosition[rank];
147 }
148
149 return true;
150}
151
152inline int AbstractSymmetricProduct::getOrbitRank(dom_int x) const {
153 if (m_indicesReverse.empty()) {
154 if (m_indices.empty())
155 return -1;
156
157 dom_int rank = 0;
158 BOOST_FOREACH(const std::set<dom_int>& orb, m_indices) {
159 BOOST_FOREACH(dom_int el, orb) {
160 m_indicesReverse[el] = rank;
161 }
162 ++rank;
163 }
164 }
165
166 std::map<dom_int, dom_int>::const_iterator pos = m_indicesReverse.find(x);
167 if (pos == m_indicesReverse.end())
168 return -1;
169
170 return (*pos).second;
171}
172
173} // end NS
174
175#endif
A high level interface for a permutation group.
Definition: abstract_permutation_group.h:54
std::list< std::set< dom_int > > OrbitList
typedef for a list of orbits, each of which is a set
Definition: abstract_permutation_group.h:74
A high level interface implementing a direct product of symmetric groups.
Definition: abstract_symmetric_product.h:44
virtual OrbitList * orbits() const
computes all orbits
Definition: abstract_symmetric_product.h:109
virtual bool isLexMinSet(const std::vector< dom_int > &setIndices, const std::vector< dom_int > &rankIndices) const
checks whether a set is lexicographically minimal with respect to a given ordering of indices
Definition: abstract_symmetric_product.h:125
virtual void transversalSizes(std::vector< unsigned long > &sizes) const
fills a list with sizes of transversals along a stabilizer chain
Definition: abstract_symmetric_product.h:82
virtual AbstractGroupType type() const
implementation type of this abstract class
Definition: abstract_symmetric_product.h:68
AbstractSymmetricProduct(InputIterator begin, InputIterator end)
constructor
Definition: abstract_symmetric_product.h:55
virtual AbstractPermutationGroup * setStabilizer(const std::vector< dom_int > &s) const
computes the stabilizer of a set
Definition: abstract_symmetric_product.h:91
stores an orbit in a sorted list
Definition: orbit_list.h:42