给定一个随机整数和一个变换函数，经过一段时间的变换，它就会运行成一个循环

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是一个函数（它总是为给定的输入产生相同的输出），并且因为函数的范围（可能输出的集合）是有限的。由于范围是有限的，如果你反复将范围映射到它本身，你最终必须得到一些你已经看到的值。