4
$\begingroup$

Intersection works as expected in this case...

a = Range[1,5];b=Range[3,7]; Intersection[a,b]

giving...

{3,4,5}

However if I expand the concept of sameness using SameTest to this...

Intersection[a,b, SameTest->(Abs[#1-#2]<=1&)]

I get the slightly puzzling result of...

{5}

I was expecting to see something like {2,3,4,5,6}.

I thought this might be Union running within Intersection but...

Union[{2,3,4,5,6},SameTest->(Abs[#1-#2]<=1&)]

gives...

{2,4,6}

So I am at something of a loss.

Part II

Given the comments below, clearly Intersection isn't going to give me what I want, which is

  1. every element from list a that is within some given distance of any element within list b. and
  2. every element from list b that is within some given distance of any element within list a.

I can do this with something ugly like...

Union[Flatten[Select[Apply[Join, Outer[List, a, b]], Abs[{1, -1}.#] <= 1 &]]]

But the Outer is likely to bite hard with big lists.

Any improvements spring to mind?

Improve this question
$\endgroup$
4
  • 2
    $\begingroup$ In your first example, there is a typo, you use #1 in both cases. In general, your sameness function is not transitive (meaning that from a ~ b and b ~ c does not follow a ~ c in general, where I used ~ to denote sameness function), so you may expect different results depending on the order in which things are compared. So, you should either use a transitive sameness function, or rely on a particular order of comparisons, if you want predictable and deterministic results. $\endgroup$ Commented Oct 9, 2014 at 15:12
  • 2
    $\begingroup$ To add to what @Leonid Shifrin noted about the typo, once you have one element, all others will be deemed "SameQ". Hence that singleton result. $\endgroup$ Commented Oct 9, 2014 at 15:17
  • $\begingroup$ @LeonidShifrin - Thank you, that does make sense. I suppose the next question is... how do I get what I actually want? $\endgroup$ Commented Oct 9, 2014 at 15:35
  • 2
    $\begingroup$ @Ymareth Well, the first step would be to clearly formulate what you actually want. It is clear that for non-transitive sameness function, the result will depend on the order of the elements in your lists. OTOH, functions like Complement, Intersection, Union etc. treat lists as sets. Which means that they are probably inappropriate for your needs, unless you manage to reformulate your problem to use a transitive sameness function. $\endgroup$ Commented Oct 9, 2014 at 15:39

2 Answers 2

Reset to default
4
$\begingroup$

Addressing Part II here is a fairly efficient method using Interval and IntervalMemberQ:

distanceInt[a_, b_, d_: 1] := Module[{toInt, pick}, toInt = Interval @@ ({# - d, # + d}\[Transpose]) &; pick = Pick[#, toInt[#2] ~IntervalMemberQ~ #] &; pick[a, b] ⋃ pick[b, a] ]

A single timing compared to your method:

SeedRandom[1] {a, b} = List @@ RandomInteger[99999, {2, 1000}]; Union[Flatten[Select[Apply[Join, Outer[List, a, b]], Abs[{1, -1}.#] <= 1 &]]] // Length // AbsoluteTiming 
{1.623093, 50} 
distanceInt[a, b, 1] // Length // AbsoluteTiming 
{0.003000, 50}
Improve this answer
$\endgroup$
1
  • $\begingroup$ @Ymareth You're welcome. :-) $\endgroup$ Commented Oct 10, 2014 at 17:33
1
$\begingroup$

When lists are like these.

a = {1, 4, 6, 11, 12}; b = {0, 1, 5, 10};

My try is this.

f[p_, q_, n_: 1] := Table[Intersection[p + i, q], {i, -n, n}] {f[a, b], f[b, a]} // Flatten // Union

{0, 1, 4, 5, 6, 10, 11}

Timing

distanceInt[a, b, 1] // Length // AbsoluteTiming

{0.015600, 50}

{f[a, b], f[b, a]} // Flatten // Union // Length // AbsoluteTiming

{0., 50}

Improve this answer
$\endgroup$
5
  • $\begingroup$ Nice idea, but I think that the integer lists were only an example in which case this enumeration will not be robust. Even for integers the operation will slow as n grows. Consider e.g. {a, b} = List @@ RandomInteger[1*^7, {2, 1000}]; and then distanceInt[a, b, 2500] $\endgroup$ Commented Oct 9, 2014 at 18:29
  • $\begingroup$ @Mr.Wizard You right. It is just show that my code is not much slow. $\endgroup$ Commented Oct 9, 2014 at 18:36
  • 1
    $\begingroup$ @Mr.Wizard Just I tried with simple code.:) $\endgroup$ Commented Oct 9, 2014 at 18:37
  • $\begingroup$ And for the example the OP gave it works just fine. Sorry for being overly critical. Sometimes I focus too much on my own assumptions about the nature of the question. $\endgroup$ Commented Oct 9, 2014 at 18:43
  • $\begingroup$ FYI - The actual use case concerns lists of times (represented by "HH:MM:SS.sss" strings, Mathematica's TimeObjects being woefully slow as yet) where I'm looking for nearly simultaneous events. I convert these to Reals using {3600, 60, 1}.ToExpression[StringSplit[#, ":"]]&. This is a lot faster than using DateDifference. $\endgroup$ Commented Oct 10, 2014 at 10:52

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.