[superprismatic]

Bushindo's nice "Find the permutation" problem, which intermingled

a binary array with permutations, inspired me to strike out in a

similar vein. Here's the outcome.

Consider the permutation on 16 things:

 1 -> 13

 2 ->  5

 3 -> 14

 4 ->  3

 5 -> 12

 6 ->  9

 7 -> 11

 8 -> 10

 9 -> 16

10 ->  6

11 ->  1

12 -> 15

13 ->  7

14 ->  4

15 ->  2

16 ->  8

[/code]


This can be written in [b]cyclic form[/b] like this:

(1,13,7,11)(2,5,12,15)(3,14,4)(6,9,16,8,10) so that

the cyclic structure of the permutation is easily seen.

(1,13,7,11) is just shorthand for 1 -> 13 -> 7 -> 11 -> 1 ...,

and is seen to be a 4-long cycle.  We will use this

cyclic form for permutations in this problem.



We will assign a score to any permutation of 16 elements

by using the 16×16 array of integers below (the rows and

columns are numbered for ease of reference).  The permutation

will decide which elements of this array will be added

together to form the score.  If i -> j in the permutation

(or, equivalently, if j follows i in the cyclic form of it),

then the element in the i[sup]th[/sup] row and j[sup]th[/sup] column is chosen

to be in the sum.  For example, the score for the above

permutation is seen to be 3277 because

[code]

 219 from row  1, column 13

+226 from row  2, column  5

+131 from row  3, column 14

+136 from row  4, column  3

+218 from row  5, column 12

+230 from row  6, column  9

+254 from row  7, column 11

+203 from row  8, column 10

+245 from row  9, column 16

+241 from row 10, column  6

+185 from row 11, column  1

+201 from row 12, column 15

+246 from row 13, column  7

+135 from row 14, column  4

+157 from row 15, column  2

+250 from row 16, column  8

-----

3277 total


The array:

[code]

      1    2    3    4    5    6    7    8    9   10   11   12   13   14   15   16

 1  -155 -107   94   45  -34  -19   -7  111  -45  -64  233  -97  219  251   28  254

 2  -199   96    4   42  226 -101  -64 -223   31  155 -132  119  164  -50 -109  -57

 3  -202   99 -218  -91  239   84  121  -62   18   24  208   35 -174  131 -250  106

 4    66   11  136 -230  141  -99 -136  134    3  -63   88   -2   95   74  -37   39

 5  -180  109  -23  -32 -141  -50  141   62   98   76 -248  218  112 -147  194 -105

 6   188   92   65    5  116  -28  196 -150  230  141   41 -142  -56  130   59 -218

 7    47 -153  -59 -102  246   60 -158 -125 -172   55  254  223  107 -235 -208  234

 8    94  174  127    7  106 -160  159 -194  -98  203 -208  129   -5  250   62  240

 9   231 -136  183  -21  229 -221  -82   -1 -240  189   75  -73   13  -43  -70  245

10     4 -180   51   33  -94  241  231 -133 -191 -224  145  227  -17   65  -69  212

11   185 -129  -74  152 -145    4    0   59 -143   30  112  193  172  -21  -59 -205

12  -239 -121   60 -174  154 -155 -150   -8 -147 -146 -107 -231 -137 -133  201   59

13   -97 -113  -73   13  141  204  246  -68  193  190 -110  205 -130   32   44  -54

14  -109 -176 -125  135  184  167  152  156 -228  248  142  155  168   17 -183 -240

15  -131  157   19   -2  117   83  206  247 -100  -10 -193  -93  149  -31  -96   66

16   -61  -21  152  -22   35  136  180  250   81  199  182  -27   87    5   89 -166

The problem is in 3 parts:

1. Find the highest scoring permutation which has one 16-long cycle

2. Find the highest scoring permutation which has two 8-long cycles

3. Find the highest scoring permutation which has four 4-long cycles

[araver]

My greedy answer - score 3309 - cycles:

1	13	6	9

2	5	12	15

3	7	11	4

8	14	10	16

[araver]

My branch&bound answer: score 3430 - 16-longcycle:

(1, 11, 4, 3, 5, 12, 15, 2, 13, 7, 16, 8, 14, 10, 6, 9) 

[araver]

My branch&bound answer: score 3330 - 2x8-long cycles:

(1, 11, 4, 8, 14, 10, 6, 9)

(2, 13, 7, 16, 3, 5, 12, 15)

 

Edited November 13, 2010 by araver

[superprismatic]

My branch&bound answer: score 3330 - 2x8-long cycles:

(2, 13, 7, 16, 3, 5, 12, 15)

(1, 11, 4, 8, 14, 10, 6, 9)

You got all three correct and you did it very quickly! You must be a good programmer.