循环检测算法

Question

说我有一个函数f:

f(0) = 0
f(i) = (i - 1) % 4

F(0..12):

0 0 1 2 3 0 1 2 3 0 1 2 3

我想找到循环开始和循环长度,分别为1和4.乌龟和野兔算法适用于迭代函数,但我没有迭代函数.是否有其他算法可以使用非迭代函数,或者可以为此修改龟和野兔算法？

编辑:

使用Jason S的答案,我设法提出了这个,这似乎是有效的:

public static Tuple<int, int> ModifiedTortoiseHare(Func<int, int> f, int x0 = 0, int checks = 4)
{
    for (; ; x0++)
    {
        int lam = 0, tortoise, hare;

        do
        {
            lam++;
            tortoise = f(x0 + lam);
            hare = f(x0 + 2 * lam);
        } while (tortoise != hare);

        int mu = -1;

        do
        {
            mu++;
            tortoise = f(x0 + mu);
            hare = f(x0 + mu + lam);
        } while (tortoise != hare);

        if (mu != 0) continue;

        bool correct = true;
        int lamCheckMax = lam * checks;

        for (int x = 0; x < lamCheckMax; x++)
        {
            if (f(x0 + x + mu) != f(x0 + x + mu + lam))
            {
                correct = false;
                if (mu != 0) x0 += mu - 1;
                break;
            }
        }

        if (correct) return Tuple.Create(x0 + mu, lam);
    }
}

Answer 1

如果函数是一个"黑盒子",你有能力为任何个体x找到f(x)(无论是对实数有效还是只对整数有效),但你不知道其他任何东西,没有一般的方法找到一个循环开始和长度.例如,考虑一下这个功能

f(k) = (k - 1) % 4 + g(k)
g(k) = max(0, k-1000000)

然后f(k)看起来像每4个整数重复一次,但是当你达到k = 1000000时,模式就会停止.

如果函数具有有限的范围内,并且可以测试所有整数,乌龟/野兔算法(= 弗洛伊德的循环查找算法)可以被用来帮助.

而不是迭代函数评估,计算f(k0 + k)和f(k0 + 2*k)直到它们匹配,此时可疑周期为k,你只需要重复所有值以验证循环继续.

您的问题似乎是一个等同的问题:"我应该如何找到重复的单词序列？" 这有很多答案.