Как определить периодическую последовательность в массиве целых чисел

Question

Основная цель состоит в том, чтобы найти периодическую последовательность в массиве с Баш, например:

{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}
или {2, 5, 6, 3, 4, 2, 5, 6, 3, 4, 2, 5, 6, 3, 4}

, который должен быть возвращен как идентифицированный последовательность для двух примеров
{2, 5, 7, 8, 2, 6, 5, 3, 5, 4} и {2, 5, 6, 3, 4}

I tri ed со списком и под-списком из двух массивов, но без успеха. Мне не хватает чего-то в моих петлях. Я думаю, что алгоритм «черепаха и заяц» является альтернативой, но я пропускаю некоторые знания в командах bash для его реализации.

Я предпочитаю оставлять свою вторую попытку с черепахой и зайцем, как и первый, кажется, бесполезная попытка:

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

Я получил ошибки на ассоциативном массиве нуждаясь Indice

Answer 1

Дан массив a из одного десятичных цифр

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) 

затем с использованием регулярных выражений backsubstitution, например, в perl

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

Тестирование с неполной последовательностью

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

Если вы хотите только полные повторы, добавьте $ линию якорь в RE, /^(\d+)\1+$/

---

Теперь, если вы хотите, чтобы идентифицировать самая длинная подпоследовательность, которая «почти почти» повторена, это немного сложнее. Например, в случае вашей 250-значной последовательности - это 118-значная подпоследовательность, повторяющаяся 2 раза (с оставшимися 16 символами), тогда как ваш ожидаемый результат представляет собой 13-значную подпоследовательность (повторяется 19 раз, с Осталось 3 цифры). Поэтому вам нужен алгоритм, «жадный, но не слишком жадный».

Один (надеюсь, не слишком неэффективно) способ сделать это было бы, чтобы последовательно удалить хвостовых цифры до тех пор, якорь матч не будет получен, т.е. всей оставшейся последовательности s* может быть представлено в виде n x t для некоторой подпоследовательности t. В Perlом, мы можем написать, что, как простой цикл

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

Тестирования с 250-разрядной последовательностью:

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) 

Тогда

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

Примечания: это не если прекратить строка исчерпана до того, как будет найдена совпадение; если это возможно, вам нужно будет проверить это и вырваться из цикла while.

Answer 2

Я тестировал это только с помощью введенных вами входов. Предположения - шаблон для соответствия всегда начинается в начале массива и повторяется там после.

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