Efficiently delete cyclic permutations in list [duplicate]

Question

This question already has an answer here:

• How to represent a list as a cycle 3 answers
• DeleteDuplicates[] does not work as expected on floating point values 2 answers

Edit I think I misused the words cyclic permutation. I mean rotating the list, but not changing the order: the permutations I'd like to consider for $a,b,c,d$ are $(b,c,d,a)$, $(c,d,a,b)$, $(d,a,b,c)$ but not $(b,a,c,d)$. Please let me know if you know the exact terminology.

---

I have a list of a few million 5-tuples and want to delete duplicates given a specified tolerance, and also cyclic permutations. For example, f[{{1.,2.,3.,4.,5.},{4.01,4.99,1.,2.03,3.2}}] should return {{1.,2.,3.,4.,5.}}.

The following naive approach works but is very slow for big lists:

n = 5;
norm[list1_, list2_] := 
          Min[Norm /@ (list2 - # & /@ NestList[RotateLeft, list1, n - 1])]

Union[{{1., 2., 3., 4., 5.}, {4.01, 4.99, 1., 2.03, 3.2}}, 
          SameTest -> (norm[#1, #2] < .3 &)]
(* {1., 2., 3., 4., 5.} *)

Example for a larger list:

tab = RandomReal[1, {5000, n}]; 
Union[tab, SameTest -> (norm[#1, #2] < .3 &)];//AbsoluteTiming
(* ~ 5 seconds *)

Are there some better solutions? If you post an answer, please explain the idea behind it, as it not always easy to understand.

Answer 1

SameTest is not always the best way to approach such tasks because it forces a pairwise comparison between all elements. That means $O(n^2)$ complexity.

A better way is to construct a canonical form. Transform each element to a standard form so that equivalent elements will look identical. The functions like Union or DeleteDuplicates can use $O(n \log n)$ algorithms based on sorting instead of pairwise comparison.

Of course such a canonical form doesn't always exist, but sometimes we can use approximations. The problem here is comparison with a tolerance. This isn't a proper equivalence relation anyway because it is not transitive ... I.e. with a tolerance of 0.01, 1.00 == 1.01 and 1.01 == 1.02, but 1.00 != 1.02.

What we can do instead is Round the numbers. Then consider numbers in the same rounding bin to be equivalent. The reason why this is just an approximation is that with a rounding bin size of 0.1, 3.09 and 3.11 would be considered different. Still, this technique is useful to throw out as many duplicates as possible. If the list gets much smaller, then a SameTest based method will be much faster as a post-processing step.

What about a canonical form to deal with permutation? Cyclically rotate each list so that the smallest element comes first. Here I'm assuming that the sublists do not contain duplicates, otherwise there may be multiple smallest elements at different positions.

Here's a function to construct a canonical form for equivalent cyclic permutations:

can1 = RotateLeft[#, Ordering[#, 1] - 1] &

Here's one for comparison with a tolerance of 0.5:

can2 = Round[#, 0.05] &

Then use DeleteDuplicatesBy:

DeleteDuplicatesBy[{{1., 2., 3., 4., 5.}, {4.01, 4.99, 1., 2.03, 3.02}}, can1@*can2]

(* {{1., 2., 3., 4., 5.}} *)


tab = RandomReal[1, {5000, n}];

DeleteDuplicatesBy[tab, can1@*can2] // Length // AbsoluteTiming
(* {0.022923, 98} *)

There's room for optimization here: the rounding can be done in one step on the whole list, exploiting vectorization.