8
$\begingroup$

This question already has an answer here:

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!

$\endgroup$

marked as duplicate by Mr.Wizard Jun 23 '17 at 17:21

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

  • $\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
7
$\begingroup$

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]
True
$\endgroup$
  • 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
1
$\begingroup$

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?

$\endgroup$

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