Calculate a string of numbers (see context for details)

Question

there are two lines of numbers, line 1 is consecutive numbers starting with 0, now ask you to fill in line 2 to make sure that the number in line 2 is the time of the proofreading number in line 1 appearing in line 2.

For instance:

0 1 2 3 4 5 6 7 8 9

_ _ _ _ _ _ _ _ _ _

To be more specific, we use row1 for rows 1 and row2 for row 2, we populate row2 to make sure it satisfies: row2[i] = count(row2, row1[i]) . count(row2, row1[i]) means the frequency of counting row1[i] among row2 .

Answer 1

Out of 1000 starts, this solution was supposed to start the cycle on average 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 fortune telling, x and returns count. We are mainly looking for a solution such that f (x) = x.

First, we select 10 random numbers from 0-9 and make a list. Our goal is to re-establish this list as equal to ourselves until we find a solution or work in a loop. To check the cycles, we use the turtle and hair algorithm, which moves at a speed of 2 speeds. Fast speed, which is two times faster than slow speed. If they are equal, we run into a loop and start with a new random scenario.

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

Answer 2

We can solve it mathematically.

Let us call our solution s and p subset of s , where s[i] > 0 , that is, the set of numbers represented (any zero is a number or index that is not represented).

We can say that n = sum of all frequencies = sum p

Now let p' subset of p without s[0] , which are the frequencies of only numbers greater than zero.

It is clear that sum p' = sum p - s[0] = length p , which is simply the number of numbers in s greater than zero.

Remember that length p = length p' + 1 . Now, if length p > 4 , we know that sum p' > 4 , and we are left with a section of length m ( p' ), which should be added to m+1 , where m > 3 . The only way to do this is (m-1) 1 and one 2, for example, [1,1,1,2] in the case m=4 (by definition there are no zeros in p' ). Such a section may not make sense as a solution to our problem, and therefore we see that p or a subset of numbers greater than zero in our solution should have less than 5 elements.

Now we can solve for specific cases:

Each solution must have s[0] > 0 , since zero in the zero column will invalidate the solution.

length p = 1 is only possible if s[0] can simultaneously be zero and greater than zero.

length p = 2 means p' = [2] , and therefore there are two zeros and two 2, s=[2,0,2,0]

length p = 3 means p' = [1,2] . Since we know that there is only one more s[i] , which s[0] > 0 , 2 in p' must either refer to itself, and in this case we have s=[2,1,2,0,0] ; or to two 1 and therefore s=[1,2,1,0]

length p = 4, p' = [2,1,1] . In this case, 2 can refer only to two, and we must take s[0] > 2 , which also means sum p >= (3+2+1+1 = 7) . This is the final / general case that user1125600 found: s[1]=2, s[2]=1 . The last 1 refers to s[0] , so its index is s[0] . Recalling that sum p - s[0] = length p , we get s[0] = n - 4 , and the solution for p = 4, n> 6: s=[n - 4,2,1...1,0,0,0]

Answer 3

Solution: brute force. There are only 42 whole sections out of 10 . Try them all and see which one works.