Perl: estrai serie di numeri con offset dall'array

Question

Sto cercando di cercare serie di numeri all'interno di un array di numeri interi. Ad esempio, se la matrice è costituito dai numeri 1,2,3,10,12,14, si potrebbe riassumere per

1 a 3 con compensazione 1,

10 a 14 con correzione 2

Questi mio codice, dove un ciclo su la matrice dal secondo elemento, tiene lo sfasamento tra elementi dell'array consecutivi e creare un nuovo 'serie' se i cambiamenti di 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); 

uscita appare come segue:

Questo non è il risultato desiderato, poiché le ultime due serie potrebbero essere riassunte in una (da 10 a 14, offset 2 invece di due serie).

Il difetto nell'algoritmo è indipendente da perl, tuttavia, forse qualcuno potrebbe darmi un suggerimento su come avvicinarsi al meglio, forse esistono alcuni trucchi specifici perl per questo.

Nella mia applicazione, tutti gli interi dell'array sono in ordine crescente e non esistono numeri duplicati.

EDIT Se singoli numeri verificano che non può essere assignet un grave, che dovrebbe essere una serie di lunghezza.

i numeri più può essere sintetizzato come serie, il migliore (voglio minimizzare il numero di serie!)

Answer 1

Il problema è nel l'operatore ternario. Se è stato utilizzato pianura

offset => $last_diff, 

che ci si nota che v'è

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

che è corretto in un certo senso. Per evitarlo, puoi undef $diff dopo aver premuto su @series. Produrrebbe l'output previsto per il tuo caso, ma tratterà comunque 1 2 3 7 10 12 14 come tre sequenze, a partire da 1, 7 e 12. Quello che ti serve è rendere una frase più lunga avida in qualche modo, ora.

ho sperimentato con il seguente, ma si dovrebbe testare più:

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

Questo è più facilmente risolto se fatto in tre fasi distinte

• Determinare differenza tra ogni numero.
• Determinare le sequenze di differenze.
• Infine, determinare gli intervalli.

Ognuna di queste operazioni viene eseguita per semplificare il debug se ogni passaggio è corretto. Inoltre, per determinati valori come 1,7,8,9, è necessario cercare tre numeri in avanti per determinare se 7 deve essere coccolato con 1 oppure no.Pertanto, è utile avere già calcolato tutte le informazioni in anticipo per determinare più facilmente e specificare le regole necessarie nel ciclo finale per creare gli intervalli.

Per rendere l'output più facile da leggere, sto visualizzando i numeri solitari come solo un valore start. Inoltre, ho aggiunto un count agli hash degli intervalli. Queste modifiche sono facilmente modificabili in seguito.

Per ulteriori dati di test, ho aggiunto una sequenza con un 1 solitario seguito da una sequenza di 3 numeri e ho anche aggiunto una sequenza di Fibonacci per la sfida.

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 

Uscite:

(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 }, 
)