arrays - 如何识别整数数组中的周期序列

Question

主要目标是用bash在数组中找到一个周期序列，例如:

{ 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, 6, 3, 4 }

这两个示例必须返回已识别的序列
{ 2, 5, 7, 8, 2, 6, 5, 3, 5, 4 } 和 { 2, 5, 6, 3, 4 }

我尝试了一个列表和一个由两个数组组成的子列表，但没有成功。我一定是在我的循环中遗漏了一些东西。我认为可以使用“龟兔赛跑”算法作为替代方案，但我缺少一些关于实现它的 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

我在需要索引的关联数组上遇到错误

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)

然后使用正则表达式反向替换，例如在 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

如果你只想要完整的重复，添加一个$ line anchor到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 循环。