TSabc 発言

廣島です．

> 1) 与えられたリストの先頭から連番になっている部分リストを除去し，

> # 1) の部分は今のところ単なる線形検索でやっています．
> # リストが長く，欠番が少ない場合には効率が悪くなるので，
> # 重みつきの 2 分木検索で最初の欠番を探すのが良いと思います．
> # (次の「お題」か? スクリプトが見にくくなるだけ?)

単調増加数列の連番が最初に終る位置を 2 分木検索 で探す関数を書きました．
seekfirstleap(3, 4, 5, 7, 9, 10) なら，5 で連番が終るので，
その位置(インデックス) 2 を返します．

list を単調増加数列のリスト，
a を検索区間の下限
b を検索区間の上限とします．
ともに list のインデックスで
初期値は a = 0 と b = (list の最後のインデックス)です．

検索区間に含まれる欠番の数は，

l = list[b] - list[0] - b

で計算できます．
list 中に欠番が均等に分散しているならば，
最初の欠番は全体の  1 / (l + 1) の位置にあるはずなので，
インデックス c = (a * l + b) / (l + 1) を調べます．

まず a と c の間の欠番の数

m = list[c] - list[0] - c

を計算します．(0 から a までには欠番が無い事に注意)

m > 0 ならばインデックス a から c までの間に欠番があります．
検索区間の上限 b を b = c - 1 に設定し直します．
list[b] - list[0] - b == 0 なら，b が求めるものです．

m == 0 ならばインデックス a から c までは連番になっています．
検索区間の下限 a を a = c + 1 に設定し直します．
list[a] - list[0] - a > 0 なら c が求めるものです．

sub seekfirstleap {
  my $f = $_[0];
  my $l = $_[-1] - $f - $#_;
  return $#_ if $l == 0;
  my $a = 0;
  my $b = $#_;
  my $c;
  for (;;) {
    $c = int (($a * $l + $b) / ($l + 1));
    if ($_[$c] - $f - $c > 0) {
      $b = $c - 1;
      $l = $_[$b] - $f - $b;
      return $b if $l == 0;
    } else {
      $a = $c + 1;
      return $c if $_[$a] - $f - $a;
    }
  }
}

@list = (1,2,3,5,7,8,10,12,14,15,16,17);

sub seqfind4 {
  my @ret;
  while (@_) {
    my $i = seekfirstleap(@_) + 1;
    my @seq = splice @_, 0, $i;
    push @ret, scalar @seq == 1 ? $seq[0] : "$seq[0]-$seq[-1]";
  }
  return join(',', @ret);
}

print seqfind4(@list), "\n";

# Scheme や Lisp みたいに
# リストの要素 list[n] へのアクセスが線形時間 O(n) なら，
# あまり意味が無いです．
# Perl の配列へのアクセスって O(1) なのかな?

-----------------------------
	廣島 勉
	(tsutomu@...)