17
$\begingroup$

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.

Improve this question
$\endgroup$

5 Answers 5

Reset to default
28
$\begingroup$ 
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}}

Improve this answer
$\endgroup$
3
  • $\begingroup$ 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. $\endgroup$
    – muzzlator
    Nov 12, 2013 at 8:17
  • $\begingroup$ This is much faster than other methods too! +1 $\endgroup$
    – PlatoManiac
    Nov 12, 2013 at 8:21
  • 3
    $\begingroup$ +1 -- for those who like brevity: BinLists[v, {{-∞, ##, ∞}& @@ f}] $\endgroup$
    – Mr.Wizard
    Nov 12, 2013 at 11:31
10
$\begingroup$

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}} *)
Improve this answer
$\endgroup$
1
  • $\begingroup$ 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 $\endgroup$
    – PlatoManiac
    Nov 13, 2013 at 14:16
5
$\begingroup$

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}}

Improve this answer
$\endgroup$
1
  • $\begingroup$ 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 $\endgroup$
    – muzzlator
    Nov 12, 2013 at 7:42
4
$\begingroup$

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}}
Improve this answer
$\endgroup$
0
$\begingroup$ 
    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}}}

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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