Rosetta Code

Talk:Best shuffle: Difference between revisions

Page Discussion

Talk:Best shuffle (view source)

Revision as of 19:53, 21 July 2016

735 bytes removed ,  7 years ago
m
added a section header to the 1st comment so that the TOC (table of contents) appears in the correct location.
m (added a section header to the 1st comment so that the TOC (table of contents) appears in the correct location.)
 
(11 intermediate revisions by 6 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 17 ⟶ 18:
:::::: Very clear. Go for it! --[[User:Dgamey|Dgamey]] 20:27, 16 May 2011 (UTC)
 
== J implementation notes ==
 
<lang j>bestShuf2 =: verb define
equivs=. (\:#&>)@:(<@I.@=) y
y C.~ (;equivs) </.~ (i.#y) |~ #>{. equivs
)</lang>
 
This mechanism has two steps.
 
First, we group indices for multiple instances of the same character, with indices for the most frequently occurring character appearing first. In other words:
 
<lang j> (\:#&>)@:(<@I.@=) 'abracadabra'
┌──────────┬───┬───┬─┬─┐
│0 3 5 7 10│1 8│2 9│4│6│
└──────────┴───┴───┴─┴─┘</lang>
 
Here, 'a' is the most frequently occurring character and it appears at character indices 0, 3, 5, 7 and 10.
 
Next we find the number of occurrences of the most frequently occurring character and we group these rearranged indices into that many distinct groups. In other words if <code>equivs=: (\:#&>)@:(<@I.@=) y=:'abracadabra'</code>, we need 5 distinct groups of indices to separate the five instances of the letter 'a'. We do this by taking the grouped character indices from before, ignoring the grouping and counting to 5, repeatedly (the first index goes in the first group, the second goes in the second group, and so on):
 
<lang j> (i.#y) |~ #>{. equivs
0 1 2 3 4 0 1 2 3 4 0
(;equivs) </.~ (i.#y) |~ #>{. equivs
┌─────┬───┬───┬───┬────┐
│0 1 6│3 8│5 2│7 9│10 4│
└─────┴───┴───┴───┴────┘</lang>
 
These new groupings represent [http://www.jsoftware.com/help/dictionary/dccapdot.htm cycles] and are used to permute the original sequence of characters.
 
: Maybe it's late or just missing something (and my J just sucks), but if I read this right this should lead to the permutation "baadcbaraar" with position 4 unchanged for a score of 1. It certainly isn't obvious how the posted solution arrives at "bdabararaac". --[[User:Dgamey|Dgamey]] 02:00, 18 April 2011 (UTC)
 
:: Could you explain your reasoning in more detail? (I am not getting your point.) For now, I will note that the above shows 10 and 4 in a cycle, which means the character at position 4 will be swapped with the character at position 10. (I assumed, by the way, that when you said "position 4" you meant index value 4 in the original string which corresponds to the first instance of the letter 'c' and which has position 9 in the list of equivalent indices. But since the remainder of 9 divided by 5 is 4, this letter also winds up being in the cycle with position 4 in the list of cycles.) --[[User:Rdm|Rdm]] 16:27, 23 May 2011 (UTC)
:: P.S. I am considering replacing these notes, so they follow the current entry. Please let me know how you want to deal with your comment in the re-write? Thanks. --[[User:Rdm|Rdm]] 16:41, 23 May 2011 (UTC)
:: P.P.S. If you are having problems with the J: I used the same underlying logic in the Javascript implementation. The C and Clojure versions also use this approach. --[[User:Rdm|Rdm]] 17:00, 23 May 2011 (UTC)
 
In degenerate cases, where more than half of the characters are the same, some of these cycles will only involve one character, which can not move to another position.
 
Note that we can accomplish this without sorting. The important issue is that each cycle involving the same character be distinct from other cycles.
 
<lang j>bestShuf3 =: verb define
y C.~ (;eqs) </.~ (i.#y) |~ {:$> eqs=. <@I.= y
)</lang>
 
Or, for fans of zero-point code: <code>bestShuf4=: (C.~ ; </.~ {:@$@:> | i.@#@;) <@I.@=</code>
 
== Javascript implementation ==
Line 169 ⟶ 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 inner list: ((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.
Line 179 ⟶ 138:
:: The code as posted doesn't compile. After removing two right parens, it compiles but produced wrong results: <code>abracadabra dcbaabarraa (2)</code>.
:: I looked at the code again, using <code>random</code> can't warrant correct results (note that a random shuffle can not garantee a result with minimal overlapping. Since it's random, you can't even garantee that after infinitely long run.) I'll mark it incorrect. --[[User:Ledrug|Ledrug]] 11:22, 14 October 2011 (UTC)
:::oops, i pasted the code back into the interpreter, to test it and didn't get any errors. bothi use SBCL, which ignores extra parens silently! and CMUCL where i tested once only gave a warning.--[[User:EMBee|eMBee]] about18:21, the14 extraOctober 2011 )(UTC)
:::thank you for clearing up the task description. i don't know when i'll find the time to fix it though.--[[User:EMBee|eMBee]] 11:52, 14 October 2011 (UTC)
 
: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)
Retrieved from "https://rosettacode.org/wiki/Special:MobileDiff/167823...167835"