An arrangement machine reshuffles an input line by interchanging one pair of elements per step. In Step 1 it interchanges the elements standing at the 1st and the last positions, in Step 2 those at the 2nd and the second-last positions, in Step 3 those at the 3rd and the third-last positions, and so on. Nothing is ever taken out of the line — the two elements simply trade places — and the machine stops when no untouched pair is left to interchange. Input: 52 amber 17 crest 46 dune 73 flint 28. How many steps are needed to complete the rearrangement of the above input?

Question

Accepted Answer

4. There are nine elements, so the pairs are (1,9), (2,8), (3,7) and (4,6) — four pairs in all. Position 5, held by 46, has no partner and is never touched, so the machine halts after Step 4: 28 flint 73 dune 46 crest 17 amber 52. Counting the lonely middle element as a fifth step is the standard error; counting one step per element gives nine, and one step per element bar the last gives eight.

Step-by-Step Solution

Master this topic in 30 minutes a day.

More Input-Output practice