Consider the two lists


it is evident by inspection that list2 is just a cyclic rotation of list1. Considering an equivalence class of lists under cyclic rotations, I would like to have a function cycRot[x_List] that takes a list and returns a cyclically rotated representative of that list, which would be independent of the initial cyclic order of the list. Such that



is guaranteed (the exact resulting rotation is irrelevant as long as the function returns the same result for any cyclically equivalent list). Is there such a function in Mathematica? Or maybe one can implement it efficiently? Thanks for any suggestion!

  • $\begingroup$ When asking for efficiency, do you have very large lists in mind, or very many short ones to compare, or something else? If the lists are short then list1 === RotateLeft[list2, First @ Position[list2, First @ list1, {1}, 1] - 1] should be ok. $\endgroup$ – Marius Ladegård Meyer Oct 15 '16 at 17:31
  • $\begingroup$ The problem with this is that I do not want to compare two explicitly given lists. Rather, I want a function that returns a unique representative of the equivalence class, which I could apply to any (previously unknown) number of lists as a substitution rule. $\endgroup$ – Kagaratsch Oct 15 '16 at 17:38

Here is a function

cyc[list_] := RotateLeft[list, First@Ordering[list, 1]]

For your lists:

list1 = {1, 2, a[1], 8, b[4], 9};
list2 = {8, b[4], 9, 1, 2, a[1]};
cyc[list1] == cyc[list2]
  • 1
    $\begingroup$ I've updated the function. $\endgroup$ – bill s Oct 15 '16 at 17:54
  • $\begingroup$ Exactly what I was looking for, thank you! $\endgroup$ – Kagaratsch Oct 15 '16 at 17:57

My own attempt at a solution is this

cycRot[x_List] := Block[{p},
  p = Position[x, Sort[x][[1]], 1][[1, 1]];
  {x[[p ;;]], x[[1 ;; p - 1]]} // Flatten

However, I am not sure if this is going to be slow for larger lists, since the cyclic property is not being utilized to improve performance when performing a complete sorting. Maybe there are better more efficient solutions?


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