# Accumulate second elements in sublist

I want to accumulate the second elements in each sublist identified by its first element.

{
{{1, 1}}, {{2, 1}}, {{3, 1}}, {{2, 2}}, {{5, 1}},
{{2, 1}, {3, 1}},
{{7, 1}}, {{2, 3}}, {{3, 2}},
{{2, 1}, {5, 1}},
{{11, 1}},
{{2, 2}, {3, 1}},
{{13, 1}},
{{2, 1}, {7, 1}},
{{3, 1}, {5, 1}},
{{2, 4}}, {{17, 1}},
{{2, 1}, {3, 2}}
}


For the first eight elements in my list

{{{1, 1}}, {{2, 1}}, {{3, 1}}, {{2, 2}}, {{5, 1}}, {{2, 1}, {3, 1}}, {{7, 1}}, {{2, 3}}}, ...


the desired result is

{{{1, 1}}, {{2, 1}}, {{3, 1}}, {{2, 3}}, {{5, 1}}, {{2, 4}, {3, 2}}, {{7, 1}}, {2, 7}}}, ...


In the result, the first element of each sublist will be the identification element, and the second element is just how much of the first element there are upto any given postition of the list

So for the sixth position in the list, {{2, 1}, {3, 1}}, the result would be {{2, 4}, {3, 2}}, because by that time in the list there will be an accumilation of 4 'twos' and 2 'threes'.

• Why is the 4th element of the desired result {{2,3}} and not {{2,2}}? Apr 26, 2014 at 20:03
• {{2,2}} = {{2, 2+1}}. because when you reach the fourth element you have accumulated 3 "twos" so far. the 1 comes from element two which is {{2,1}} Apr 26, 2014 at 20:17

Similar in idea to Hassler Thurston's, different in style:

acc[l_List] := Module[{reg, f},
reg[_] = 0; (* register reg[x] stores the current total for index x *)
SetAttributes[f, Listable];
{f[x_], f[a_]} ^:= {x, reg[x] = reg[x] + a};
f[l]
]


OP's example:

list = {{{1, 1}}, {{2, 1}}, {{3, 1}}, {{2, 2}}, {{5, 1}}, {{2, 1}, {3,
1}}, {{7, 1}}, {{2, 3}}, {{3, 2}}, {{2, 1}, {5, 1}}, {{11,
1}}, {{2, 2}, {3, 1}}, {{13, 1}}, {{2, 1}, {7, 1}}, {{3, 1}, {5,
1}}, {{2, 4}}, {{17, 1}}, {{2, 1}, {3, 2}}};

acc[list]
(*
{{{1, 1}}, {{2, 1}}, {{3, 1}}, {{2, 3}}, {{5, 1}}, {{2, 4}, {3, 2}},
{{7, 1}}, {{2, 7}}, {{3, 4}}, {{2, 8}, {5, 2}}, {{11, 1}},
{{2, 10}, {3, 5}}, {{13, 1}}, {{2, 11}, {7, 2}}, {{3, 6}, {5, 3}},
{{2, 15}}, {{17, 1}}, {{2, 16}, {3, 8}}}
*)

• I like this one, question, what does listable do? i have never seen it used like this before. Apr 26, 2014 at 21:55
• @Crisp Thanks! :) The attribute Listable tells Mathematica to thread over lists, like this: f[{{1, 2}, {3, 4}} first becomes {{f[1], f[2]}, {f[3], f[4]}}. Then rules (definitions) for f are applied. Apr 27, 2014 at 0:04
• oh similar to map, thanks Apr 27, 2014 at 0:14
• @Crisp There is a difference from Map: f[{1, {2, 3}}] yields {f[1], {f[2], f[3]}}. Apr 27, 2014 at 0:24

For each "first element", keep a count of its accumulation:

SecondLevelAccumulation[list_] := Module[{counts, replace},
counts = {};
replace[tuple_] := Module[{},
(* If we've never seen a "first element", initialize its count to 0 *)
If[! MemberQ[counts[[All, 1]], tuple[[1]]],
AppendTo[counts, tuple[[1]] -> 0]];
(* Then update the count to reflect the tuple's second element *)
counts = counts /. {(tuple[[1]] -> a_) :> (tuple[[1]] -> a + tuple[[2]])};
(* Finally, replace the second element of the given tuple to its accumulation *)
{tuple[[1]], tuple[[1]]/.counts}
];
(* As a last step, map the replace function to the original list at level 2 *)
Map[replace, list, {2}]
]


Result:

Michael posted a good method but it uses the Listable Attribute and UpSetDelayed (^:=) which are both fairly advanced concepts. Since I know that you are in the process of learning Mathematica let me show you that these methods are simply not necessary here.

I too will use the simple counter construct I often do(1),(2) and which is discussed in More efficient way of generating list of occurrence counts?

Fundamentally I shall be using a pattern and I shall need to restrict it(3)(4); I shall show both levelspec and purely pattern based approaches.

For all examples I have assigned your input expression to data.

levelspec in Replace:

Module[{count},
count[_] = 0;
Replace[data, {i_, n_} :> {i, count[i] += n}, {2}]
]

Module[{count},
count[_] = 0;
data /. {i_, n_Integer} :> {i, count[i] += n}
]


In addition to these examples you may find it interesting that the counter need not be localized, e.g. with Module, should you actually want to apply it globally:

count[_] = 0;
fn = # /. {i_, n_Integer} :> {i, count[i] += n} &;


Now:

fn @ {{1, 1}, {2, 1}, {3, 1}}
fn @ {{3, 4}, {5, 1}}
fn @ {{2, 2}, {3, 1}}

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

{{3, 5}, {5, 1}}

{{2, 3}, {3, 6}}


To resent the counter you can use this:

ClearAll[count]; count[_] = 0;