algorithm - 计算一行数字(详见上下文)

Question

有两行数字，第一行是从0开始的连续数字，现在要求你填写第二行，确保第二行的数字是第一行对应数字出现在第二行的次数。

例如:

0 1 2 3 4 5 6 7 8 9

_ _ _ _ _ _ _ _ _ _

更具体地说，我们使用 row1 作为第 1 行，row2 作为第 2 行，我们填写 row2 以确保它满足: row2[i] = count(row2, row1[i])。 count(row2, row1[i])表示row2中row1[i]的频率计数。

Answer 1

在 1000 次运行中，此解决方案必须平均运行循环 3.608 次

import random

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

fast = list(range(10))

while f(fast) != fast:
    fast = []
    slow = []
    for i in range(10):
        r = random.randint(0,9)
        fast.append(r)
        slow.append(r)
    while True:
        fast = f(f(fast))
        slow = f(slow)
        if fast == slow:
            break

print(fast)

f(x) 进行猜测 x，并返回计数。我们本质上是在寻找满足 f(x) = x 的解决方案。

我们首先从 0-9 中选择 10 个随机整数并制作一个列表。我们的目标是重复设置此列表等于其自身，直到我们找到解决方案或遇到循环。为了检查周期，我们使用乌龟和毛发算法，它们以两种速度移动。比慢速快两倍的快速。如果它们相等，我们就进入了一个循环并从一个新的随机场景开始。

我经过了几次，找到了 n>6(在本例中 n = 10)的一般解决方案。它的形式是 [n-4,2,1,0...,0,1,0,0,0]