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.(adsbygoogle = window.adsbygoogle || []).push({});

Code (Text):

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;

}

**Physics Forums | Science Articles, Homework Help, Discussion**

Dismiss Notice

Join Physics Forums Today!

The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

# C++ function to tell whether a group is cyclic

Loading...

Similar Threads for function tell whether |
---|

Surface plot for a 3D function |

Program that calculates the list of x and f(x) for a given function |

C/++/# Is Pass-by-Reference part of a Function Signature? |

Fortran Fortran external functions vs subroutines |

**Physics Forums | Science Articles, Homework Help, Discussion**