Perl - trích xuất hàng loạt các số có bù từ mảng

Question

Tôi đang cố gắng tìm kiếm chuỗi số trong một mảng các số nguyên. Ví dụ, nếu mảng bao gồm các số 1,2,3,10,12,14, nó có thể được tóm tắt để

1-3 với bù 1,

10-14 với bù 2

Dưới đây mã của tôi, nơi tôi vòng qua mảng từ phần tử thứ hai, theo dõi bù đắp giữa các phần tử mảng liên tục và tạo ra một mới 'loạt' nếu những thay đổi offset:

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); 

Output trông như sau:

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

Đây không phải là kết quả mong muốn, vì hai chuỗi cuối cùng có thể được tóm tắt thành một (10 đến 14, bù trừ 2 thay vì hai chuỗi).

Lỗ hổng trong thuật toán độc lập với perl, tuy nhiên, có thể ai đó có thể cho tôi gợi ý về cách tiếp cận tốt nhất, có thể tồn tại một số thủ thuật cụ thể cho điều này.

Trong ứng dụng của tôi, tất cả các số nguyên trong mảng nằm trong thứ tự tăng dần và số trùng lặp không tồn tại.

CHỈNH SỬA Nếu số đơn lẻ xảy ra không thể gán cho mức nghiêm trọng, chúng phải là chuỗi có độ dài một.

Những con số hơn có thể được tóm tắt để loạt, thì càng tốt (Tôi muốn giảm thiểu số lượng hàng loạt!)

Answer 1

Vấn đề là trong điều hành ternary. Nếu bạn sử dụng đơn giản

offset => $last_diff, 

bạn muốn thông báo rằng có

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

nào là đúng theo một cách. Để tránh điều đó, bạn có thể undef $diff sau khi chuyển sang @series. Nó sẽ tạo ra kết quả mong đợi cho trường hợp của bạn, nhưng vẫn sẽ xử lý 1 2 3 7 10 12 14 như ba chuỗi, bắt đầu từ 1, 7 và 12. Điều bạn cần là làm cho một câu dài hơn tham lam bằng cách nào đó, bây giờ.

tôi đã thử nghiệm với những điều sau đây, nhưng bạn nên kiểm tra hơn:

#!/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); 

Answer 2

này được dễ dàng nhất giải quyết nếu được thực hiện trong ba bước riêng biệt

• Xác định chênh lệch giữa mỗi số.
• Xác định chuỗi sự khác biệt.
• Cuối cùng xác định phạm vi.

Mỗi bước được thực hiện để dễ dàng gỡ lỗi hơn cho dù mỗi bước là chính xác. Ngoài ra, đối với các giá trị nhất định như 1,7,8,9, cần phải xem xét ba số trước để xác định xem 7 có nên được ôm ấp với 1 hay không.Do đó nó giúp đã tính toán tất cả các thông tin trước để dễ dàng xác định và xác định các quy tắc cần thiết trong vòng lặp cuối cùng để xây dựng các phạm vi.

Để làm cho đầu ra dễ đọc hơn, tôi hiển thị các số đơn độc chỉ với giá trị start. Ngoài ra, tôi đã thêm một count vào băm phạm vi. Những thay đổi này có thể dễ dàng điều chỉnh sau.

Để có dữ liệu thử nghiệm bổ sung, tôi đã thêm một chuỗi có đơn độc 1 theo sau là một chuỗi gồm 3 số và tôi cũng đã thêm một chuỗi Fibonacci cho thử thách.

use strict; 
use warnings; 

use Data::Dump; 

while (<DATA>) { 
    chomp; 
    my @nums = split ','; 

    my @diffs = map {$nums[$_+1] - $nums[$_]} (0..$#nums-1); 

    my @seq; 
    for (@diffs) { 
     if (@seq && $seq[-1]{diff} == $_) { 
      $seq[-1]{count}++; 
     } else { 
      push @seq, {diff => $_, count => 1}; 
     } 
    } 

    my @ranges; 
    for (my $i = 0; $i < @nums; $i++) { 
     my $seq = shift @seq; 

     # Solitary Number 
     if (!$seq || ($seq->{count} == 1 && @seq && $seq[0]{count} > 1)) { 
      push @ranges, {start => $nums[$i]}; 

     # Confirmed Range 
     } else { 
      push @ranges, { 
       start => $nums[$i], 
       end => $nums[$i + $seq->{count}], 
       count => $seq->{count} + 1, # Can be commented out 
       offset => $seq->{diff}, 
      }; 
      $i += $seq->{count}; 
      shift @seq if @seq && !--$seq[0]{count}; 
     } 
    } 

    dd @nums; 
    dd @ranges; 
    print "\n"; 
} 

__DATA__ 
1,2,3,10,12,14 
1,2,3,5,7 
1,7,8,9 
1,2,3,7,8,11,13,15,22,100,150,200 
2,3,5,8,13,21,34,55,89 

Đầu ra:

(1, 2, 3, 10, 12, 14) 
(
    { count => 3, end => 3, offset => 1, start => 1 }, 
    { count => 3, end => 14, offset => 2, start => 10 }, 
) 

(1, 2, 3, 5, 7) 
(
    { count => 3, end => 3, offset => 1, start => 1 }, 
    { count => 2, end => 7, offset => 2, start => 5 }, 
) 

(1, 7, 8, 9) 
(
    { start => 1 }, 
    { count => 3, end => 9, offset => 1, start => 7 }, 
) 

(1, 2, 3, 7, 8, 11, 13, 15, 22, 100, 150, 200) 
(
    { count => 3, end => 3, offset => 1, start => 1 }, 
    { count => 2, end => 8, offset => 1, start => 7 }, 
    { count => 3, end => 15, offset => 2, start => 11 }, 
    { start => 22 }, 
    { count => 3, end => 200, offset => 50, start => 100 }, 
) 

(2, 3, 5, 8, 13, 21, 34, 55, 89) 
(
    { count => 2, end => 3, offset => 1, start => 2 }, 
    { count => 2, end => 8, offset => 3, start => 5 }, 
    { count => 2, end => 21, offset => 8, start => 13 }, 
    { count => 2, end => 55, offset => 21, start => 34 }, 
    { start => 89 }, 
)