You have a list of the integers 1 through N in some random order, and you are going to attempt to sort them. The only operation you have is to randomize any subset of these integers. Specifically, you may select any subset of the integers and lock them in place, and then the other ones get rearranged randomly. You may perform this operation as many times as you like, but want to do it as few times as possible.
Given the initial list of integers, what is the optimal average number of steps it will take to get the list in order?
The original puzzle had a bit more coding bubble-wrap around it, but not too much. It also had a nicer explanation of why the algorithm is so weird, but whatever.
As a few specific examples, if the initial list is (2 1 3), you can hold the 3 in place and randomize the other two until they fall in place, this will take on average 2 steps. If the initial list is (2 1 4 3) you can hold the first two in place until the second two land in order and then hold the second two in place until the first two land in order. This will take 4 steps on average. Given the initial list, is there an easy way to determine how many steps it will take on average? (Hint: there is, or I wouldn't consider this puzzle interesting).
1 comment:
If there are initially K items out of place, then the optimal strategy will have K randomizations on average.
Any strategy is optimal as long as each of the randomized subsets (1) contain no items in the correct place, and (2) every member of the subset belongs in the place now occupied by another member of the subset. The simplest way to do this is to just always randomize the full set of all out-of-place items, but other strategies may also be optimal as long as they meet the criteria above (as your second example shows).
Sketch of proof: in any randomization of a subset with the two properties above, on average one of the items will land in the correct spot. It will then take, on average, K randomization operations to put the K out-of-place items in place. (This can be shown using induction.)
Any subset that does not have these properties, the expected increase in in-place-items will be strictly less than one.
Post a Comment