# Locating similar points between two lists

Let's create some sample data

n = 1000;
data1 = Table[{RandomReal[{-1, 1}], RandomReal[{-1, 1}],
RandomReal[{-1, 1}], RandomReal[{-1, 1}], RandomReal[{-1, 1}],
RandomReal[{-1, 1}]}, {i, 1, n}]
data2 = Table[{RandomReal[{-1, 1}], RandomReal[{-1, 1}],
RandomReal[{-1, 1}], RandomReal[{-1, 1}], RandomReal[{-1, 1}],
RandomReal[{-1, 1}]}, {i, 1, n}]


As you can see, we have two data lists, data1 and data2 which contain six columns of real numbers. Let's call $x_i, y_i, z_i, p_{xi}, p_{yi}, p_{zi}$ the elements of data1 and $x_j, y_j, z_j, p_{xj}, p_{yj}, p_{zj}$ the elements of data2.

My scope is to find if there are any identical points between the two lists and which are exactly these duplicate points. By the term "identical" I refer to points for which

$|x_i - x_j| < 10^{-5}$, $|z_i - z_j| < 10^{-5}$, $|p_{xi} - p_{xj}| < 10^{-5}$, $|p_{zi} - p_{zj}| < 10^{-5}$, simultaneously. Note that we are not interested about $y$ and $p_y$.

Any suggestions?

I use version 9.0 of MMA.

• Note that RandomReal[{-1, 1}, {1000, 6}] will generate your fake data a bit more compactly. – MarcoB Apr 25 '18 at 16:34

Use Nearest. For example, with the data:

SeedRandom[1]
list1 = RandomReal[1, {10^4, 4}];
list2 = RandomReal[1, {10^4, 4}];


You can define a NearestFunction:

nf = Nearest[list1->"Index", DistanceFunction->ChessboardDistance];


ChessboardDistance measures the distance between 2 points assuming the distance is covered by a Queen (or King). Now, with 10^4 random points it is extremely unlikely that any 2 points have a ChessboardDistance of 10^-5 or less. For the above data, a distance that produces "identical" points is something on the order of 10^-2:

res = nf[list2, {All, 10^-2}];
identical = Pick[list2, Length /@ res, Except[0, _Integer]]


{{0.685292, 0.397605, 0.475159, 0.328691}, {0.335736, 0.280756, 0.407469, 0.533887}, {0.912073, 0.685974, 0.952897, 0.271151}, {0.326838, 0.504337, 0.125602, 0.314291}, {0.676946, 0.110687, 0.939404, 0.492283}, {0.747907, 0.385783, 0.230076, 0.198834}, {0.440763, 0.351743, 0.492735, 0.207811}, {0.539763, 0.309531, 0.115746, 0.700582}, {0.935517, 0.227098, 0.640445, 0.400848}, {0.400585, 0.0229188, 0.652013, 0.652141}, {0.335365, 0.111325, 0.664795, 0.17639}, {0.43019, 0.163319, 0.075704, 0.67404}, {0.661021, 0.03022, 0.20255, 0.372881}}

Let's compare the identical elements:

Thread[{list1[[#]]& /@ DeleteCases[res, {}], identical}]


{{{{0.689472, 0.40506, 0.473408, 0.332559}}, {0.685292, 0.397605, 0.475159, 0.328691}}, {{{0.342825, 0.276343, 0.408599, 0.525442}}, {0.335736, 0.280756, 0.407469, 0.533887}}, {{{0.902177, 0.68945, 0.94329, 0.265362}}, {0.912073, 0.685974, 0.952897, 0.271151}}, {{{0.323412, 0.510421, 0.121472, 0.317904}}, {0.326838, 0.504337, 0.125602, 0.314291}}, {{{0.679234, 0.120186, 0.933942, 0.490366}}, {0.676946, 0.110687, 0.939404, 0.492283}}, {{{0.748489, 0.393792, 0.232312, 0.198016}}, {0.747907, 0.385783, 0.230076, 0.198834}}, {{{0.447516, 0.350137, 0.49212, 0.211425}}, {0.440763, 0.351743, 0.492735, 0.207811}}, {{{0.549304, 0.318568, 0.108417, 0.702578}}, {0.539763, 0.309531, 0.115746, 0.700582}}, {{{0.93924, 0.224546, 0.635966, 0.398112}}, {0.935517, 0.227098, 0.640445, 0.400848}}, {{{0.409333, 0.0203513, 0.644093, 0.654824}}, {0.400585, 0.0229188, 0.652013, 0.652141}}, {{{0.342227, 0.111995, 0.663345, 0.178174}}, {0.335365, 0.111325, 0.664795, 0.17639}}, {{{0.424369, 0.157971, 0.0763675, 0.678569}}, {0.43019, 0.163319, 0.075704, 0.67404}}, {{{0.663532, 0.0398141, 0.193906, 0.369557}}, {0.661021, 0.03022, 0.20255, 0.372881}}}

Looks identical based on the distance measure .01.

• When I evaluate nf I get the following error: Nearest::near1: "\!({{0.8173894901710712, 0.11141961113123644, 0.7895259946338515, 0.18780314670602638}, {0.24136096745765045, 0.06573875950878105, 0.5422466205096241, 0.23115450673602744}, {0.3960060815485871, 0.7004737819422449, 0.21182597905412748, 0.748656881482948}, <<46>>, {0.17990176055342078, 0.035655750518962304, 0.2653318875513011, 0.8421484523408236}, <<9950>>} -> \"Index\") is neither a list of real points nor a valid list of rules" Note that I use version 9. – Vaggelis_Z Apr 25 '18 at 17:33
• In version 9 use Nearest[list->Automatic, DistanceFunction->ChessboardDistance], but this will be very slow. Non-default DistanceFunction specifications in M9 are slow, but in M10 they are just as fast as the default. I recommend trying to upgrade to at least M10. – Carl Woll Apr 25 '18 at 17:43

You can do the following:

First, define the matching condition:

matchQ[point1_List, point2_List, threshold_] :=
Abs[Part[point1, 1] - Part[point2, 1]] < threshold &&
Abs[Part[point1, 3] - Part[point2, 3]] < threshold &&
Abs[Part[point1, 4] - Part[point2, 4]] < threshold &&
Abs[Part[point1, 6] - Part[point2, 6]] < threshold;


Then you can use the following function to take cross product of the two lists and then select those pair of 6-tuples that match matchQ.

IdenticalList[l1_List, l2_List,threshold_] :=
Select[Tuples[{l1, l2}], matchQ[#[[1]], #[[2]],threshold] &];


IdenticalList[data1,data2,10^(-5)]

• It seems that when the lists contain a large number of data (try n = 10000) the code aborts due to insufficient memory ... General::nomem: The current computation was aborted because there was insufficient memory available to complete the computation. Is there any trick to overcome this issue? – Vaggelis_Z Apr 25 '18 at 16:48
• @Vaggelis_Z I cannot see any way but to check all the $n^2$ pairs by brute force. – Subho Apr 25 '18 at 16:55
• What exactly do you propose? Could you please explain the "brute force" approach? – Vaggelis_Z Apr 25 '18 at 16:58

Since you only want to know IF there are duplicates according to your criteria, but it seems that you do not want to know which are the "duplicates", I would use DuplicateFreeQ on a new list generated from removing duplicates from each of the original ones, then joining the two resulting lists. You also need an appropriate distance/test function that embodies your criteria.

DuplicateFreeQ was introduced after v.9; nevertheless, its functionality is equivalent to:

DuplicateFreeQ[list] --> SameQ[list, DeleteDuplicates[list]]


and DeleteDuplicates takes a test function to decide whether two elements are to be considered the same.

So here we go. withintolerance is the pairwise test function to test whether two points are within your specified tolerance and should be considered the same. duplicatefreeq reproduces the functionality of the built in DuplicateFreeQ for older versions.

Clear[withintolerance, duplicatefreeq]

withintolerance[a_, b_] := And @@
Thread[Abs@*Subtract @@@ (Transpose[{a, b}][[{1, 3, 4, 6}]]) < 1*^-5]

duplicatefreeq[list_] := SameQ[list, DeleteDuplicates[list, withintolerance]]


Let's generate some data:

data1 = RandomReal[{-1, 1}, {1000, 6}];
data2 = RandomReal[{-1, 1}, {1000, 6}];

duplicatefreeq[
Join @@ (DeleteDuplicates[#, withintolerance] & /@ {data1, data2})
]
(* False *)


This indicates that, indeed, there are values that are considered equal according to your criteria.

To list the duplicated points, you can still use the withintolerance function and the combined list generated above, then use Tally to count the frequency of each point, and select those that appear more than once in the combined list.

Join @@ (DeleteDuplicates[#, withintolerance] & /@ {data1, data2});
Cases[Tally[%, withintolerance], {l_List, n_} /; n > 1 :> l]

(* Out: {{-0.966795,-0.666258,0.596014,-0.558378,-0.814469,-0.585457},<<37>>,{<<1>>}} *)

• Actually, I do want to know which are the duplicates! – Vaggelis_Z Apr 25 '18 at 17:19
• @Vaggelis_Z Well, you probably want to adjust your question then, because you asked "IF" there are duplicates. Do you want a function that returns each duplicate value then? – MarcoB Apr 25 '18 at 17:21
• See my edit. Yes, I want a function returning all the duplicate points within the tolerance. – Vaggelis_Z Apr 25 '18 at 17:22
• @Vaggelis_Z Take a look at my addition at the end of the answer. Would that work? – MarcoB Apr 25 '18 at 17:28
• I tested it to my actual data and the results are not correct. The reported duplicates have common x but the values of z, p_x and p_z are not equal (their differences are much higher than the tolerance). – Vaggelis_Z Apr 25 '18 at 17:48