- #1
Jamin2112
- 986
- 12
Is there anything wrong with my logic and is there any way to further optimize this potentially long-running function? I've put a lot of comments to explain what's going on.
Code:
template <typename ObType, typename BinaryFunction>
bool isCyclic(const std::set<ObType> & G, BinaryFunction & op, ObType & g)
{
/*
isCyclic returns true or false depending on whether the group G
is an cyclic group, that is, whether it can be generated from
one its elements. Formally, G is cyclic if there exists an
element g in G such that, for all elements h in g,
h = g^n for some n.
*/
bool foundGenerator = false;
size_t maxN = G.size();
/*
Guaranteed that for each x in G, x^(maxN + 1) will be in the set
{x, x^2, ..., x^maxN}. That is the meaning of maxN.
*/
for (typename std::set<ObType>::const_iterator it(G.cbegin()), offend(G.cend()); it != offend && !foundGenerator; ++it)
{
ObType e0 = *it;
ObType e = e0;
std::set<ObType> powSet = {e};
size_t k = 2;
while (k <= maxN)
{
e = op(e, e0); /* Sets e equal to e^i */
if (powSet.count(e) == 0)
powSet.insert(e);
else
break;
/* Why the break statement?
If e is already in powSet, then we've found a cycle but
powSet != G; therefore e cannot generate G.
*/
++k;
}
if (k == maxN) /* true iff (powSet == G) */
{
foundGenerator = true;
g = e;
}
}
return foundGenerator;
}
Last edited: