Take the 2-minute tour ×
Mathematica Stack Exchange is a question and answer site for users of Mathematica. It's 100% free, no registration required.

I have two sorted lists, one list will be called the "fences" and the other the "values"

Fences could be: $\{1, 5, 9, 14\}$

Values could be $\{-1, 1, 3, 4, 6, 9, 10, 13, 14, 15\}$

I want to partition the values list using the equivalence relation that they are between the same fence values. ($f_i \leq v < f_{i+1})$

With the example above, I would get the partition:

$$\{\{-1\}, \{1,3,4\}, \{6\}, \{9, 10, 13\}, \{14,15\}\}$$

This partitioning is quite easy using to implement using a for loop but I can't help but feel there is a better way to do it using some of the inbuilt Mathematica functions. I am not asking anyone to write the algorithm for me but to suggest which functions I should be aware of in order to do this elegantly.

share|improve this question
add comment

5 Answers

up vote 24 down vote accepted
f = {1, 5, 9, 14};
v = {-1, 1, 3, 4, 6, 9, 10, 13, 14, 15};
BinLists[v, {Join[{-Infinity}, f, {Infinity}]}]

{{-1}, {1, 3, 4}, {6}, {9, 10, 13}, {14, 15}}

share|improve this answer
    
I can't believe there is a function to do exactly what I wanted. Thanks Ray, and to the other people who answered and taught me new things along the way. –  muzzlator Nov 12 '13 at 8:17
    
This is much faster than other methods too! +1 –  PlatoManiac Nov 12 '13 at 8:21
3  
+1 -- for those who like brevity: BinLists[v, {{-∞, ##, ∞}& @@ f}] –  Mr.Wizard Nov 12 '13 at 11:31
add comment

You can try this!

fences = {1, 5, 9, 14};
vals = {-1, 1, 3, 4, 6, 9, 10, 13, 14, 15};
Select[vals, #] & /@
(Function[{x}, #1 <= x < #2] & @@@Partition[fences, 2, 1, {2, 1}, {Infinity, -Infinity}])

{{-1}, {1, 3, 4}, {6}, {9, 10, 13}, {14, 15}}

share|improve this answer
    
Thanks PlatoManiac, this uses a lot of stuff I'm unfamiliar with at the moment, which is a good thing. I'll now try and figure out what exactly you're doing –  muzzlator Nov 12 '13 at 7:42
add comment

Here's another way using SplitBy

fences = {1, 5, 9, 14};
values = {-1, 1, 3, 4, 6, 9, 10, 13, 14, 15};

Then:

SplitBy[values, Function[{z}, #1 <= z < #2] & @@@ Partition[fences, 2, 1]] // 
   Flatten[#, Length[fences] - 2] &

Which gives:

{{-1}, {1, 3, 4}, {6}, {9, 10, 13}, {14, 15}}
share|improve this answer
add comment

I'd go with the BinLists method. Were that not available, one could do well with a zero-order interpolation. These can be useful if the fence list is large, because lookup is efficient (log(n) rather than n).

I do some negating to get the continuity to be at the left end of the intervals.

interp[x_List] := 
 With[{newx = Join[{-10^8}, x, {10^8}]}, 
  Interpolation[Transpose[{Reverse[-newx], Range[Length[newx]]}], 
   InterpolationOrder -> 0]]

v = {-1, 1, 3, 4, 6, 9, 10, 13, 14, 15};
f = interp[{1, 5, 9, 14}];
SplitBy[v, f[-#] &]

(* Out[48]= {{-1}, {1, 3, 4}, {6}, {9, 10, 13}, {14, 15}} *)
share|improve this answer
    
This so much memory efficient. Tested BinList with f = Union@RandomInteger[{-10^7, 10^7}, 10^5]; v = Sort@RandomInteger[{-10^8, 10^8}, 10^7]; on a 64GB system and MMA9 aborted. Yours worked fine and took mere 56 sec..+1 –  PlatoManiac Nov 13 '13 at 14:16
add comment
    PartIt[{k_List, bb_List}] := 
     Block[{t, a = {}, st, s, b = bb, l = k, 
       bt = Partition[{-Infinity, b /. List -> Sequence, Infinity}, 2,1]},                    
      {Table[If[bt[[i, 1]] <= l[[j]] < bt[[i, 2]], a = {a, {i, l[[j]]}},j],
      {i, 1, Length[bt]}, {j, 1, Length[l]}],
       st = Partition[Flatten[a], 2], 
       s = Map[Rest[#] &, GatherBy[st, First], {2}] // Flatten[#, {3}] &};
       s]

b = {1, 5, 9, 14}; l = {-1, 1, 1, 3, 4, 6, 9, 10, 13, 14, 15};

PartIt[{l, b}]

{{{-1}, {1, 3, 4}, {6}, {9, 10, 13}, {14, 15}}}

PartIt[{l + 3, b}]

{{{2, 4}, {6, 7}, {9, 12, 13}, {16, 17, 18}}}

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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