पर्ल - सरणी

Question

से ऑफ़सेट के साथ संख्याओं की श्रृंखला निकालें मैं पूर्णांक की सरणी के भीतर संख्याओं की श्रृंखला की खोज करने की कोशिश कर रहा हूं। उदाहरण के लिए, यदि सरणी संख्या 1,2,3,10,12,14 के होते हैं, यह

1 से 3 करने के लिए ऑफसेट 1,

10 के साथ 14 को संक्षेप किया जा सकता है ऑफसेट 2

मेरे कोड के नीचे, जहाँ मैं पाश से अधिक के साथ दूसरा तत्व से सरणी, ट्रैक लगातार सरणी तत्वों के बीच ऑफसेट और एक नया 'श्रृंखला' अगर ऑफसेट परिवर्तन बनाने के लिए:

012:

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- विशिष्ट चाल मौजूद हैं।

मेरे आवेदन में, सरणी में सभी पूर्णांक आरोही क्रम में हैं और डुप्लिकेट संख्या मौजूद नहीं है।

EDIT यदि एकल संख्याएं होती हैं जो किसी गंभीर को असाइनमेंट नहीं कर सकती हैं, तो वे लंबाई की एक श्रृंखला होनी चाहिए।

अधिक संख्या श्रृंखला के लिए संक्षेप किया जा सकता है, बेहतर है (मैं श्रृंखला की संख्या को कम करना चाहते हैं!)

Answer 1

समस्या त्रिगुट ऑपरेटर में है। यदि आप सादे इस्तेमाल किया

offset => $last_diff, 

आप है कि वहाँ

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

जो एक तरह से सही है नोटिस चाहते हैं। इससे बचने के लिए, आप @series पर धक्का देने के बाद undef $diff कर सकते हैं। यह आपके मामले के लिए अपेक्षित आउटपुट का उत्पादन करेगा, लेकिन अभी भी 112 और 8 से शुरू होने वाले तीन अनुक्रमों के रूप में 1 2 3 7 10 12 14 का इलाज करेगा। 12. आपको किसी भी तरह की लंबी अवधि लालची बनाने के लिए अब क्या चाहिए।

मैं निम्नलिखित के साथ प्रयोग किया है, लेकिन आप अधिक का परीक्षण करना चाहिए:

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

यह सबसे आसानी से करता है, तो तीन अलग-अलग चरणों

• प्रत्येक संख्या के बीच अंतर का निर्धारण में किया हल किया जाता है।
• मतभेदों के अनुक्रम निर्धारित करें।
• अंत में श्रेणियां निर्धारित करें।

इनमें से प्रत्येक चरण अधिक आसानी से डीबग करने के लिए किया जाता है कि प्रत्येक चरण सही है या नहीं। इसके अतिरिक्त, 1,7,8,9 जैसे कुछ मानों के लिए, 7 को 1 के साथ cuddled किया जाना चाहिए या नहीं, यह निर्धारित करने के लिए तीन नंबर आगे देखना आवश्यक है।इसलिए यह सीमाओं को बनाने के लिए अंतिम लूप में आवश्यक नियमों को आसानी से निर्धारित और निर्दिष्ट करने के लिए पहले से ही सभी जानकारी की गणना करने में मदद करता है।

आउटपुट को पढ़ने में आसान बनाने के लिए, मैं अकेले संख्या को start मान के रूप में प्रदर्शित कर रहा हूं। इसके अतिरिक्त, मैंने श्रेणी हैश में count जोड़ा। इन परिवर्तनों को बाद में आसानी से समायोजित किया जाता है।

अतिरिक्त परीक्षण डेटा के लिए, मैंने एक अकेले 1 के साथ एक अनुक्रम जोड़ा जिसके बाद 3 संख्याओं का अनुक्रम हुआ, और मैंने चुनौती के लिए एक फाइबोनैकी अनुक्रम भी जोड़ा।

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 

आउटपुट:

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