103 const unsigned int n = m_U.n();
104 std::vector<dom_int> AllLambdas(n);
105 std::vector<dom_int> LambdaReverse(n, n);
106 unsigned int LambdaLastIndex = 0;
107 std::list<unsigned int> LambdaBegin;
108 std::list<unsigned int> LambdaSize;
111 for (omega = 0; omega < n; ++omega)
112 if (m_alpha != omega)
115 BOOST_ASSERT( omega < n );
119 for (
typename OrbitSet<PERM, dom_int>::const_iterator oit = omegaOrbit.
begin(); oit != omegaOrbit.
end(); ++oit) {
120 AllLambdas[LambdaLastIndex++] = *oit;
121 LambdaReverse[*oit] = 0;
123 LambdaBegin.push_back(0);
124 LambdaSize.push_back(omegaOrbit.
size());
127 const dom_int lambda = AllLambdas[LambdaBegin.back()];
128 std::vector<dom_int>::const_iterator LambdaItBegin = AllLambdas.begin() + LambdaBegin.back();
129 std::vector<dom_int>::const_iterator LambdaItEnd = LambdaItBegin + LambdaSize.back();
130 bool needAnotherIteration =
false;
132 PERMLIB_DEBUG( std::cout <<
"lambda = " << lambda << std::endl; )
134 for (std::vector<dom_int>::const_iterator lit = LambdaItBegin; lit != LambdaItEnd; ++lit) {
135 boost::scoped_ptr<PERM> u_lambda(m_U.at(lambda));
136 BOOST_ASSERT( u_lambda );
138 const dom_int gamma = *lit;
139 const dom_int mu = *u_lambda / gamma;
141 PERMLIB_DEBUG( std::cout <<
" u_lambda = " << *u_lambda <<
", gamma = " << gamma <<
", mu = " << mu << std::endl; )
143 const unsigned int muIndex = LambdaReverse[mu];
144 if (mu != m_alpha && muIndex == n) {
145 PERMLIB_DEBUG( std::cout <<
" add orbit of mu = " << mu <<
" at " << LambdaBegin.size() << std::endl; )
148 LambdaBegin.push_back(LambdaLastIndex);
149 LambdaSize.push_back(muOrbit.
size());
150 for (
typename OrbitSet<PERM, dom_int>::const_iterator oit = muOrbit.
begin(); oit != muOrbit.
end(); ++oit) {
151 AllLambdas[LambdaLastIndex++] = *oit;
152 LambdaReverse[*oit] = LambdaBegin.size() - 1;
154 needAnotherIteration =
true;
156 }
else if (muIndex < LambdaBegin.size() - 1) {
157 std::list<unsigned int>::const_reverse_iterator sizeIt = LambdaSize.rbegin();
158 std::list<unsigned int>::const_reverse_iterator reprIt = LambdaBegin.rbegin();
159 unsigned int largestReprIndex = n;
160 unsigned int largestLambdaSize = 0;
161 for (dom_int i = muIndex; i < LambdaBegin.size(); ++i) {
162 if (*sizeIt > largestLambdaSize) {
163 largestLambdaSize = *sizeIt;
164 largestReprIndex = *reprIt;
169 PERMLIB_DEBUG( std::cout <<
" merge sets from i = " << muIndex <<
" with representative " << AllLambdas[largestReprIndex] << std::endl; )
171 std::swap(AllLambdas[*boost::next(LambdaBegin.begin(), muIndex)], AllLambdas[largestReprIndex]);
172 for (dom_int i = LambdaBegin.size() - 1; i > muIndex ; --i) {
173 const unsigned int oldSize = LambdaSize.back();
174 LambdaSize.pop_back();
175 LambdaBegin.pop_back();
176 LambdaSize.back() += oldSize;
178 for (
unsigned int i = 0; i < n; ++i)
179 if (LambdaReverse[i] > muIndex && LambdaReverse[i] < n)
180 LambdaReverse[i] = muIndex;
182 PERMLIB_DEBUG( std::cout <<
" now there are " << LambdaBegin.size() <<
" sets left" << std::endl; )
183 needAnotherIteration =
true;
188 BOOST_ASSERT( LambdaBegin.size() == LambdaSize.size() );
190 if (!needAnotherIteration)
195 minimalBlock->clear();
196 minimalBlock->resize(LambdaSize.back() + 1);
197 minimalBlock->at(0) = m_alpha;
198 for (
unsigned int i = 1; i < minimalBlock->size(); ++i)
199 minimalBlock->at(i) = AllLambdas[LambdaBegin.back() + i - 1];
202 return LambdaSize.back() == m_U.size() - 1;