arrays - Perl - 从数组中提取具有偏移量的数字系列

Question

我正在尝试在整数数组中搜索一系列数字。例如，如果数组由数字 1,2,3,10,12,14 组成，可以归纳为

1 到 3，偏移量为 1，

10 到 14，偏移量为 2

在我的代码下方，我从第二个元素开始遍历数组，跟踪连续数组元素之间的偏移量，并在偏移量发生变化时创建一个新的“系列”:

use strict;
use warnings;

my @numbers = (1,2,3,10,12,14); #array to extract series from 
my $last_diff;
my $start = $numbers[0];
my $end;
my @all_series; #array will hold all information on series
for my $i (1..($#numbers+1)){
        my $diff;
        if ($i <($#numbers+1)){
                $diff = $numbers[$i] - $numbers[$i-1];
        }
        if (!$diff || ( $last_diff && ($last_diff != $diff)) ) {
                $end = $numbers[$i-1];
                my $series = { 'start'=> $start,
                            'end'  => $end,
                            'offset'=> $start == $end ? 1 : $last_diff,
                };
                push @all_series, $series;
                $start = $numbers[$i];
        }
        $last_diff = $diff;
}

use Data::Dumper;
print Dumper(@all_series);

输出如下所示:

$VAR1 = {
          'offset' => 1,
          'end' => 3,
          'start' => 1
        };
$VAR2 = {
          'offset' => 1,
          'end' => 10,
          'start' => 10
        };
$VAR3 = {
          'offset' => 2,
          'end' => 14,
          'start' => 12
        };

这不是预期的结果，因为可以将最后两个系列汇总为一个(10 到 14，偏移量 2 而不是两个系列)。

算法中的缺陷与 perl 无关，但是，也许有人可以给我一个关于如何最好地实现这一点的提示，也许存在一些特定于 perl 的技巧。

在我的应用程序中，数组中的所有整数都按升序排列，并且不存在重复的数字。

编辑
如果出现不能分配给一个严重的单个数字，它们应该是一系列长度为 1 的数字。

可以总结为系列的数字越多越好(我想尽量减少系列的数量!)

Answer 1

问题出在三元运算符中。如果您使用普通

offset => $last_diff,

你会注意到有

$VAR2 = {
          'offset' => 7,
          'end' => 10,
          'start' => 10

这在某种程度上是正确的。为了避免它，您可以 undef $diff在推送到@series 之后。它会为您的案例产生预期的输出，但仍会处理 1 2 3 7 10 12 14作为三个序列，从 1、7 和 12 开始。现在您需要以某种方式使更长的句子变得 greedy。

我尝试了以下内容，但您应该进行更多测试:

#!/usr/bin/perl
use warnings;
use strict;

use Data::Dumper;

my @numbers = (1, 2, 3, 10, 12, 14);
my $last_diff;
my $start = $numbers[0];
my @all_series;
for my $i (1 .. $#numbers + 1) {
    my $diff;
    if ($i < $#numbers + 1) {
        $diff = $numbers[$i] - $numbers[ $i - 1 ];
    }

    # Merge with the last number from the previous series if needed:
    if (!$last_diff # Just starting a new series.
        and $i > 2  # Far enough to have preceding numbers.
        and $diff and $diff == $numbers[ $i - 1 ] - $numbers[ $i - 2 ]
       ) {
        $all_series[-1]{end} = $numbers[ $i - 3 ];
        $all_series[-1]{offset} = 0 if $all_series[-1]{start} == $all_series[-1]{end};
        $start = $numbers[ $i - 2 ];
    }

    if (! $diff or ( $last_diff && ($last_diff != $diff)) ) {
        push @all_series, { start  => $start,
                            end    => $numbers[ $i - 1 ],
                            offset => $last_diff,
                          };
        $start = $numbers[$i];
        undef $diff;
    }
    $last_diff = $diff;
}

print Dumper(@all_series);