2
$\begingroup$

This question already has an answer here:

This is a continuation of this question.

In the previous question we got a routine that can take two cyclically equivalent lists and determine their equivalence if all the elements in each list are unique:

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

However, this routine fails e.g. for the lists

list1 = {1, 1, 1, 3, 1, 1};
list2 = {3, 1, 1, 1, 1, 1};
cyc[list1]==cyc[list2]

False

Is there a convenient way to generalize the routine to be able to deal with lists containing repeated elements efficiently as well? Thanks for any suggestion!

$\endgroup$

marked as duplicate by Mr.Wizard function-construction Jun 23 '17 at 17:32

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.

1
$\begingroup$

This question is a duplicate of How to represent a list as a cycle and I shall be marking it as such. Note that canonize greatly outperforms Carl Woll's canon on long lists:

canonize[a_List] := 
  With[{X = # ~Extract~ Ordering[#, 1] &},
    RotateLeft[a, # - 1] & /@ Position[a, X @ a] // X
  ]

big = RandomInteger[500, 1000];

canonize@big === canon@big

canon[big];     // RepeatedTiming
canonize[big];  // RepeatedTiming
True

{0.0129, Null}

{0.0000548, Null}
$\endgroup$
  • $\begingroup$ Are duplicate questions deleted eventually? Curious, since I could delete it right away if thats the case. On the other hand, I would not have thought of searching for "represent list as cycle" to find the answer, so some redundancy in possible titles to search for in order to find this particular answer might be useful... $\endgroup$ – Kagaratsch Jun 23 '17 at 19:29
  • 1
    $\begingroup$ @Kagaratsch No, in all but rare cases "duplicate" (or more techincally already has an answer) Questions are not deleted and serve as signposts for the original/master Question just as you propose. ps thanks for the Accept. $\endgroup$ – Mr.Wizard Jun 23 '17 at 19:31
2
$\begingroup$

How about:

canon[list_] := First @ Sort @ NestList[RotateLeft, list, Length[list]-1]

Then:

canon[{1, 1, 1, 3, 1, 1}]
canon[{3, 1, 1, 1, 1, 1}]

{1, 1, 1, 1, 1, 3}

{1, 1, 1, 1, 1, 3}

$\endgroup$
  • $\begingroup$ This works great! Should be good enough for short lists, thank you! $\endgroup$ – Kagaratsch Jun 23 '17 at 4:34

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