# Cyclically sort lists of mixed element types? [duplicate]

Consider the two lists

list1={1,2,a[1],8,b[4],9};
list2={8,b[4],9,1,2,a[1]};


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

cycRot[list1]==cycRot[list2]


True

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!

• 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. – Marius Ladegård Meyer Oct 15 '16 at 17:31
• 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. – Kagaratsch Oct 15 '16 at 17:38

Here is a function

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


list1 = {1, 2, a[1], 8, b[4], 9};
list2 = {8, b[4], 9, 1, 2, a[1]};
cyc[list1] == cyc[list2]
True

• I've updated the function. – bill s Oct 15 '16 at 17:54
• Exactly what I was looking for, thank you! – 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?