如何测试列表是否包含Mathematica中的连续整数？

Question

我想测试列表是否包含连续的整数.

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

尽管函数consQ完成了这项工作,但我想知道是否有更好(更短,更快)的方法,最好使用函数式编程风格.

编辑: 上面的函数将连续整数的列表以递减顺序映射到False.我想将此更改为True.

Answer 1

Szablics的解决方案可能就是我要做的,但这里有一个替代方案:

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

请注意,这些方法在处理空列表方面有所不同.

Answer 2

你可以用

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

如果您知道传递给它的每个列表只有整数,则可能需要删除整数测试.

编辑: 一点额外:如果你使用一个没有的旧版本Differences,或者想知道如何实现它,

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

编辑2:要求的更改:

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

这适用于递增和递减序列,并且还提供True大小为1或0的列表.

更一般地说,您可以测试数字列表是否等间隔 equallySpacedQ[a_List] := Length@Union@Differences[a] == 1

Answer 3

我喜欢其他两个解决方案,但我会关注很长的列表.考虑数据

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

它在一开始就有非连续点.我得到consQ1了Brett和consQ2Szabolcs的设置

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

或者,两者之间差异大约为十倍,与多次试验保持相对一致.通过使用NestWhile以下方法短路过程,可将此时间减少一半左右:

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

它测试每对,只有在它们返回true时才会继续.时间安排

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

同

{0.000076, False}

对consQ.所以,布雷特的答案相当接近,但偶尔也需要两倍的时间.

编辑:我将时间数据的图形移动到社区Wiki答案.

Answer 4

我认为以下内容也很快,并且比较反向列表不需要更长时间:

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]]

编辑

迄今为止对紧固件解决方案的简短测试:

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 可以在一个非常简洁的表达式中使用,该表达式运行得非常快:

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

模式匹配可用于以显着降低的性能为代价提供非常明确的意图表达:

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

编辑

consQFold,正如所写,适用于Mathematica v8.0.4,但不适用于早期版本的v8或v7.要纠正这个问题,有几种选择.第一个是明确Return指出要点:

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

第二个,正如@ Mr.Wizard建议的那样,Return用Throw/ 替换Catch:

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

Answer 6

我现在确信belisarius试图通过编写故意复杂的代码来获取我的山羊.:-P

我会写: f = Range[##, Sign[#2 - #]]& @@ #[[{1, -1}]] == # &

另外,我相信WReach可能会写一些类似的东西:

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

Answer 7

由于时机似乎相当重要.我已经将各种方法之间的比较,社区维基,答案.

使用的数据只是连续整数的列表,具有单个非连续点,并且它们是通过生成的

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]

第一种形式dat[n]相当于dat[n, 1].时间码很简单:

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]

它在1和每个之间生成100个随机整数{10, 25, 50, 100, 250, 500, 1000},dat然后使用每个随机数作为10,000个元素长的列表中的非连续点.consQ然后将每个实现应用于由其生成的每个列表dat,并对结果进行平均.绘图功能很简单

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
  ]

我计时以下功能consQSzabolcs1,consQSzabolcs2,consQBrett,consQRCollyer,consQBelisarius,consQWRFold,consQWRFold2,consQWRFold3,consQWRMatch,和MrWizard的版本的consQBelisarius.

在最左边的定时的升序:consQBelisarius,consQWizard,consQRCollyer,consQBrett,consQSzabolcs1,consQWRMatch,consQSzabolcs2,consQWRFold2,consQWRFold3,和consQWRFold.

编辑:重新使用timeAvg(第二个)而不是Timingin中的所有函数consQTiming.不过,我的平均成绩仍超过100次.在大多数情况下,有任何变化,除了最低的两个,其中从运行到运行有一些变化.所以,把这两条线带上一粒盐,因为它们的时间几乎相同.