Programming puzzles: processing lists!

[DavidM]

(06-06-2017 01:44 PM)pier4r Wrote:  I was curious how solid it was in shuffling the list, since I do not know the algorithm (any chances to share the idea?).

Certainly.

LSHF is essentially a faster/more efficient SysRPL implementation of this routine, which you may recognize from another posting:

Code:

ShufList
\<<
  @ explode the list onto stack and save the size (sz)
  OBJ\-> \-> sz

  \<<
    @ loop: for list item positions 1 to (sz-1), choose a
    @ random item from the remaining candidates and move it
    @ to the target position

    @ note: stack positions (sz...1) are numbered inversely to
    @ list positions (1...sz)

    @ x represents the current target position
    sz 2 FOR x

      @ pick a random item position from the remaining pool
      x RAND * CEIL

      @ move the chosen item to stack level 1
      ROLL

      @ move the chosen item to the current target position
      x ROLLD

    @ update target to the next position
    -1 STEP

    @ implode the resulting list data
    sz \->LIST
  \>>
\>>

Its "randomness" is entirely dependent on the quality of the internal RAND function. Although I didn't realize it at the time I wrote it, apparently this method has a name: Durstenfeld's Version of the Fisher-Yates Shuffle.

For what it's worth, this came about because I noticed that the previous routine I used ("RANL" from the 1-Minute Marvels) gave biased results. RANL is a bit smaller, but the results seem questionable to me. I'll leave the analysis up to those more qualified. If you take a quick look at sample results from RANL, though, I think you'll quickly see what I'm referring to. Here's a sample run of 20 iterations of running RANL on a single list containing the integers 1-20 in order:

{ 1 2 3 4 5 6 14 7 20 8 19 9 18 15 17 10 11 16 12 13 }
{ 1 2 3 4 5 14 6 7 8 9 19 10 18 11 16 15 20 12 17 13 }
{ 1 2 3 4 5 6 7 8 9 15 20 14 10 11 19 12 18 13 16 17 }
{ 1 2 3 4 5 6 16 18 7 20 8 9 10 11 15 19 17 13 12 14 }
{ 1 2 3 17 4 5 6 7 8 14 9 13 10 11 19 12 16 18 15 20 }
{ 1 2 3 15 4 5 6 12 20 7 8 9 14 16 10 11 13 17 19 18 }
{ 1 2 3 4 5 6 7 17 16 15 8 19 18 9 10 11 12 20 13 14 }
{ 1 2 3 20 4 5 6 7 8 9 10 11 19 12 15 18 13 17 16 14 }
{ 1 2 3 4 5 6 20 14 7 15 18 16 8 9 19 17 13 10 11 12 }
{ 1 2 3 4 18 5 6 16 7 8 9 19 20 10 11 14 13 12 17 15 }
{ 1 2 3 4 5 20 6 7 15 8 17 9 14 10 13 11 18 12 19 16 }
{ 1 2 3 14 4 19 5 6 7 13 8 9 16 10 15 11 20 18 12 17 }
{ 1 2 3 15 4 5 18 6 7 14 8 9 16 20 10 11 12 17 13 19 }
{ 1 2 3 15 4 5 6 7 20 8 9 10 12 11 19 18 17 16 13 14 }
{ 1 2 3 4 5 6 7 8 9 10 18 19 11 20 17 15 16 12 14 13 }
{ 1 2 16 3 4 5 19 6 15 7 8 9 10 17 14 11 12 18 13 20 }
{ 1 2 3 16 4 5 6 18 14 7 19 17 8 9 10 11 12 13 20 15 }
{ 1 2 3 4 5 6 17 18 7 8 15 13 9 10 12 20 14 16 11 19 }
{ 1 2 3 19 4 15 5 6 7 8 9 10 11 12 13 17 18 16 14 20 }
{ 1 17 2 3 4 5 6 7 18 8 15 14 9 10 11 12 19 13 16 20 }

...and the same test using the ShufList routine:

{ 14 10 3 1 12 11 18 19 17 7 13 2 9 4 16 5 20 15 6 8 }
{ 14 11 8 6 9 1 7 5 19 17 2 13 4 18 3 12 20 10 16 15 }
{ 3 15 10 6 19 20 11 5 9 16 2 8 4 13 18 17 14 12 7 1 }
{ 15 8 5 3 1 12 9 2 13 16 11 18 6 14 20 7 19 10 4 17 }
{ 17 10 5 9 20 11 19 7 18 16 8 6 3 13 2 14 1 12 4 15 }
{ 13 9 7 11 8 2 16 3 4 20 5 18 14 15 17 6 10 19 12 1 }
{ 4 17 1 8 16 13 2 11 14 20 19 9 18 10 3 7 6 12 5 15 }
{ 8 20 2 3 4 16 7 10 17 5 13 14 6 1 18 11 15 9 12 19 }
{ 2 7 3 8 16 12 17 5 13 1 14 19 10 18 9 15 11 4 6 20 }
{ 9 3 20 11 5 13 19 2 1 18 7 4 16 8 10 15 6 17 12 14 }
{ 17 15 6 5 11 3 4 20 16 7 19 13 14 2 8 12 18 10 9 1 }
{ 18 13 4 20 1 17 5 7 6 15 8 11 10 16 2 9 19 3 14 12 }
{ 11 4 13 16 6 8 7 12 15 19 2 1 5 18 10 14 9 3 17 20 }
{ 20 8 3 11 6 18 15 12 4 2 16 9 13 19 1 14 10 17 7 5 }
{ 6 11 9 12 15 13 4 3 20 2 17 10 19 7 8 14 16 1 18 5 }
{ 4 10 18 16 20 19 17 3 12 11 7 2 9 15 5 6 8 14 13 1 }
{ 18 5 11 14 17 15 20 7 19 2 16 3 10 4 1 6 8 9 12 13 }
{ 18 15 6 10 5 8 4 12 17 13 20 1 3 7 16 9 2 14 11 19 }
{ 3 6 17 7 10 5 4 19 16 1 13 9 12 18 8 20 11 15 2 14 }
{ 2 4 14 6 7 1 13 16 3 10 12 19 20 17 5 9 18 8 11 15 }