4
$\begingroup$

Can you help me to find and count sub-sequences of consecutive, identical integer members of a long list (at least 1000 members)? By sub-sequences I mean runs like 0, 0 or 5, 5, 5.

$\endgroup$
2
  • $\begingroup$ Welcome to Mathematica.SE! I hope you will become a regular contributor. To get started, 1) take the introductory tour now, 2) when you see good questions and answers, vote them up by clicking the gray triangles, because the credibility of the system is based on the reputation gained by users sharing their knowledge, 3) remember to accept the answer, if any, that solves your problem, by clicking the checkmark sign, and 4) give help too, by answering questions in your areas of expertise. $\endgroup$
    – bbgodfrey
    Commented Oct 2, 2015 at 13:08
  • $\begingroup$ What is "at least"? The answers so far are sufficient for lists of a few thousand or so (unless the operation will be done repeatedly in some tight loop, then even that will add up). For large lists they can be significantly beaten. $\endgroup$
    – ciao
    Commented Oct 3, 2015 at 2:39

4 Answers 4

7
$\begingroup$

Modifying the approach by @bbgodfrey one might also use Tally to count all patterns:

list = RandomInteger[{0, 9}, 1000]; (* some integers *)  

patternCount = Tally @ Split @ list (* returns a list of {{integer..},count} *)

Now we just take the ones that interest us (e.g. more than one integer):

patternCount2plus = Cases[ 
    patternCount, 
    { { Repeated[ _Integer, {2, Infinity} ] }, count_Integer }
]

(* { {{3,3}, 11}, {{4,4}, 8}, ... }*)

This might be sorted by the elements that are repeated and formatted more nicely:

patternCount2plusSorted = SortBy[ patternCount2plus, #[[1,1]]& ];

Grid[
    patternCount2plusSorted,
    Alignment -> Right,
    Background -> { None, { {LightBlue, White} } }, (* alternate rows *)
    Frame -> True
]

Giving something like this:

Output

$\endgroup$
2
  • 1
    $\begingroup$ Perhaps, your second line of code should be patternCount = Tally@Split@list, and your third patternCount2plus = Cases[patternCount, {{Repeated[_Integer, {2, Infinity}]}, count_Integer}]. $\endgroup$
    – bbgodfrey
    Commented Oct 2, 2015 at 17:38
  • $\begingroup$ @bbgodfrey Yes, of course, thank you. That happens when one copies like the monks in medieval times. ;-) $\endgroup$
    – gwr
    Commented Oct 2, 2015 at 18:39
5
$\begingroup$

If the List is named lst, then

rept = Cases[Split[lst], z_ :> z /; Length[z] > 1]

finds all runs of repeated integers, and

Length[rept]

finds the number of them. Applied to

lst = {1, 2, 3, 3, 4, 5, 5, 5, 6, 4}

they give

(* {{3, 3}, {5, 5, 5}} *)
(* 2 *)

If only the number of repeated runs is desired, then

Count[Split[lst], z_ /; Length[z] > 1]

can be used. For instance,

SeedRandom[5];
Table[Count[Split[RandomInteger[{0, 9}, 10^i]], z_ /; Length[z] > 1], {i, 1, 6}]
(* {2, 9, 93, 890, 9063, 90270} *)
$\endgroup$
2
$\begingroup$
SeedRandom[0];
list = RandomInteger[{0, 9}, 1000];

Tally @ Cases[{_, __}] @ Split[list]

{{{5, 5}, 4}, {{0, 0}, 10}, {{7, 7}, 9}, {{6, 6}, 12}, {{3, 3}, 14}, {{9, 9}, 9}, {{1, 1}, 12}, {{4, 4}, 10}, {{6, 6, 6}, 2}, {{8, 8}, 6}, {{2, 2}, 8}, {{0, 0, 0}, 1}, {{9, 9, 9}, 1}, {{8, 8, 8, 8}, 1}, {{7, 7, 7}, 1}}

Alternatively, we could use

Tally @ SequenceCases[list, {a_, a_ ..}]

but it's rather slow

$\endgroup$
1
$\begingroup$

An alternative is to use SequenceSplit, but it is quite slow compared to @eldo's proposals with SequenceCases and Split. This way, grabbing @eldo's list and SequenceSplit we get:

SeedRandom[0];
list = RandomInteger[{0, 9}, 1000];

Tally@Cases[{a_, a_ ..}]@SequenceSplit[list, s : {a_, a_ ..} :> s]

(*{{{5, 5}, 4}, {{0, 0}, 10}, {{7, 7}, 9}, {{6, 6}, 12}, {{3, 3}, 14}, 
   {{9, 9}, 9}, {{1, 1}, 12}, {{4, 4}, 10}, {{6, 6, 6}, 2}, 
   {{8, 8}, 6}, {{2, 2}, 8}, {{0, 0, 0}, 1}, {{9, 9, 9}, 1}, 
   {{8, 8, 8, 8}, 1}, {{7, 7, 7}, 1}}*)

A slightly faster version can be built using Reap and Sow:

CountConsecutive[lst_?VectorQ] := Tally[
    Part[
            Reap[
                Module[{temp = {}},
                    Do[
                        If[
                                And[
                                    Greater[i, 1],
                                    Equal[lst[[i]], Part[lst, i - 1]]
                                ],
                                AppendTo[temp, lst[[i]]],
                                If[
                                    Greater[Length @ temp, 0],
                                    AppendTo[temp, Part[lst, i - 1]];
                                    Sow[temp, "temp"];
                                    temp = {}
                                ];
                            ];
                    ,
                        {i, Length @ lst}
                    ];
                    If[Greater[Length @ temp, 0],
                        AppendTo[temp, lst[[-1]]];
                        Sow[temp, "temp"]
                    ];
                ],
                "temp"
            ],
            2, 1
        ]
   ];

On my turtle machine I get the following:

CountConsecutive[list] // AbsoluteTiming

(*{0.0047334, {{{5, 5}, 4}, {{0, 0}, 10}, {{7, 7}, 9}, {{6, 6}, 12}, {{3, 3}, 14}, 
             {{9, 9}, 9}, {{1, 1}, 12}, {{4, 4}, 10}, {{6, 6, 6}, 2}, {{8, 8}, 6}, 
             {{2, 2}, 8}, {{0, 0, 0}, 1}, {{9, 9, 9}, 1}, {{8, 8, 8, 8}, 1}, 
             {{7, 7, 7}, 1}}}*)

A slightly faster alternative is to define AdjacentDuplicates and use Select:

AdjacentDuplicates = Most@# === Rest@# && Length[#] > 1 &;

Tally@Select[AdjacentDuplicates]@Split[list] // AbsoluteTiming

(*{0.002888, {{{5, 5}, 4}, {{0, 0}, 10}, {{7, 7}, 9}, {{6, 6}, 12}, {{3, 3}, 14}, 
             {{9, 9}, 9}, {{1, 1}, 12}, {{4, 4}, 10}, {{6, 6, 6}, 2}, {{8, 8}, 6}, 
             {{2, 2}, 8}, {{0, 0, 0}, 1}, {{9, 9, 9}, 1}, {{8, 8, 8, 8}, 1}, 
             {{7, 7, 7}, 1}}}*)
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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