# Partitioning a list of numbers the Mathematica way

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.

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

• 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. Nov 12 '13 at 8:17
• This is much faster than other methods too! +1 Nov 12 '13 at 8:21
• +1 -- for those who like brevity: BinLists[v, {{-∞, ##, ∞}& @@ f}] Nov 12 '13 at 11:31

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= {{-1}, {1, 3, 4}, {6}, {9, 10, 13}, {14, 15}} *)

• 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 Nov 13 '13 at 14:16

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

• 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 Nov 12 '13 at 7:42

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

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