8
$\begingroup$

Given a list of integers like this:

z = {113, 117, 118, 119, 120, 121, 475, 476, 529, 538, 542, 543, 544}

I want a function that returns:

{113, 121, 476, 529, 538, 544}

here's the pedestrian version:

LastinSequence[a_] := Module[
  {n},
  n = {};
  Do[
   If[
     a[[i]] > (1 + a[[i - 1]]),
     n = Append[n, a[[i - 1]]]
     ];
   , {i, 2, Length@a}
   ];
  n = Append[n, Last@a];
  n
  ]

Horrible.

Can I have some suggestions to do this elegantly (and quickly!) in Wolfram language?

Also, a variation FirstinSequence[a_] that would return:

{113 117, 475, 529, 538, 542}

Thanks.

$\endgroup$
7
$\begingroup$

Use a "background" element of the desired difference in SparseArray on the differences, and "AdjacencyLists" will pick out what you desire:

Last in sequence:

positions = Append[SparseArray[Differences@z, Automatic, 1], 0]["AdjacencyLists"]
(*  {1, 6, 8, 9, 10, 13}  *)

z ~Part~ positions // Normal
(*  {113, 121, 476, 529, 538, 544}  *)

More efficient version:

Append[
 z ~Part~
   SparseArray[Rest@z - Most@z, Automatic, 1]["AdjacencyLists"],
 Last@z]

First in sequence:

Prepend[
 Reverse@z ~Part~
  Reverse[SparseArray[Rest@z - Most@z, Automatic, 1]]["AdjacencyLists"],
 First@z]
(*  {113, 117, 475, 529, 538, 542}  *)

My answer is similar to Mr.Wizard's answer to Find subsequences of consecutive integers inside a list, which asks for the essentially same thing as the OP but with the output in a different form.

$\endgroup$
  • $\begingroup$ +1 This seems to be the fastest approach so far. $\endgroup$ – rhermans Aug 2 at 15:16
  • 1
    $\begingroup$ @rhermans Thanks. "AdjacencyLists" and "NonzeroPositions" can be found in efficient solution to many similar problems on this site. (I couldn't find a duplicate, though, which surprises me.) $\endgroup$ – Michael E2 Aug 2 at 15:23
  • $\begingroup$ @Shadowray Really?: i.stack.imgur.com/KVWea.png $\endgroup$ – Michael E2 Aug 2 at 16:56
  • 2
    $\begingroup$ Note also that for vector of integers, Differences[z] may be noticably slower than Rest[z]-Most[z] $\endgroup$ – Shadowray Aug 2 at 17:44
  • $\begingroup$ @Shadowray Awesome! I knew that but had forgotten. Thanks! $\endgroup$ – Michael E2 Aug 2 at 17:52
13
$\begingroup$

You can use Split:

Last /@ Split[z, #2 == # + 1&]

{113, 121, 476, 529, 538, 544}

First /@ Split[z, #2 == # + 1&]

{113, 117, 475, 529, 538, 542}

$\endgroup$
  • $\begingroup$ Very elegant indeed. $\endgroup$ – Jonathan Kinlay Aug 2 at 16:27
5
$\begingroup$

Pick in combination with vectorized arithmetic is as fast as SparseArray:

myLastInSequenceV3[z_] := Join[Pick[Most[z], Unitize[Rest[z]-Most[z]-1], 1], {Last[z]}]

Alternative version. Shorter, but slower:

myLastInSequence[z_] := Pick[z, Join[Differences[z], {0}], Except[1, _Integer]]

Test:

LastinSequence[z] == myLastInSequence[z] == myLastInSequenceV3[z]

True

Timing for SparseArray-based solution:

data = NestList[(# + RandomInteger[9]) &, 1, 100000];

lastInSequenceSparseUpd[z_] := Append[z ~Part~SparseArray[Rest@z - Most@z, Automatic, 1]["AdjacencyLists"],Last@z]
First@RepeatedTiming[lastInSequenceSparseUpd[data];]

0.0018

This method:

First@RepeatedTiming[myLastInSequenceV3[data];]

0.0019

$\endgroup$
  • $\begingroup$ Very fast and elegant. Superb! $\endgroup$ – Jonathan Kinlay Aug 2 at 16:28
4
$\begingroup$

Solutions

This is actually twice as fast as fast as kglr's but three times slower than Shadowray's . MichaelE2 has provided the fastest answer by far.

LastInSequenceRH2[d_] := Pick[d, Inner[Unequal, d, RotateLeft[d - 1], List]]

This was my previous attempt

FirstInSequenceRH1[z_] := With[{n = Length[z]},
   Pick[z, Array[(z[[#]] != z[[Max[# - 1, 1]]] + 1) &, n]]
   ];
LastInSequenceRH1[z_] := With[{n = Length[z]},
  Pick[z, Array[(z[[Min[# + 1, n]]] != z[[#]] + 1) &, n]]
  ]


FirstInSequence[data]
(* {113, 117, 475, 529, 538, 542} *)

LastInSequence[data]
(* {113, 121, 476, 529, 538, 544} *)

Benchmark

data = NestList[(# + RandomInteger[9]) &, 1, 100000]; (* Large data       *)

First@RepeatedTiming[FirstInSequenceRH1[data];]       (* My first answer  *)
(* 0.242 *)

First@RepeatedTiming[FirstInSequencekglr[data];]      (* kglr's answer    *)
(* 0.0913 *)

First@RepeatedTiming[LastInSequenceOP[data];]         (* OP question      *)
(* 11.57 *)

First@RepeatedTiming[LastInSequenceRH2[data];]        (* My second answer *)
(* 0.049 *)

First@RepeatedTiming[LastInSequenceShadowray[data];]  (* Shadowray's      *)
(* 0.016 *)

First@RepeatedTiming[LastInSequenceMichaelE2[data];]  (* MichaelE2        *)
(* 0.0038 *)
$\endgroup$
2
$\begingroup$

Some great solutions here. I borrowed Shadowray's code and created this:

    FirstInSequence[z_] := 
 Join[{First[z]}, Pick[Rest[z], Unitize[Differences[z] - 1], 1]]

FirstInSequence[{113, 117, 118, 119, 120, 121, 475, 476, 529, 538, 
  542, 543, 544}]

{113, 117, 475, 529, 538, 542}
$\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.