Perl6: Van Eck 數列產生器


幾周前的 Perl Weekly Challenge #14.1 裡的一題,是寫個能產生出 Van Eck 數列的程式。果不其然,這也是個有在 Numberphile 裡有介紹到的數列。Numberphile -- Don't Know (the Van Eck Sequence)OEIS/A181391

這個數列的第一項為 0,之後的每一項的計算公式,是將目前項數減去前一項數字在前一次出現時的項數。

a[1] = 0
a[n+1] = 0, 若 a[n] 不存在於 a[0..n] 之中
a[n+1] = n - m, 其中 a[m] = a[n] 且為最大者

也就是說,要求 a[n+1],必需向前回溯,找出 a[n] 前一次出現的地方。

~laurent_r 在其部落格上提供了迴圈解:

use v6;

my @a = 0,;
for ^20 -> $n {
    my $result = 0;
    for reverse ^$n -> $m {
        $result = $n - $m and last if @a[$m] == @a[$n];
            # Note: $m is always smaller than $n, so $n - $m > 0
    }
    push @a, $result;
}
say @a;

我則想試著做出可惰性求值、無限產生下去的物件。最後的成果如下:

my $vaneck = Seq.new(
    class :: does Iterator {
        has %!seen is default(-1);
        has Int $!term = -1;
        has Int $!pos  = 0;

        method pull-one {
            my $next = %!seen{$!term} == -1 ?? 0 !! $!pos - %!seen{$!term};
            %!seen{$!term} = $!pos++;
            return $!term = $next;
        }
    }.new()
);

其中 SeqIterator 都是 perl6 中原有的型別。我以 %!seen 這個私有變數去記錄「前一次」見到每一項數字是在何時。

如此做則能印出前 200 項:

$vaneck[^200].map({ .say });