8
$\begingroup$

I have a list of integers. The first n members of the lists will, when added to each other, will result in the n + 1 st member of the list. . I would like to replace each list with the accumulated sum when a match occurs; if there is more than one match (e.g. lis5), replace the list with the numerically largest match.

lis1 = {8,2,3,9,22} res1 = 22

lis2 = {9,11,21,3,44,12,3} res2 = 44

lis3 = {3,8,2,1,12,26} res3 = 26

lis4 = {8,4,6,2,9,11,40,3} res4 = 40

lis5 = {3,7,10,2,14,36,4} res5 = 36 (not 10)

Testing recursively the accumulated sum against each succeeding element until a match is found. Thanks for any ideas...

$\endgroup$
10
$\begingroup$

This function should do:

f = x \[Function] Last[Intersection[x, Accumulate[x]]]

(Note that Intersection automatically orders lists, so we merely have to take the last element of the intersection.)

Testing:

lists = {{8, 2, 3, 9, 22},
   {9, 11, 21, 3, 44, 12, 3},
   {3, 8, 2, 1, 12, 26},
   {8, 4, 6, 2, 9, 11, 40, 3},
   {3, 7, 10, 2, 14, 36, 4}
   };
f /@ lists

{22, 44, 26, 40, 36}

Edit

kglr pointed out that the equality of position might be necessary for a match. In this case, the following function might be what you are looking for.

g = x \[Function] Max[Pick[Rest[x], Unitize[Accumulate[Most[x]] - Rest[x]], 0]]

We obtain

g /@ lists

{22, 44, 26, 40, 36}

and with kglr's lists2

lists2 = {{22, 2, 9, 8, 3},
   {9, 3, 12, 44, 3, 21, 11},
   {12, 8, 2, 3, 1, 26},
   {2, 11, 6, 8, 4, 9, 3, 40},
   {3, 10, 4, 7, 14, 36, 2}
   };
g /@ lists2

{-∞, 12, 26, -∞, -∞}

(And yes, the supremum of an empty set is $-\infty$.)

$\endgroup$
  • $\begingroup$ Henrik, Intersection[x, Accumulate[x]] does not guarantee the requirement that positions match. $\endgroup$ – kglr May 29 '18 at 6:14
  • $\begingroup$ @kglr Good point! Maybe edit resolves that... $\endgroup$ – Henrik Schumacher May 29 '18 at 6:37
  • 1
    $\begingroup$ Since I like syntactic brevity: f = Last[# ⋂ Accumulate[#]] & $\endgroup$ – Mr.Wizard May 29 '18 at 11:32
4
$\begingroup$

Another approach is to recognize that what you want is the max value in each list. Hence:

lists = {{8, 2, 3, 9, 22}, 
         {9, 11, 21, 3, 44, 12, 3}, 
         {3, 8, 2, 1, 12, 26}, 
         {8, 4, 6, 2, 9, 11, 40, 3}, 
         {3, 7, 10, 2, 14, 36, 4}};
 Max @@@ lists
{22, 44, 26, 40, 36}
$\endgroup$
  • $\begingroup$ I should have made the question more general: the last element in the list could be a higher number than the preceding, e.g. lis6 = {3,7,10,17,37,40} which requires Henrik's solution. $\endgroup$ – Suite401 May 29 '18 at 3:41
4
$\begingroup$
f1 = Module[{i = Length@#, a = #, b = Accumulate @ #}, 
    While[a[[i]] - b[[--i]] != 0 && i > 0]; ; If[i == 0, {}, a[[i + 1]]]] &;
f2 = Module[{a = Reverse @ Accumulate @ Most @ #, b = Reverse @ Rest @ #, l}, 
    l = LengthWhile[a - b, # != 0 &]; If[l == Length@a, {}, a[[1 + l]]]] &;

Examples:

lists = {{8, 2, 3, 9, 22},
   {9, 11, 21, 3, 44, 12, 3},
   {3, 8, 2, 1, 12, 26},
   {8, 4, 6, 2, 9, 11, 40, 3},
   {3, 7, 10, 2, 14, 36, 4}};

{f1 /@ lists, f2 /@ lists}

{{22, 44, 26, 40, 36}, {22, 44, 26, 40, 36}}

SeedRandom[1]
lists2 = RandomSample/@lists

{{22, 2, 9, 8, 3},
{9, 3, 12, 44, 3, 21, 11},
{12, 8, 2, 3, 1, 26},
{2, 11, 6, 8, 4, 9, 3, 40},
{3, 10, 4, 7, 14, 36, 2}}

{f1 /@ lists2, f2 /@ lists2}

{{{}, 12, 26, {}, {}}, {{}, 12, 26, {}, {}}}

$\endgroup$
3
$\begingroup$
(Pick[#, (#1 - #2) & @@@ FoldList[{#2, Total@Flatten@{#1}} &, #],0][[-1]]) & /@ lists

{22, 44, 26, 40, 36}

Original Answer

'Borrowing' from bill s

Max@Cases[FoldList[{#2, Total@Flatten@{#1}} &, lst5], {x_, x_} :> x]

36

lists = {{8, 2, 3, 9, 22}, {9, 11, 21, 3, 44, 12, 3}, {3, 8, 2, 1, 12,
 26}, {8, 4, 6, 2, 9, 11, 40, 3}, {3, 7, 10, 2, 14, 36, 4}};

Max@Cases[FoldList[{#2, Total@Flatten@{#1}} &, #], {x_, x_} :> x] & /@ lists

{22, 44, 26, 40, 36}

$\endgroup$
  • $\begingroup$ @Mr.Wizard. Thank you for that nice edit! $\endgroup$ – user1066 May 29 '18 at 12:21

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.