calculate a row of numbers(see context for details)

Question

there are two rows of numbers, row 1 is consecutive numbers starting from 0, now ask you to fill out row 2 to make sure the number in row 2 is the times of correspoding number in row 1 appearing in row 2.

For example:

0 1 2 3 4 5 6 7 8 9

_ _ _ _ _ _ _ _ _ _

To be more specific, we use row1 for row 1 and row2 for row 2, we fill out row2 to make sure it satisies: row2[i] = count(row2, row1[i]). count(row2, row1[i]) means frequency count of row1[i] among row2.

Answer 1

Out of 1000 runs this solution had to run the loop an average of 3.608 times

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) takes a guess, x, and returns the counts. We are essentially looking for a solution such that f(x) = x.

We first choose 10 random integers from 0-9 and make a list. Our goal is to repeatedly set this list equal to itself until we either find a solution or run into a cycle. To check for cycles, we use the Tortoise and the Hair algorithm, which move at 2 speeds. A fast speed which is twice as quick as the slow speed. If these are equal, we have run into a cycle and start from a new random scenario.

I ran through this a few times, and found the general solution for n>6 (where in this case n = 10). It is of the form [n-4,2,1,0...,0,1,0,0,0]