|
:::::: 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 ==
|