algorithm - 给定随机整数和一个变换函数，经过几次变换，就会进入一个循环

Question

这是一道派生题，可以引用original question ,我的问题是:给定 10 个随机整数(从 0 到 9，允许重复)和一个转换函数 f，f 是这样的(在 python 3.3 代码中):

def f(a):
    l = []
    for i in range(10):
        l.append(a.count(i))
return l

假设a是十个随机整数，执行f并将结果赋值给a，重复这个过程，几次之后，你会遇到一个循环。就是说:a,a1=f(a),a2=f(a1)...，这个序列有一个循环。

测试代码如下(代码来自@user1125600):

import random
# [tortoise and hare algorithm][2] to detect cycle
a = []
for i in range(10):
    a.append(random.randint(0,9))
print('random:', a)
fast = a
slow = a
i = 0
while True:
    fast = f(f(fast))
    slow = f(slow)
    print('slow:', slow, 'fast:', fast)
    i +=1
    # in case of running into an infinite loop, we are limited to run no more than 10 times
    if(i > 10):
        print('more than 10 times, quit')
        break
    if fast == slow:
        print('you are running in a cycle:', fast, 'loop times:', i)
        break

如何证明其中存在循环？还有一个有趣的事情是:看测试结果，你会发现fast和slow只会在三个点相遇:[7, 1, 0, 1, 0, 0, 1, 0, 0, 0] 和 [6, 3, 0, 0, 0, 0, 0, 1, 0, 0] 和[6, 2, 1, 0, 0, 0, 1, 0, 0, 0]

Answer 1

必须有一个循环，因为 f 是一个函数(对于给定的输入它总是产生相同的输出)，并且因为函数的范围(可能输出的集合)是有限的.由于范围是有限的，如果您反复将范围映射到自身，您最终必须得到一些您已经看到的值。