Talk:Best shuffle: Difference between revisions
→Common Lisp
Line 169:
::::i looked at the description of the C solution (but i didn't study the code), and i don't quite understand how this is supposed to work.
::::it splits the input into sets, starting a new set when a letter is already in a set, so for abracadabra this would produce ((a b r) (a c) (a d) (a b r) (a)), but that is not right, to make it work the sets should be: ((a b r) (a c) (a d) (a b) (r a)). there is also talk about putting the longest set first, but i don't understand how it prevents a letter from falling into the same place as the input if sets are reordered.--[[User:EMBee|eMBee]] 14:39, 14 October 2011 (UTC)
:::::''In other words, instead of making the sets ((a b r) (a c) (a d) (a b r) (a)) I was thinking you could instead make the sets of the indices which select ((a a a a a) (b b) (c) (d) (r r)). In other words, you would shuffle the lists ((0 3 5 7 10) (1 8) (4) (6) (2 9)) perhaps getting ((10 0 5 7 3) (8 1) (4) (6) (9 2)). Then you would generate the lists of indices which might have corresponded to something like your ((a b r) (a c) ...). In this case, we first restructure the index lists based on the length of the longest set: ((10 0 5 7 3) (8 1 4 6 9) (2)). Then we form new groups picking the first, second, third, .. from these "equal length except for the last one" lists: ((10 8 2) (0 1) (5 4) (7 6) (3 9)). Finally, you go back to the original string and you rotate characters within the positions in these groups. In other words, using capital letters to represent letters from positions (10 8 2): 'abRacadaBrA' becomes 'abBacadaArR', (0 1): ABbacadaarr becomes BAbacadaarr, (5 4): babaCAdaarr becomes babaACdaarr, (7 6): babaacDAarr becomes babaacADarr, (3 9): babAacadaRr becomes babRacadaAr. In other words, if I had a different 'a' position for my first 'a' I would be rotating the first 'r' to that position instead... Is this a clear enough presentation of the concept? --[[User:Rdm|Rdm]] 15:59, 14 October 2011 (UTC)''
<del>
i posted a function for generating a random permutation as per the task description, and am still working on comparing the results.
| |||