Take the 2-minute tour ×
Mathematica Stack Exchange is a question and answer site for users of Mathematica. It's 100% free, no registration required.

I want to program a function that counts the successive positions with the same value:

In[]= ConsecutiveValues[{1, 1, 1, 1, 2, 2, 1, 0}]
Out[]= {4, 2, 1, 1}

In fact, I can program this using loops and such, but I have the feeling that there is a nicer, more Mathematicaesque way to do it.

Thanks!

share|improve this question

3 Answers 3

Most straightforward method

Use Split:

consecutiveValues[l_List] := Length /@ Split[l]

This is both fast and simple

Using linked lists

Note that patterns are by themselves not necessarily very slow, if constructed efficiently. Below is a recursive version, based on linked lists, which is about 5 times slower than the above Split-based version on large lists (which is not bad for purely top-level implementation), but has correct asymptotic complexity (linear):

toLinkedList[l_List] := Fold[{#2, #1} &, {}, Reverse@l]

Clear[cValsRec];
cValsRec[l_List] := cValsRec[toLinkedList@l, {{}, 0}];
cValsRec[{}, counts_] := Most@Flatten[counts];
cValsRec[{val_, tail : {val_, _List}}, {prev_List, count_}] :=
    cValsRec[tail, {prev, count + 1}];
cValsRec[{val_, tail_List}, {prev_List, count_}] :=
    cValsRec[tail, {{prev, count + 1}, 0}];

You use it as

cValsRec[{1, 1, 1, 1, 2, 2, 1, 0}]

The above function is properly tail-recursive in Mathematica sense. Note that for large lists, you may want to wrap the call in Block[{$IterationLimit = Infinity},...].

This is not the first time that I promote the use of linked lists. In my opinion, they are underused in Mathematica. Generally, they can very often be used for problems involving ragged lists, and /or the need of some look-ahead behavior in list processing, as an idiomatic (and often faster) alternative to procedural loops. The advantage of linked lists is that they bring reasonable (for the top-level code), and easily predictable performance, can be coded straightforwardly, and the code is declarative (easy to understand). And in some cases, the use of linked lists leads to dramatic performance improvements.

The need for speed

It is possible to beat Split-based method, performance-wise. Here is how:

ClearAll[cvalsAlt];
cvalsAlt[l_List] :=
 With[{pos = 
         Flatten[
            SparseArray[
               Unitize[Subtract @@ Partition[l, Length[l] - 1, 1]]
            ]["NonzeroPositions"]]
        },
    Differences[{0}~Join~pos~Join~{Length[l]}]
 ]

According to my benchmarks, this method is 4-5 times faster than the one based on Split.

share|improve this answer
    
Well, that easy! Thanks! –  Michaël Jun 10 '12 at 23:43
1  
@Michaël Thanks for the accept, but generally, it is a good idea to wait for some time, to encourage more answers. There are often many ways to do things in Mathematica, and the first working answer isn't necessarily the best one (you can always uncheck the currently accepted answer and accept another one, b.t.w.) –  Leonid Shifrin Jun 10 '12 at 23:46

I cannot beat Split but if that function did not exist I might use:

f=
 Reap[
   Fold[If[# == #2, i++; #, Sow[i]; i = 1; #2] &, "!", # ~Append~ "!"]
 ][[2, 1, 2;;]] &;

f @ {1, 1, 1, 1, 2, 2, 1, 0}
{4, 2, 1, 1}

"!" is an arbitrary object that will not appear in the list.

Or, taking a pattern based approach at the expense of performance I might use:

f = # /. {x : Longest[p_ ..], y___} :> Prepend[f@{y}, Length@{x}] &;

f @ {1, 1, 1, 1, 2, 2, 1, 0}
{4, 2, 1, 1}
share|improve this answer
    
Very nice, particularly the last version. +1. –  Leonid Shifrin Jun 11 '12 at 9:37

Leonid's answer is very straightforward and I doubt it can be beat. Nevertheless, here's another approach using pattern matching and rule replacements to get the same result:

consecutiveValues[l_List] := l /. x_Integer :> {x, 1} //. 
    {h___, {x_, i_}, {x_, j_}, t___} :> {h, {x, i + j}, t} /. {_, x_} :> x
share|improve this answer
2  
+1. In fact, almost exactly the same code, written by Frank Zizza to solve the run-length encoding problem, won the programming contest at 1990 Mathematica conference. –  Leonid Shifrin Jun 11 '12 at 9:35
    
Actually, in terms of speed, Split-based method can be beat, see my edit. –  Leonid Shifrin Jun 11 '12 at 10:41

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.