Best shuffle: Difference between revisions
Content added Content deleted
(→{{header|Java}}: fixed bug, added optimization) |
|||
| Line 808: | Line 808: | ||
The approach taken requires 2n memory and will run in O(n^2) time swapping once per final changed character. The algorithm is concise and conceptually simple avoiding the lists of indices, sorting, cycles, groups, and special cases requiring rotation needed by many of the other solutions. It proceeds through the entire string swapping characters ensuring that neither of the two characters are swapped with another instance of themselves in the ''original'' string. |
The approach taken requires 2n memory and will run in O(n^2) time swapping once per final changed character. The algorithm is concise and conceptually simple avoiding the lists of indices, sorting, cycles, groups, and special cases requiring rotation needed by many of the other solutions. It proceeds through the entire string swapping characters ensuring that neither of the two characters are swapped with another instance of themselves in the ''original'' string. |
||
Additionally, this can be trivially modified to randomize the shuffle |
Additionally, this can be trivially modified to randomize the shuffle by uncommenting the line |
||
<lang icon># every !t :=: ?t # Uncomment to get a random best shuffling</lang> in <tt>bestShuffle</tt>. |
|||
<lang icon>procedure main(args) |
<lang icon>procedure main(args) |
||
while scram := bestShuffle(line := read()) do |
while scram := bestShuffle(line := read()) do |
||