[bushindo]

A permutation is a rearrangement of a list. For instance, suppose that we have a vector x = (A, B, C, D, E, F, G), and we have a permutation P = ( 7,6,5,4,3,2,1 ). If we apply P to y, we get the following

P( y ) = (G, F, E, D, C, B, A).

If we apply this particular permutation P twice to y, we get the original vector back

P²( y ) = P( P( y ) ) = (A, B, C, D, E, F, G).

Let's say that I have a 62-dimensional binary vector y. I also have another permutation P. I apply the consecutive powers of P to y, and list out the result. In the code block below, the 61 rows, starting from the first one, list out P⁰y, P¹y, P²y, ....., P⁶⁰y. Note that P has a cycle of 60, as P⁶⁰y = y.

The challenge is to find P from the data below. What is this permutation?

0 1 0 1 1 0 1 0 1 0 1 1 0 0 1 1 1 0 1 1 1 1 1 0 1 1 1 0 0 0 0 0 0 1 0 1 0 0 0 0 1 0 0 1 1 0 0 0 1 1 0 1 1 1 0 0 1 0 0 1 1 0

0 1 0 1 0 0 1 1 1 0 0 0 1 1 1 1 0 1 1 0 0 1 0 1 1 0 1 1 1 1 0 0 1 1 0 0 0 0 1 0 1 0 1 1 0 0 0 0 0 0 1 0 1 0 0 1 1 0 1 1 1 0

1 1 1 0 0 0 1 0 0 0 1 1 0 1 1 0 0 1 0 0 0 0 0 1 1 1 1 1 0 1 1 0 0 1 1 0 0 1 1 1 1 1 1 1 1 0 0 0 0 1 0 1 0 0 0 0 1 0 0 1 0 1

0 1 1 1 0 1 0 0 0 1 0 0 1 1 1 1 0 0 0 1 0 0 0 1 0 1 1 1 0 0 1 1 0 1 1 1 0 1 1 0 0 0 0 1 1 1 1 0 1 0 0 1 1 0 0 1 1 0 0 0 1 0

0 0 1 0 0 1 1 0 1 0 1 0 0 1 1 1 0 0 0 0 0 1 1 0 0 0 1 1 1 0 1 0 0 1 1 1 1 0 0 1 1 0 1 0 1 1 1 1 0 0 0 0 0 1 1 1 1 0 0 1 1 0

0 1 0 0 0 0 1 0 0 0 1 0 1 1 1 1 1 1 1 1 1 0 1 1 1 0 1 0 1 0 1 0 0 0 1 1 0 0 0 0 0 0 0 1 0 1 1 1 0 0 0 1 0 1 0 0 1 1 1 1 0 1

1 1 1 0 1 0 0 1 0 1 0 0 1 1 0 0 1 0 1 0 0 1 1 1 0 1 1 1 1 1 1 0 1 1 0 1 0 0 1 1 0 0 0 0 0 1 0 1 0 0 0 0 0 0 0 1 1 0 1 1 0 1

1 0 1 0 0 0 0 0 0 1 1 1 0 0 1 0 1 0 1 1 0 0 0 1 1 0 1 0 1 1 1 0 1 1 1 0 1 1 0 1 0 1 0 0 1 1 1 1 1 0 1 0 0 0 0 0 1 0 0 0 1 1

0 0 1 1 0 1 1 0 1 1 0 0 1 1 1 1 1 0 0 1 0 1 1 0 0 0 1 0 0 1 0 1 1 0 0 1 1 1 1 0 0 1 0 0 0 1 1 1 1 1 0 0 0 0 0 0 1 1 0 0 0 1

0 1 0 0 1 1 0 0 1 1 0 0 0 1 0 0 1 1 1 0 0 1 1 0 1 0 1 0 1 0 1 1 1 0 0 0 1 1 0 1 1 1 0 0 1 0 1 1 0 0 0 0 1 1 1 0 1 1 0 1 0 0

0 0 0 0 1 1 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 0 1 1 1 1 1 0 0 1 1 1 1 1 0 0 1 0 1 0 0 1 1 1 0 1 0 0 0 0 1 0 0 1 1 0 1 1 1 0 0 1

1 0 1 0 1 0 0 1 0 1 0 0 0 0 1 0 0 0 1 0 1 1 0 0 0 1 1 1 0 1 0 1 1 0 0 0 0 1 1 0 0 1 0 0 1 1 0 1 0 1 1 1 0 1 1 0 1 1 1 1 1 0

1 0 0 0 1 1 1 1 0 0 0 1 0 1 0 1 1 0 0 0 1 0 0 1 1 0 1 0 0 1 0 1 0 0 1 0 1 1 0 0 0 1 0 0 1 0 1 1 1 1 1 0 1 0 1 1 1 0 1 0 1 0

1 1 1 1 0 1 1 1 1 0 1 1 0 0 0 1 1 0 0 0 1 0 1 0 0 0 1 0 0 0 1 1 1 0 0 1 0 1 1 0 0 0 1 0 0 0 0 0 1 1 1 0 1 1 1 0 1 1 0 1 0 0

0 1 0 1 1 1 0 1 1 0 0 1 1 0 0 0 0 1 1 0 1 0 0 1 0 0 1 0 1 0 0 0 1 1 0 0 0 0 0 0 1 1 1 0 1 1 1 0 1 1 0 1 1 1 1 0 1 0 1 1 0 0

1 0 1 1 0 0 0 1 1 0 0 1 0 0 1 1 0 1 0 0 1 0 1 1 0 1 1 0 0 1 0 1 0 1 0 0 0 0 0 1 1 1 1 1 0 0 0 1 0 0 1 1 1 1 0 1 1 0 1 0 0 1

1 0 1 1 0 0 0 1 0 1 1 1 0 1 1 0 1 1 1 1 0 0 0 0 0 1 1 1 0 0 0 1 0 0 0 0 0 1 0 0 1 0 1 1 0 0 1 0 1 1 0 1 0 0 1 1 1 0 1 1 1 0

1 0 0 1 0 1 1 0 1 0 1 1 1 1 0 0 0 0 0 0 1 1 1 1 0 1 1 1 0 1 1 0 1 0 1 0 1 0 0 0 1 0 0 1 0 0 1 0 1 0 0 1 1 0 1 1 1 0 0 0 1 0

0 1 1 1 0 0 1 1 1 0 1 0 1 0 0 0 0 1 1 0 1 0 1 0 1 0 1 1 0 0 1 0 0 0 1 1 0 1 0 1 1 1 1 1 0 1 0 0 1 0 0 0 0 1 0 1 1 1 0 0 1 0

0 1 0 0 1 1 1 1 1 0 1 1 1 0 0 0 0 1 1 1 0 0 0 0 0 1 1 1 1 1 0 1 0 1 1 1 0 0 1 1 1 0 0 1 0 1 1 1 0 0 0 1 0 0 0 0 1 0 1 0 0 0

1 1 0 1 0 0 0 0 0 0 0 1 1 0 1 0 1 1 0 1 0 1 1 0 0 1 1 1 1 1 0 0 0 1 1 1 0 1 0 1 0 0 0 1 1 0 0 1 0 0 1 0 0 1 1 1 1 0 0 0 1 1

0 0 0 1 0 1 1 0 0 1 1 0 0 1 1 1 1 0 1 1 1 1 0 0 1 1 1 1 1 0 0 0 1 1 1 1 0 1 0 1 1 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 1 0 1 0 1 1

1 1 0 0 0 1 1 1 1 1 0 0 1 1 1 0 0 0 0 1 0 1 0 0 1 0 1 0 1 1 1 0 1 0 1 1 1 0 1 0 1 1 0 1 0 0 0 0 0 0 0 0 1 1 0 0 1 0 0 1 1 1

0 1 0 0 0 0 1 0 0 1 0 1 0 1 0 0 0 1 0 0 0 1 0 1 1 0 1 1 1 0 1 1 0 1 0 1 1 1 1 1 0 1 1 1 1 1 0 0 1 0 0 0 0 1 0 0 1 1 1 0 0 1

1 1 1 1 1 1 0 0 1 1 0 0 0 0 1 1 0 0 0 1 0 0 0 0 1 1 1 1 1 0 1 1 0 1 1 0 1 0 1 0 0 0 0 0 1 1 0 1 0 0 0 1 0 0 1 0 1 1 1 0 0 1

1 0 0 0 1 0 0 0 0 1 0 0 0 1 1 1 1 1 0 0 1 1 0 0 0 0 1 0 0 0 0 0 0 1 1 1 1 0 1 0 1 0 0 0 1 1 1 1 1 0 1 0 0 1 1 1 1 1 0 1 1 1

0 0 0 0 1 0 1 1 1 1 1 0 0 1 1 1 1 0 0 0 1 0 1 1 1 1 1 0 1 0 1 0 1 0 0 1 1 0 0 0 0 0 0 1 1 0 0 1 1 1 1 0 0 0 0 0 1 1 1 1 0 0

1 1 1 0 1 0 0 1 1 0 0 1 1 1 0 1 1 1 1 0 0 0 0 1 0 0 1 1 1 0 1 0 1 0 0 0 1 0 1 0 0 1 0 0 0 1 0 0 0 1 1 0 1 0 0 0 1 1 0 1 1 1

0 0 1 1 1 0 1 0 0 1 0 1 0 0 0 0 0 1 0 0 0 0 0 1 0 1 1 0 0 1 1 1 1 1 1 0 0 0 0 1 0 1 1 0 1 1 1 1 1 1 1 0 1 0 0 0 1 1 0 1 0 1

0 1 1 1 1 0 0 0 1 1 0 0 0 0 1 1 1 0 0 1 0 0 1 1 0 1 1 0 0 0 0 1 0 0 0 1 1 1 0 0 1 1 1 0 0 1 1 1 0 1 1 1 1 0 1 0 1 0 0 0 1 0

0 0 1 0 0 1 1 0 0 0 0 0 0 1 0 0 1 1 1 0 1 1 1 0 0 0 1 0 1 0 0 1 1 1 0 0 1 0 0 0 1 0 1 1 0 0 1 1 0 1 1 1 1 0 1 1 1 1 0 1 1 0

0 1 0 0 1 0 1 1 0 0 1 0 0 0 1 0 1 0 1 0 1 0 1 1 1 1 1 1 0 1 1 0 1 0 0 0 0 0 0 0 0 1 1 1 0 0 1 0 0 1 0 1 1 1 1 1 1 1 0 0 0 1

0 1 1 0 1 0 0 1 0 1 1 1 1 1 0 0 0 0 1 0 1 0 1 0 0 0 1 1 0 1 0 1 1 1 1 0 0 1 1 0 0 1 1 0 0 1 0 0 0 0 1 1 1 0 0 1 1 0 1 0 1 0

1 0 0 1 0 1 1 1 0 0 1 1 1 0 1 0 0 0 1 0 0 0 0 0 0 0 1 0 0 1 1 1 0 1 1 1 1 1 0 1 0 1 1 0 1 0 1 1 0 1 1 1 0 0 1 1 1 0 0 0 0 0

0 1 0 1 0 1 0 0 0 0 1 1 1 1 1 1 1 0 0 1 1 0 1 0 0 0 1 0 1 1 0 1 0 0 0 1 0 1 0 1 1 0 0 0 0 1 0 0 1 1 0 1 1 1 1 1 1 1 0 0 0 0

0 0 0 1 1 1 0 1 1 0 1 0 1 1 0 0 0 0 1 1 1 1 0 0 0 0 1 0 1 0 1 0 1 1 0 0 0 1 0 1 1 0 1 1 0 0 0 1 0 0 0 0 1 1 1 1 1 0 1 1 0 1

1 0 0 0 0 1 0 1 0 1 1 1 1 0 1 0 1 1 0 1 1 1 0 1 1 0 1 1 0 1 1 0 0 0 0 0 0 0 0 1 1 1 1 1 0 1 0 0 0 0 1 1 0 1 0 0 1 0 1 0 0 1

1 0 1 1 0 0 0 1 0 1 0 1 1 1 0 0 0 0 0 1 0 1 0 0 1 1 1 1 0 0 0 1 1 0 1 0 1 1 1 1 0 0 0 1 0 1 0 1 1 1 0 1 0 1 0 1 1 0 1 0 0 0

1 0 0 1 0 1 0 0 1 0 1 1 0 0 0 0 1 0 0 1 0 1 0 0 1 0 1 1 0 0 1 0 0 0 1 1 1 0 1 1 1 1 0 0 1 0 1 1 1 0 0 0 1 0 1 1 1 1 1 0 1 0

1 0 0 1 1 0 1 0 1 0 1 0 1 0 0 1 1 1 0 1 1 1 1 0 1 0 1 0 1 0 0 1 1 0 1 1 0 0 1 0 1 0 1 1 1 1 0 0 1 0 0 0 0 1 0 0 1 1 0 0 0 0

0 1 0 0 1 0 0 1 1 0 0 0 1 0 0 1 0 1 1 0 0 1 0 0 1 1 1 1 1 0 0 0 1 0 0 1 0 0 1 1 1 1 0 1 1 0 0 1 1 0 1 1 0 0 1 0 1 0 1 1 0 1

1 0 0 0 0 0 0 0 1 1 0 1 0 0 0 1 1 1 0 1 1 0 0 1 1 1 1 1 1 1 0 1 0 1 1 0 0 0 1 1 0 1 0 1 1 0 0 0 0 1 1 0 0 0 0 1 1 0 0 1 1 1

0 0 1 1 0 0 1 1 0 1 1 0 0 0 1 1 0 1 0 1 0 1 0 1 0 1 1 1 0 0 0 1 1 0 1 1 1 1 1 0 0 0 0 0 1 0 0 0 1 1 0 0 1 0 1 0 1 0 0 1 1 1

0 1 1 0 0 1 1 0 1 1 0 1 1 1 0 1 0 0 0 0 1 1 0 1 1 1 1 0 1 0 0 0 0 0 1 1 1 0 0 0 1 1 1 0 1 0 1 0 0 0 0 0 1 0 1 0 1 1 0 1 1 0

0 1 1 1 1 0 1 1 0 0 0 0 0 0 0 1 0 1 0 0 1 0 1 1 1 0 1 0 1 0 1 1 0 1 0 1 1 0 1 1 0 0 1 1 0 0 1 0 0 0 0 1 0 1 0 0 1 1 0 1 1 1

0 1 1 0 1 0 1 1 0 1 0 1 0 0 1 0 0 0 1 1 0 0 1 1 0 1 1 1 1 0 0 0 0 1 0 0 0 0 1 0 1 0 0 0 1 1 1 0 0 0 1 1 0 0 1 1 1 1 1 1 0 1

1 1 1 1 1 0 0 0 0 1 1 1 0 1 1 1 0 0 1 0 1 1 1 1 0 0 1 0 0 1 0 0 0 1 1 0 1 0 0 0 0 0 0 1 1 0 1 1 0 1 1 0 0 0 0 1 1 0 0 0 1 1

0 0 1 1 0 0 1 1 0 1 1 0 1 1 1 1 1 0 1 0 0 0 1 0 1 0 1 1 0 1 1 0 0 1 0 1 1 1 0 0 1 0 0 0 0 0 1 0 1 1 1 0 1 0 0 0 1 1 0 1 0 0

0 1 0 0 1 1 0 0 1 0 0 1 1 1 1 0 0 0 1 0 0 0 1 1 0 0 1 0 1 1 1 0 1 0 1 0 1 1 1 1 1 0 1 1 0 1 1 0 0 1 0 0 1 0 0 0 1 1 0 1 0 0

0 0 1 1 1 1 0 0 0 0 0 0 0 1 0 0 0 1 1 1 0 0 1 1 0 0 1 1 0 1 1 0 0 1 0 1 0 1 0 1 0 1 1 1 1 1 0 1 0 0 1 1 1 1 0 0 1 1 0 0 0 1

0 0 1 0 1 1 0 0 0 1 0 0 0 0 1 1 1 0 1 1 0 1 0 0 0 1 1 1 1 1 1 1 0 0 1 0 0 1 0 0 1 0 1 0 0 1 1 1 0 1 1 1 0 1 0 1 1 0 1 0 0 0

1 0 0 0 0 1 0 0 0 0 1 0 0 1 0 0 1 0 0 0 0 1 1 0 1 0 1 0 0 1 0 0 1 0 1 1 1 1 0 0 0 0 0 1 0 1 1 1 0 1 1 1 1 1 1 1 1 0 1 1 1 1

1 0 0 0 0 1 1 0 0 1 1 0 1 0 0 0 1 0 1 0 1 0 1 1 1 0 1 1 1 0 1 0 1 0 0 1 0 1 1 0 0 1 1 0 0 0 0 1 1 1 0 0 1 1 0 1 1 1 1 0 0 0

1 1 1 0 1 1 0 1 1 0 1 0 1 0 0 0 1 0 1 0 0 0 0 0 0 0 1 0 1 1 0 1 1 0 1 0 1 0 1 1 0 1 1 0 1 1 0 0 1 0 0 1 1 1 0 0 1 0 1 0 0 1

1 0 0 0 0 0 0 0 1 1 0 1 1 0 0 1 0 1 0 1 0 0 0 0 0 0 1 0 0 1 0 1 1 1 0 1 0 1 0 1 0 1 1 0 1 0 1 1 1 0 1 1 0 1 1 1 1 1 1 0 0 1

1 0 0 1 1 1 0 0 1 1 1 0 0 0 1 1 1 1 0 1 1 1 1 0 0 1 1 0 1 0 0 1 0 0 0 0 1 1 0 1 0 1 0 0 0 0 0 0 1 1 0 1 0 0 1 1 1 0 1 1 0 0

1 0 0 0 0 1 0 1 1 0 1 0 1 1 0 0 0 1 1 1 1 1 0 1 1 1 1 0 0 0 0 1 1 0 0 0 1 0 0 0 1 0 0 0 0 0 0 0 1 0 1 0 1 1 1 1 1 1 0 1 1 1

0 0 1 0 1 0 1 1 1 1 1 1 1 0 0 0 0 1 0 0 1 1 0 1 1 1 1 0 0 1 1 0 0 0 0 0 0 0 1 1 0 1 1 1 0 0 0 0 1 1 0 0 0 1 1 0 1 1 1 0 1 0

1 1 1 1 1 0 1 1 1 0 0 1 1 0 0 0 0 1 0 1 1 0 0 0 1 1 1 1 0 0 0 1 0 0 0 0 1 1 1 1 0 0 0 0 1 1 1 0 0 0 1 1 1 0 0 0 1 0 1 0 1 0

1 1 0 1 0 1 1 1 0 0 0 1 0 0 0 1 0 1 0 1 0 1 1 0 0 1 1 0 0 0 0 0 0 1 1 0 0 0 1 1 1 0 1 0 1 0 1 1 1 1 1 0 0 0 1 1 1 1 0 0 1 0

0 1 0 1 1 0 1 0 1 0 1 1 0 0 1 1 1 0 1 1 1 1 1 0 1 1 1 0 0 0 0 0 0 1 0 1 0 0 0 0 1 0 0 1 1 0 0 0 1 1 0 1 1 1 0 0 1 0 0 1 1 0

Edited November 10, 2010 by bushindo

[araver]

Actually 2 solutions since there are 2 fixed points in the permutation at positions 27 and 57 and your vector y contains 1s at positions 27 and 57 (the fixed points positions). For another y, there might be possible to distinguish an unique solution.

59	7	24	12	58	38	61	21	49	62	56	8	11	15	34	45	48	9	23	40	55	20	47	60	22	18	27	44	36	19	14	42	17	2	28	35	10	30	25	13	4	33	53	41	39	31	3	46	1	51	5	43	50	6	32	52	57	37	54	16	26	29

and

59	7	24	12	58	38	61	21	49	62	56	8	11	15	34	45	48	9	23	40	55	20	47	60	22	18	57	44	36	19	14	42	17	0	28	35	10	30	25	13	4	33	53	41	39	31	3	46	0	51	5	43	50	6	32	52	27	37	54	16	26	29

Also, only the first 10 powers were needed for this particular vector y to determine P.

[araver]

Create a vector by taking the first X positions for digit Y of the vector (E.g. X=10, Y=1 take the first 10 positions for the first column).

These are the "visitors" for place Y during successive applications of the permutations.

Search for the same vector starting from the second row in other columns and you will find a single column Z where this vector repeats. If you find multiple column, increase X till there is no ambiguity. If there is an ambiguity even for X=60, then you're looking at a fixed point or at similar portions of the input vector which are permuted the exact same way.

The column Z is the column where the digits in place Y go next in the permutation.

So in the Zth place in the permution you can write Y (Y goes to Z.)

Repeat for all Ys (1:62).

Can be done in a spreadsheet, with two extra-tables besides the input one:

- one for subtracting column vectors (&transpose them) to get patterns

- one for searching the pattern.

And another for fast multiply with row number to write the permutation.

Loved it (because it's very similar to crib finding and classical code breaking.)

[superprismatic]

(49 34 47 41 51 54 2 12 18 37 13 4 40 31 14 60 33 26 30 22 8 25 19 3 39 61 27 35 62 38 46 55 42 15 36 29 58 6 45 20 44 32 52 28 16 48 23 17 9 53 50 56 43 59 21 11 57 5 1 24 7 10) and 27 and 57 can be interchanged.

Edited November 10, 2010 by superprismatic

[bushindo]

Actually 2 solutions since there are 2 fixed points in the permutation at positions 27 and 57 and your vector y contains 1s at positions 27 and 57 (the fixed points positions). For another y, there might be possible to distinguish an unique solution.

59	7	24	12	58	38	61	21	49	62	56	8	11	15	34	45	48	9	23	40	55	20	47	60	22	18	27	44	36	19	14	42	17	2	28	35	10	30	25	13	4	33	53	41	39	31	3	46	1	51	5	43	50	6	32	52	57	37	54	16	26	29

and

59	7	24	12	58	38	61	21	49	62	56	8	11	15	34	45	48	9	23	40	55	20	47	60	22	18	57	44	36	19	14	42	17	0	28	35	10	30	25	13	4	33	53	41	39	31	3	46	0	51	5	43	50	6	32	52	27	37	54	16	26	29

Also, only the first 10 powers were needed for this particular vector y to determine P.

Excellent! Thanks for the explanation of your strategy. I'm glad you enjoyed it.

(49 34 47 41 51 54 2 12 18 37 13 4 40 31 14 60 33 26 30 22 8 25 19 3 39 61 27 35 62 38 46 55 42 15 36 29 58 6 45 20 44 32 52 28 16 48 23 17 9 53 50 56 43 59 21 11 57 5 1 24 7 10) and 27 and 57 can be interchanged.

I think something has gone amiss here. This solution does have a cycle of 60, so it properly takes y back to itself on the 60th power. The powers of P in between 0 and 60, however, don't match the data though.

Edited November 10, 2010 by bushindo

[superprismatic]

Excellent! Thanks for the explanation of your strategy. I'm glad you enjoyed it.

I think something has gone amiss here. This solution does have a cycle of 60, so it properly takes y back to itself on the 60th power. The powers of P in between 0 and 60, however, don't match the data though.

My permutation is stated in a "where to" way instead of a "where from". So, the first element of 49

means that the first element of line i becomes the 49th element of line i+1. Apparently, you were

expecting a "where from", so you were expecting the 1 (59th element) of line i to become the first

element of line i+1. I couldn't tell which you wanted because the example of the reversal is the

same in both notations. I just checked and araver's is the "where from" version of my "where to".

So, my answer does match the data.

[bushindo]

My permutation is stated in a "where to" way instead of a "where from". So, the first element of 49

means that the first element of line i becomes the 49th element of line i+1. Apparently, you were

expecting a "where from", so you were expecting the 1 (59th element) of line i to become the first

element of line i+1. I couldn't tell which you wanted because the example of the reversal is the

same in both notations. I just checked and araver's is the "where from" version of my "where to".

So, my answer does match the data.

Ah, that's it. Good work! Thanks for working on this problem.