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$
  • 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$ – Leonid Shifrin Oct 9 '14 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$ – Daniel Lichtblau Oct 9 '14 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$ – Ymareth Oct 9 '14 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$ – Leonid Shifrin Oct 9 '14 at 15:39
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$
  • $\begingroup$ Ideal, thank you. $\endgroup$ – Ymareth Oct 10 '14 at 9:02
  • $\begingroup$ @Ymareth You're welcome. :-) $\endgroup$ – Mr.Wizard♦ Oct 10 '14 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$
  • $\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$ – Mr.Wizard♦ Oct 9 '14 at 18:29
  • $\begingroup$ @Mr.Wizard You right. It is just show that my code is not much slow. $\endgroup$ – Junho Lee Oct 9 '14 at 18:36
  • 1
    $\begingroup$ @Mr.Wizard Just I tried with simple code.:) $\endgroup$ – Junho Lee Oct 9 '14 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$ – Mr.Wizard♦ Oct 9 '14 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$ – Ymareth Oct 10 '14 at 10:52

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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