8
$\begingroup$

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'.

$\endgroup$
  • $\begingroup$ Why is the 4th element of the desired result {{2,3}} and not {{2,2}}? $\endgroup$ – Ymareth Apr 26 '14 at 20:03
  • $\begingroup$ {{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}} $\endgroup$ – Crisp Apr 26 '14 at 20:17
7
$\begingroup$

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}}}
*)
$\endgroup$
  • $\begingroup$ I like this one, question, what does listable do? i have never seen it used like this before. $\endgroup$ – Crisp Apr 26 '14 at 21:55
  • $\begingroup$ @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. $\endgroup$ – Michael E2 Apr 27 '14 at 0:04
  • $\begingroup$ oh similar to map, thanks $\endgroup$ – Crisp Apr 27 '14 at 0:14
  • $\begingroup$ @Crisp There is a difference from Map: f[{1, {2, 3}}] yields {f[1], {f[2], f[3]}}. $\endgroup$ – Michael E2 Apr 27 '14 at 0:24
5
$\begingroup$

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:

Results

$\endgroup$
2
$\begingroup$

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

Pattern only in ReplaceAll:

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;
$\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.