Talk:Best shuffle

This was a fun algorithm to write --- lots of twists and turns. Gerard Schildberger

Task Description

I think it would improve the task description if we said something along the lines of "Shuffle the characters of a string to produce a string as different as possible from the original. That is, the maximum # of characters in the output differ from the characters at the corresponding positions at the input". Only more concise :). I say that because the current wording lends itself to a trivial solution - reversing the string (because it doesn't make clear that a "character" is different only if its value, not its index, is different). In fact, that's how I initially interpreted the task (character=index), until I saw the solutions were a lot more complex than reverse().

--DanBron 18:28, 15 December 2010 (UTC)

Well, it says "characters" not "indexes". But feel free to change the wording as you see fit. Fwend 20:16, 15 December 2010 (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 equivs=: (\:#&>)@:(<@I.@=) y=:'abracadabra', 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 cycles and are used to permute the original sequence of characters.

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: bestShuf4=: (C.~ ; </.~ {:@$@:> | i.@#@;) <@I.@=

Javascript implementation

abracadabra, bdabararaca, (1)

Thank you for implementing a Javascript version. I'm afraid it needs tweaking, however. The word "abracadabra" can be shuffled without any character in the original position. Fwend 19:01, 17 December 2010 (UTC)

Oops, thank you, I should have paid attention to the results I was getting. --Rdm 19:15, 17 December 2010 (UTC)

C entry

"... every character is considered unique in a word and that's why grrrrr also has a score of 0."

The score is supposed to give the number of positions that have the same character value as before. It's not very important, but makes it easier to quickly see if you've achieved the optimal result.

Also the code doesn't shuffle the characters. Perhaps you should imagine the routine being used in a word game or puzzle. The results that this code produces, although clever in the way it solves the problem, wouldn't be very satisfactory. Fwend 18:53, 6 January 2011 (UTC)

The problem with the C entry is that it does not work in the general case. Consider, for example:

<lang>Enter String : aabbbbaa

aabbbbaa, aabbbbaa, (0)</lang>

(The correct answer, here, would be bbaaaabb).

--Rdm 20:24, 6 January 2011 (UTC)