How to test if a list contains consecutive integers in Mathematica?

Question

I want to test if a list contains consecutive integers.

 consQ[a_] := Module[
  {ret = True}, 
  Do[If[i > 1 && a[[i]] != a[[i - 1]] + 1, ret = False; Break[]], {i, 
  1, Length[a]}]; ret]

Although the function consQ does the job, I wonder if there is a better ( shorter, faster ) method of doing this, preferably using functional programming style.

EDIT: The function above maps lists with consecutive integers in decreasing sequence to False. I would like to change this to True.

Answer 1

Szablics' solution is probably what I'd do, but here's an alternative:

consQ[a : {___Integer}] := Most[a] + 1 === Rest[a]
consQ[_] := False

Note that these approaches differ in how they handle the empty list.

Answer 2

You could use

consQ[a_List ? (VectorQ[#, IntegerQ]&)] := Union@Differences[a] === {1}
consQ[_] = False

You may want to remove the test for integers if you know that every list you pass to it will only have integers.

EDIT: A little extra: if you use a very old version that doesn't have Differences, or wonder how to implement it,

differences[a_List] := Rest[a] - Most[a]

EDIT 2: The requested change:

consQ[a : {Integer___}] := MatchQ[Union@Differences[a], {1} | {-1} | {}]
consQ[_] = False

This works with both increasing and decreasing sequences, and gives True for a list of size 1 or 0 as well.

More generally, you can test if the list of numbers are equally spaced with something like equallySpacedQ[a_List] := Length@Union@Differences[a] == 1

Answer 3

I like the solutions by the other two, but I'd be concerned about very long lists. Consider the data

d:dat[n_Integer?Positive]:= d = {1}~Join~Range[1, n]

which has its non-sequential point at the very beginning. Setting consQ1 for Brett's and consQ2 for Szabolcs, I get

AbsoluteTiming[ #[dat[ 10000 ] ]& /@ {consQ1, consQ2}
{ {0.000110, False}, {0.001091, False} }

Or, roughly a ten times difference between the two, which stays relatively consistent with multiple trials. This time can be cut in roughly half by short-circuiting the process using NestWhile:

Clear[consQ3]
consQ3[a : {__Integer}] := 
 Module[{l = Length[a], i = 1},
   NestWhile[# + 1 &, i, 
      (#2 <= l) && a[[#1]] + 1 == a[[#2]] &, 
   2] > l
 ]

which tests each pair and only continues if they return true. The timings

AbsoluteTiming[consQ3[dat[ 10000 ]]]
{0.000059, False}

with

{0.000076, False}

for consQ. So, Brett's answer is fairly close, but occasionally, it will take twice as long.

Edit: I moved the graphs of the timing data to a Community Wiki answer.

Answer 4

I think the following is also fast, and comparing reversed lists does not take longer:

a = Range[10^7];
f[a_] := Range[Sequence @@ ##, Sign[-#[[1]] + #[[2]]]] &@{a[[1]], a[[-1]]} == a;
Timing[f[a]]
b = Reverse@a;
Timing[f[b]]

Edit

A short test for the fastests solutions so far:

a = Range[2 10^7];
Timing@consQSzab@a
Timing@consQBret@a
Timing@consQBeli@a
(*
{6.5,True}
{0.703,True}
{0.203,True}
*)

Answer 5

Fold can be used in a fairly concise expression that runs very quickly:

consQFold[a_] := (Fold[If[#2 == #1 + 1, #2, Return[False]] &, a[[1]]-1, a]; True)

Pattern-matching can be used to provide a very clear expression of intent at the cost of substantially slower performance:

consQMatch[{___, i_, j_, ___}] /; j - i != 1 := False
consQMatch[_] = True;

Edit

consQFold, as written, works in Mathematica v8.0.4 but not in earlier versions of v8 or v7. To correct this problem, there are a couple of alternatives. The first is to explicitly name the Return point:

consQFold[a_] :=
  (Fold[If[#2==#1+1, #2, Return[False,CompoundExpression]] &, a[[1]]-1, a]; True)

The second, as suggested by @Mr.Wizard, is to replace Return with Throw / Catch:

consQFold[a_] :=
  Catch[Fold[If[#2 == #1 + 1, #2, Throw[False]]&, a[[1]]-1, a]; True]

Answer 6

I am now convinced that belisarius is trying to get my goat by writing intentionally convoluted code. :-p

I would write: f = Range[##, Sign[#2 - #]]& @@ #[[{1, -1}]] == # &

Also, I believe that WReach probably intended to write something like:

consQFold[a_] := 
 Catch[
  Fold[If[#2 === # + 1, #2, Throw@False] &, a[[1]] - 1, a]; 
  True
 ]

Answer 7

Since the timing seems to be rather important. I've moved the comparisons between the various methods to this, Community Wiki, answer.

The data used are simply lists of consecutive integers, with a single non-consecutive point, and they're generated via

d : dat[n_Integer?Positive] := (d = {1}~Join~Range[1, n])
d : dat[n_Integer?Positive, p_Integer?Positive] /; p <= n := 
     Range[1, p]~Join~{p}~Join~Range[p + 1, n]

where the first form of dat[n] is equivalent to dat[n, 1]. The timing code is simple:

Clear[consQTiming]
Options[consQTiming] = {
   NonConsecutivePoints -> {10, 25, 50, 100, 250,500, 1000}};
consQTiming[fcns__, OptionPattern[]]:=
With[{rnd = RandomInteger[{1, #}, 100]}, 
  With[{fcn = #}, 
     Timing[ fcn[dat[10000, #]] & /@ rnd ][[1]]/100
  ] & /@ {fcns}
] & /@ OptionValue[NonConsecutivePoints]

It generates 100 random integers between 1 and each of {10, 25, 50, 100, 250, 500, 1000} and dat then uses each of those random numbers as the non-consecutive point in a list 10,000 elements long. Each consQ implementation is then applied to each list produced by dat, and the results are averaged. The plotting function is simply

Clear[PlotConsQTimings]
Options[PlotConsQTimings] = {
     NonConsecutivePoints -> {10, 25, 50, 100, 250, 500, 1000}};
PlotConsQTimings[timings : { _?VectorQ ..}, OptionPattern[]] :=
  ListLogLogPlot[
    Thread[{OptionValue[NonConsecutivePoints], #}] & /@ Transpose[timings],
    Frame -> True, Joined -> True, PlotMarkers -> Automatic
  ]

I timed the following functions consQSzabolcs1, consQSzabolcs2, consQBrett, consQRCollyer, consQBelisarius, consQWRFold, consQWRFold2, consQWRFold3, consQWRMatch, and MrWizard's version of consQBelisarius.

In ascending order of the left most timing: consQBelisarius, consQWizard, consQRCollyer, consQBrett, consQSzabolcs1, consQWRMatch, consQSzabolcs2, consQWRFold2, consQWRFold3,and consQWRFold.

Edit: Reran all of the functions with timeAvg (the second one) instead of Timing in consQTiming. I did still average over 100 runs, though. For the most part, there was any change, except for the lowest two where there is some variation from run to run. So, take those two lines with a grain of salt as they're timings are practically identical.