Let $G$ be a finite group. Fix an element $x\in G$, and denote by $\sim$ the equivalence relation on $G$ given by $a\sim b \iff \exists m,n\text{ such that }a=x^m b x^n$.
Example: Let $G=\langle(123),(567),(1234)(5678)\rangle\leq S_8$ and choose $x=(1234)(5678)$. We have $\left|G\right|=288$. There are 16 classes containing 16 elements, 2 classes containing 8 elements, and 4 classes containing 4 elements for a total of $\left|G/\sim\right|=22$ classes.
Is there an efficient algorithm or formula to compute this for an arbitrary group $G$? What about if a representative of each class is required as well?
The "brute-force" way to compute it would be to loop through the elements of $G$ and number each element based on the class it appears in, but this requires $O(\left|G\right|)$ memory so it is inefficient if $G$ is large.