Replacing runs of identical numbers in lists

Questions
1

I have nested lists like {{2,2,7},{2,2,3,7},{3},{6,6,6,7}}
I need to replace the runs of consecutive numbers x in the sublists with Range[x-n-1, x], n being the repeat count of x.

For the above example:2,2 → 1,2; 6,6,6->4,5,6 , giving {{1,2,7},{1,2,3,7},{3},{4,5,6,7}}.
How do I achieve this (efficiently)?

2

Thank you for the explanation and code for what you want and for the example input and output. That was essential for understanding.

Try

f[v_]:=Range[First[v]-(Length[v]-1), First[v]];
g[v_]:=Flatten[Map[f,Split[v]]];
Map[g,{{2,2,7},{2,2,3,7},{3},{6,6,6,7}}]

There is a lot going on in that for someone new.

Test that on all kinds of inputs until you convince yourself that I have understood and not made any mistakes and that it is correct.

Then study the documentation for each of the functions used until you understand how and why it works. That should improve your skills and make you better prepared to solve your next problem.

3

I like Bill’s solution using Split to find the repeats-- that’s clever. Here is a pattern matching approach

In[1]:= ff[{z : Longest[PatternSequence[Repeated[x_, {2, Infinity}]]],
    y___}] := {Range[x - Length[{z}] + 1, x] /. List -> Sequence, y}

In[2]:= ff[{x_}] := {x}

In[3]:= Map[ff, {{2, 2, 7}, {2, 2, 3, 7}, {3}, {6, 6, 6, 7}}]

Out[3]= {{1, 2, 7}, {1, 2, 3, 7}, {3}, {4, 5, 6, 7}}

I made a function that matches a pattern of a repeated sequence, named z, of repeating elements, named x, and the rest of the elements, named y and then reconstructed your list. If you give it a long list it appears to be faster than using split but I am not sure exactly why.

In[9]:= data = 
  Flatten[Table[{{2, 2, 7}, {2, 2, 3, 7}, {3}, {6, 6, 6, 7}}, 10000], 
   1];

In[10]:= Map[ff, data]; // AbsoluteTiming

Out[10]= {0.144403, Null}

In[11]:= Map[g, data]; // AbsoluteTiming

Out[11]= {0.246992, Null}

Regards,

Neil

4

A variation on Neil’s solution, with a direct replacement

{{2, 2, 7}, {2, 2, 3, 7}, {3}, {6, 6, 6, 7}} /.
 {a___Integer, 
   z : Longest[PatternSequence[Repeated[x_Integer,
       {2, Infinity}]]], b___} :>
  {a, {z} - Range[Length[{z}] - 1, 0, -1], b}

It is not efficient for long runs, apparently. It will replace only the first run of repeated elements in a list.

5

I am astonished the pattern matching approaches are doing as well as they are

...
tbl={Join[Table[1,{10^6}],{2}]};
AbsoluteTiming[Map[g,tbl];]
AbsoluteTiming[Map[ff,tbl];]
AbsoluteTiming[tbl/.{a___Integer,z:Longest[PatternSequence[
  Repeated[x_Integer,{2,Infinity}]]],b___}:> {a,{z}-Range[Length[{z}]-1,0,-1],b};]

Out[1]= {0.169881,Null}
Out[2]= {0.56507,Null}
Out[3]= {0.366563,Null}

When the original message mentioned “efficiently” I assumed this implied far more repetitions and that the timing for pattern matching would grow quadratically, or even exponentially. Thus I tried to think of any single internal function that would find those repetitions without using pattern matching.

6

Bill and Gianluca,

It is interesting that Split is faster for a long run of numbers and pattern matching works better for many shorter runs of numbers. I also would have guessed that Split would be faster in all cases because it is a targeted function. Do you have any idea why?

Regards.

7

Bill, Neil Gianluca, many thanks for your help on this - I will take the time to understand and learn. Great community!
Achim