Jump to content
BrainDen.com - Brain Teasers
  • 0
Sign in to follow this  
bushindo

Question

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

P2( 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 P0y, P1y, P2y, ....., P60y. Note that P has a cycle of 60, as P60y = 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 by bushindo

Share this post


Link to post
Share on other sites

6 answers to this question

Recommended Posts

  • 0

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.

Share this post


Link to post
Share on other sites
  • 0

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.) :D

Share this post


Link to post
Share on other sites
  • 0

(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 by superprismatic

Share this post


Link to post
Share on other sites
  • 0

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 by bushindo

Share this post


Link to post
Share on other sites
  • 0

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.

Share this post


Link to post
Share on other sites
  • 0

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.

Share this post


Link to post
Share on other sites

Join the conversation

You can post now and register later. If you have an account, sign in now to post with your account.

Guest
Answer this question...

×   Pasted as rich text.   Paste as plain text instead

  Only 75 emoji are allowed.

×   Your link has been automatically embedded.   Display as a link instead

×   Your previous content has been restored.   Clear editor

×   You cannot paste images directly. Upload or insert images from URL.

Loading...
Sign in to follow this  

  • Recently Browsing   0 members

    No registered users viewing this page.

×
×
  • Create New...