3
$\begingroup$

Let $X$ be a set defined as $$X = \{\{\sigma_1, \dots, \sigma_L\} \;|\; \sigma_i = 0,\dots ,n-1\}.$$ Furthermore, let $T:X\longrightarrow X$ be a cyclic permutation $$ T\cdot\{\sigma_1, \dots, \sigma_L\} = \{\sigma_L, \sigma_1, \dots, \sigma_{L-1}\}, $$ generating a cyclic group $G=\{1, T, \dots, T^{L-1}\}$. I am interested in the set of orbits $O = X/G$ under this action. I.e. each element in $O$ is a subset of $X$, corresponding to elements that map into each other under $T$ (or in other words, each element of $O$ is of the form $G\cdot s$ for some $s\in X$).

Is there a fast and efficient way to compute the set of orbits $O$? Or even better, a representative of each orbit together with the orbit size?

Mathematica has the functions Orbits[pg,x] and OrbitRepresentatives[pg,x]. But I am not sure how to use these. Besides, they are part of the Combinatoria package but Mathematica does not like using this as part of the library are built into Mathematica now.

$\endgroup$
4
  • $\begingroup$ Maybe I misunderstand your description. T is a rotation of X to the right. That is, no element is mapped onto itself. And this is true for every element of G, with the exception of 1. And G.s == X, that is every orbit is identical to X $\endgroup$ Feb 5 at 18:03
  • $\begingroup$ Any elements $s$ of $X$ is of the form $s = \{\sigma_1, \dots, \sigma_L\}$ ,($\sigma_i=0,\dots,n-1$). Elements where all $\sigma$'s are the same will be invariant under the group action. For example, $G\cdot \{0,0,0, 0\} = \{ \{0, 0,0, 0\} \}$ is an orbit of length 1. Another example is $G\cdot \{1, 0,0, 0\} = \{ \{1, 0,0, 0\}, \{0, 1,0, 0\}, \{0, 0,1, 0\}, \{0, 0,0, 1\} \}$, which is an orbit of length 4. $\endgroup$
    – Heidar
    Feb 5 at 18:20
  • $\begingroup$ I just made the definition of $X$ more precise, as it was probably stated in a confusing way earlier. $\endgroup$
    – Heidar
    Feb 5 at 18:25
  • 1
    $\begingroup$ The definition: (σi=0,…,n−1) is confusing, you should write: (σi element of: {0,…,n−1}). I assumed that there are no repeating σi. $\endgroup$ Feb 5 at 19:19
4
$\begingroup$
GroupOrbits[CyclicGroup[5], {{1, 1, 2, 3, 3}}, Permute]
 {{{1, 1, 2, 3, 3}, 
  {1, 2, 3, 3, 1}, 
  {2, 3, 3, 1, 1},
  {3, 1, 1, 2, 3}, 
  {3, 3, 1, 1, 2}}}
$\endgroup$
1
$\begingroup$

After some clarification I think an orbit in the sense explained above can be found by repeating a right or left rotation n-1 times where n is the length of the list. This may produce identical lists (e.g. {1,2,1,2} shifted twice), therefore, we must weed out the duplicates, what can be done by DeleteDuplicates:

n = 5;
DeleteDuplicates[NestList[RotateRight, {1, 1, 2, 3, 3}, n - 1]]

(*  {{1, 1, 2, 3, 3}, {3, 1, 1, 2, 3}, {3, 3, 1, 1, 2}, {2, 3, 3, 1, 
  1}, {1, 2, 3, 3, 1}} *)
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.