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.
x
is close toy
andy
is close toz
, butx
is not close toz
what should be returned?y
? orx
andz
? Do you just want a list where 1) all members of the input list are close to a member of the output list; and 2) no members of the output list are close together? $\endgroup$ – mikado Oct 8 '16 at 14:41x
,y
orz
. I want a list were no member is close to another or its cyclic permutations, so 2). In other words, two elements of the output should not be cyclic permutations of each other. $\endgroup$ – anderstood Oct 8 '16 at 14:46cyclicPermutationQ[v1_, v2_] := Length[v1] == Length[v2] && MatchQ[Quiet[FindPermutation[v1, v2], FindPermutation::norel], Cycles[{v : {__Integer} /; Length[v] == 5}]]
. $\endgroup$ – J. M.'s ennui♦ Oct 8 '16 at 15:15