Anonymous user
Talk:Best shuffle: Difference between revisions
m
added a section header to the 1st comment so that the TOC (table of contents) appears in the correct location.
(→Common Lisp: SBCL ignores extra parens in the repl? gee...) |
m (added a section header to the 1st comment so that the TOC (table of contents) appears in the correct location.) |
||
| (7 intermediate revisions by 5 users not shown) | |||
Line 1:
== appreciation comment ==
This was a fun algorithm to write --- lots of twists and turns. [[User:Gerard Schildberger|Gerard Schildberger]]
Line 125 ⟶ 126:
::::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)). Except they are really not sets, but sequences which means we can shuffle them. 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
<del>
Line 141 ⟶ 142:
:Hi eMBee, the task description should be read as meaning that there may be several shuffles with the same best score. If run with the same input a second time, there should be a chance that another of the shuffles which equal the best score is given. Generating all permutations then scoring them and filtering them could give the right answer, but might take too long as input sizes grow --[[User:Paddy3118|Paddy3118]] 11:33, 14 October 2011 (UTC)
== Best? ==
The best (in the ordinary sense of the word) shuffle is the result of a random process, in which every possible permutation has a 1/n! chance of occurring, including the original sequence itself. Does this "best" term come from some literature on random sequences? [[Special:Contributions/192.139.122.42|192.139.122.42]] 22:45, 14 October 2011 (UTC)
: Probably not. By requiring minimal overlapping with the original string, it kills a lot of randomness. But the task's intention is pretty clear, though. --[[User:Ledrug|Ledrug]] 23:03, 14 October 2011 (UTC)
:Best is strictly defined in the task as being (one of) the shuffles that give the minimum of characters in the same place. In terms of implementations, an implementation that when run repeatadly can give a different member of the best shuffles is to be preferred. the word/term ''best'' has its meaning added to for the purposes of the task. --[[User:Paddy3118|Paddy3118]] 05:12, 15 October 2011 (UTC)
== Perl 6 ==
Perl 6 example is not correct for all words.
Sub best-shuffle for word 'aaaabbbbcccc' returns 'bbbcaaccaabc, 1', but there exists better shuffle, for example 'bbbbccccaaaa'.
--[[User:Wamba|Wamba]] ([[User talk:Wamba|talk]]) 18:43, 24 June 2015 (UTC)
| |||