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.

$\endgroup$
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}}

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

$\endgroup$
  • $\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 '13 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}}
$\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}}}

$\endgroup$

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.