Wie eine periodische Sequenz in einer Reihe von ganzen Zahlen

Question

das Hauptziel zu identifizieren, ist eine periodische Abfolge in einem Array mit heftigen Schlag zu finden, zum Beispiel:

{2, 5, 7, 8, 2, 6, 5 , 3, 5, 4, 2, 5, 7, 8, 2, 6, 5, 3, 5, 4, 2, 5, 7, 8, 2, 6, 5, 3, 5, 4}
oder {2, 5, 6, 3, 4, 2, 5, 6, 3, 4, 2, 5, 6, 3, 4, 2, 5, 6, 3, 4}

, die wie angegeben zurückgegeben werden müssen Sequenz für die zwei Beispiele
{2, 5, 7, 8, 2, 6, 5, 3, 5, 4} und {2, 5, 6, 3, 4}

I tri ed mit einer Liste und einer Unterliste, die aus zwei Arrays besteht, aber keinen Erfolg hat. Ich muss etwas in meinen Schleifen vermissen. Ich denke an den Algorithmus "Schildkröte und Hase" als eine Alternative, aber ich vermisse etwas Wissen in bash-Befehle, um es zu implementieren.

Ich ziehe meinen zweiten Versuch mit Schildkröte und Hasen als die ersten zu schreiben scheint ein nutzloser Versuch zu sein:

#!/bin/bash 
declare -A array=(1, 2, 3, 1, 2, 3, 1, 2, 3) 
declare -A found=() 
loop="notfound" 
tortoise=`echo ${array[0]}` 
hare=`echo ${array[0]}` 
found[0]=`echo ${array[0]}` 
while ($loop == "notfound") 
do 
    for ((i=1;i=`echo ${#array[@]}`;i++)) 
    do 
     if ((`echo ${array[$#]}` == $hare)) 
     then 
      echo "no loop found" 
      exit 0 
     fi 
     hare=`echo ${array[$i]}` 
     if ((`echo ${array[$#]}` == $hare)) 
     then 
      echo "no loop found" 
      exit 0 
     fi 
     hare=`echo ${array[$(($i+1))]}` 
     tortoise=`echo ${array[$i]}` 
     found[$i]=`echo ${array[$i]}` 
     if (($hare == $tortoise)) 
     then 
      loop="found" 
      printf "$found[@]}" 
     fi 
    done 
done 

ich Fehler auf assoziatives Array bekam benötigen indice

Answer 1

ein Array a einzelnereinzelneeinzelnes Gegeben Dezimalstellen

a=(2 5 7 8 2 6 5 3 5 4 2 5 7 8 2 6 5 3 5 4 2 5 7 8 2 6 5 3 5 4) 

dann reguläre Ausdruck Rücksubstitution unter Verwendung zum Beispiel in perl

printf '%d' "${a[@]}" | perl -lne 'print $1 if /^(\d+)\1+/' 
2578265354 

Testing mit einer unvollständigen Sequenz

a=(1 2 3 1 2 3 1 2) 
printf '%d' "${a[@]}" | perl -lne 'print $1 if /^(\d+)\1+/' 
123 

Wenn Sie nur komplette Wiederholungen wollen, fügen Sie eine $ Linie Anker an die RE, /^(\d+)\1+$/

---

Nun, wenn Sie die identifizieren möchten längste Untersequenz, die "fast" wiederholt wird, das ist ein wenig komplizierter. Im Falle Ihrer 250-stelligen Sequenz ist eine 118-stellige Teilfolge, die 2-mal wiederholt wird (mit 16 verbleibenden Zeichen), während Ihre erwartete Ausgabe eine 13-stellige Teilfolge ist (19-mal wiederholt, mit 3 Ziffern übrig). Sie wollen also einen Algorithmus, der "gierig, aber nicht zu gierig" ist.

One (hoffentlich nicht zu ineffiziente) Weise zu tun, wäre sukzessiv nachlauf Ziffern zu entfernen, bis ein verankertes Spiel d.h. die gesamten verbleibende Sequenz erhalten wird s* kann t als n x t für einige Subsequenz dargestellt werden. In Perl, können wir das als eine einfache Schleife

perl -lne 'while (! s/^(\d+)\1+$/$1/) {chop $_}; print' 

Testing mit Ihrer 250-Ziffernfolge schreiben:

a=(1 1 0 2 1 2 0 0 2 0 2 2 2 1 1 0 2 1 2 0 0 2 0 2 2 2 1 1 0 2 1 2 0 0 2 0 2 2 2 1 1 0 2 1 2 0 0 2 0 2 2 2 1 1 0 2 1 2 0 0 2 0 2 2 2 1 1 0 2 1 2 0 0 2 0 2 2 2 1 1 0 2 1 2 0 0 2 0 2 2 2 1 1 0 2 1 2 0 0 2 0 2 2 2 1 1 0 2 1 2 0 0 2 0 2 2 2 1 1 0 2 1 2 0 0 2 0 2 2 2 1 1 0 2 1 2 0 0 2 0 2 2 2 1 1 0 2 1 2 0 0 2 0 2 2 2 1 1 0 2 1 2 0 0 2 0 2 2 2 1 1 0 2 1 2 0 0 2 0 2 2 2 1 1 0 2 1 2 0 0 2 0 2 2 2 1 1 0 2 1 2 0 0 2 0 2 2 2 1 1 0 2 1 2 0 0 2 0 2 2 2 1 1 0 2 1 2 0 0 2 0 2 2 2 1 1 0 2 1 2 0 0 2 0 2 2 2 1 1 0) 

Dann

printf '%d' "${a[@]}" | perl -lne 'while (! s/^(\d+)\1+$/$1/) {chop $_}; print' 
1102120020222 

HINWEIS: diese zu beenden, werden scheitern, wenn die Die Zeichenfolge ist erschöpft, bevor eine Übereinstimmung gefunden wird. Wenn das eine Möglichkeit ist, müssen Sie dafür testen und aus der while Schleife ausbrechen.

Answer 2

Ich habe dies nur mit den von Ihnen bereitgestellten Eingängen getestet. Annahmen - Muster zu übereinstimmen beginnt immer am Anfang des Arrays und wiederholt sich danach.

#!/bin/bash 

#arr=(2 5 7 8 2 6 5 3 5 4 2 5 7 8 2 6 5 3 5 4 2 5 7 8 2 6 5 3 5 4) 
arr=(2 5 6 3 4 2 5 6 3 4 2 5 6 3 4 2 5 6 3 4) 

echo ${arr[@]} 
n=${#arr[*]} 
match=0 
in_pattern=false 

print_array() 
{ 
    local first=$1 
    local last=$2 
    local i 

    for ((i=first; i<=last; i++));do 
    printf "%d " ${arr[i]} 
    done 
    printf "\n" 
} 

i=0 
start=0 
end=0 
j=$((i+1)) 

while ((j < n)); do 
    #echo "arr[$i] ${arr[i]} arr[$j] ${arr[j]}" 
    if [[ ${arr[i]} -ne ${arr[j]} ]];then 
    if [[ $match -ge 1 ]];then 
     echo "arr[$i] != arr[$j]" 
     echo "pattern doesnt repeat after match # $match" 
     exit 1 
    fi 
    ((j++)) 
    i=0 
    in_pattern=false 
    continue 
    fi 
    if $in_pattern ; then 
    if [[ $i -eq $end ]];then 
     ((match++)) 
     end_match=$j 
     echo "match # $match matched from $start -> $end and $start_match -> $end_match" 
     print_array $start $end 
     print_array $start_match $end_match 
     ((j++)) 
     i=0 
     in_pattern=false 
     continue 
    fi 
    else 
    if [[ $match -eq 0 ]];then 
     end=$((j-1)) 
    fi 
    start_match=$j 
    in_pattern=true 
    #echo "trying to match from start $start end $end to start_match $start_match" 
    fi 
    ((i++)) 
    ((j++)) 
done 


output with first array - 

./sequence.sh 
2 5 7 8 2 6 5 3 5 4 2 5 7 8 2 6 5 3 5 4 2 5 7 8 2 6 5 3 5 4 
match # 1 matched from 0 -> 9 and 10 -> 19 
2 5 7 8 2 6 5 3 5 4 
2 5 7 8 2 6 5 3 5 4 
match # 2 matched from 0 -> 9 and 20 -> 29 
2 5 7 8 2 6 5 3 5 4 

2nd array - 

/sequence.sh 
2 5 6 3 4 2 5 6 3 4 2 5 6 3 4 2 5 6 3 4 
match # 1 matched from 0 -> 4 and 5 -> 9 
2 5 6 3 4 
2 5 6 3 4 
match # 2 matched from 0 -> 4 and 10 -> 14 
2 5 6 3 4 
2 5 6 3 4 
match # 3 matched from 0 -> 4 and 15 -> 19 
2 5 6 3 4 
2 5 6 3 4