PROJECT EULER · #0595
Incremental Random Sort
A deck of cards numbered from
The cards are to be sorted into ascending order using the following technique:
- Look at the initial sequence of cards. If it is already sorted, then there is no need for further action. Otherwise, if any subsequences of cards happen to be in the correct place relative to one another (ascending with no gaps), then those subsequences are fixed by attaching the cards together. For example, with
cards initially in the order 4123756, the cards labelled 1, 2 and 3 would be attached together, as would 5 and 6.
- The cards are 'shuffled' by being thrown into the air, but note that any correctly sequenced cards remain attached, so their orders are maintained. The cards (or bundles of attached cards) are then picked up randomly. You should assume that this randomisation is unbiased, despite the fact that some cards are single, and others are grouped together.
- Repeat steps 1 and 2 until the cards are sorted.
Let
Find
Write-up coming later
The complete problem is available here. An approach, code, and answer will be added later.