4 ms·
Edit: I misinterpreted the parent; see below. If by 'shuffle' you mean like Fisher-Yates, this can't work all the time, since that can produce, e.g. 0, 1, 2, 3
by akalin 9y ago
Edit:
I misinterpreted the parent; see below.
If by 'shuffle' you mean like Fisher-Yates, this can't work all the time, since that can produce, e.g. 0, 1, 2, 3, 4, 5 -> 1, 0, 4, 5, 3, which has two cycles.
If by 'shuffle' you mean like Fisher-Yates, but not leaving an element in its original position, (i.e., generating a derangement) then this doesn't suffice either, since notice that the same example satisfies that condition and yet still has two cycles. You need Sattolo's algorithm (or something like it) to guarantee a single cycle.
- mistaken 9y agoThat's not what the parent meant. You shuffle the array with e.g. Fisher-Yates and then create a permutation from the shuffled array. That always gives a permutation that has one cycle. What you did was create a permutation from the original and the shuffled variant which has the problems you describe...