# How to deal with this list problem?

Now, I want to write a function for some kind of list. The input list includes many integers. Take a simple example for f[x],

lst = {3, 6, 13};

f[x_ /; (x <= lst[[1]] && x >= 1 )] := 1;
f[x_ /; (x <= (lst[[1]] + lst[[2]]) && x >= (lst[[1]] + 1)  )] := 2;
f[x_ /; (x <= (lst[[1]]+lst[[2]] + lst[[3]])&& x >= (lst[[1]] + lst[[2]] + 1))] := 3;


How to write a simple and general function f[x] for a arbitrary list ?

• Are you looking for the index of the entry in the (sorted) list that is less than or equal to x? Jul 29 '16 at 13:06
• Accumulate[] might be useful. Jul 29 '16 at 13:11
• @KraZug Yes, using Accumulate[], it is more clear. Accumulate[lst]={3,9,22}. If 1=<x<=3, f[x]=1 ; if 4=<x<=9, f[x]=2; if 10=<x<=22, f[x]=3. Jul 29 '16 at 13:42
• And how do you want arguments between 3 and 4, and between 9 and 10 to be handled? Jul 29 '16 at 14:07
• Sorry, x is interger. Jul 29 '16 at 14:28

Not too hard:

idx = {3, 6, 13};
f = Function @@ {\[FormalX],
Piecewise[MapIndexed[Append[#2, #1] &,
#1 <= \[FormalX] <= #2 & @@@
TranslationTransform[{1, 0}][
Partition[FoldList[Plus, 0, Sort[idx]], 2, 1]]],
Indeterminate]};

f /@ Range[22]
{1, 1, 1, 2, 2, 2, 2, 2, 2, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3}

• Nice, as for the general case, just please remove the Sort, namely Sort[idx]--> idx. Jul 29 '16 at 15:26
• Yes, if your lists are already sorted to begin with, just remove the Sort[]. Jul 29 '16 at 15:28

I would do it this way.

makeF[data : {_Integer ..}] :=
With[{nums = Accumulate[data]},
f[n_Integer?Positive] :=
Module[{r = $Failed}, Do[If[n <= nums[[i]], r = i; Break[]], {i, Length[nums]}]; r]]  Then makeF[{3, 6, 13}]; Table[f[i], {i, 23}]  {1, 1, 1, 2, 2, 2, 2, 2, 2, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3,$Failed}

and

SeedRandom[42]; data = Sort[RandomSample[Range[99], 10]]


{4, 5, 7, 16, 33, 49, 55, 67, 82, 94}

makeF[data]; Table[f[i], {i, 50, 450, 50}]


{5, 6, 7, 8, 9, 9, 10, 10, \$Failed}

I am going to assume that all values in your input list are positive integers. This then is an interpolation with order zero, or index within a list.

Interpolation:

mkFn1[a_List] :=
ListInterpolation[
Join[{"lo"}, Range @ Length @ a, {"hi"}],
Join[{1}, Accumulate @ a, {Tr @ a + 1}]
, InterpolationOrder -> 0
] /* Quiet


Binary search (you must load Leonid's bsearchMax):

mkFn2[a_List] := Accumulate[a] /. acc_ :> ( bsearchMax[acc, #] & )


Output is a little different:

fn1 = mkFn1[{3, 6, 13}];
fn2 = mkFn2[{3, 6, 13}];

Array[fn1, 25, 0]
Array[fn2, 25, 0]

{"lo", 1, 1, 1, 2, 2, 2, 2, 2, 2, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, "hi", "hi"}

{1, 1, 1, 1, 2, 2, 2, 2, 2, 2, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 4, 4}


("lo" and "hi" are arbitrary expressions I chose.)

Both methods are very fast.