AMG: I guess RS wanted this page, so here goes... :^)

RS: Oops, sorry, what I meant was Shuffle a list ...

AMG: Ah, well, at least I got to write another un/sorting story page.

This page discusses shuffling algorithms and implementations thereof.

Here's a proc, adapted from unsort:

proc shuffle {data} { set rand_data [list] foreach elem $data { lappend rand_data [list [expr {rand()}] $elem] } set result [list] foreach elem [lsort -real -index 0 $rand_data] { lappend result [lindex $elem 1] } return $result }

It works, but it's seems suboptimal.

For starters, the real sort bothers me. I imagine sorting by integer would be more efficient, but then again producing random integers is (currently) slower than producing random reals. Change rand() for int(0x7fffffff * rand()) and -real for -integer and it winds up taking longer. See the benchmark below. (By the way, how am I supposed to portably get the maximum and minimum integer?)

Next, having up to three copies of the list (one of which is augmented) appears to be a waste of RAM.

So would it be better to do an in-place shuffle? For each element of $data it could swap with another, randomly-selected element of $data. I'll take a shot at it:

proc shuffle {data} { set length [llength $data] for {set idx_1 0} {$idx_1 < $length} {incr idx_1} { set idx_2 [expr {int($length * rand())}] set temp [lindex $data $idx_1] lset data $idx_1 [lindex $data $idx_2] lset data $idx_2 $temp } return $data }

Big improvement.

Here's my magical test data:

set data [lrepeat 100000 x y z z y]

If you're trying this at home from your interactive tclsh, you might want to type "; puts -nonewline {}" after the end of the above line or else its printed result will scroll for a very long time.

Now I time the shuffles:

.................................................. : : 400 MHz : 1500 MHz : :....................:.............:.............: : 1, random reals : 21.847024 s : 9.541117 s : : 2, random integers : 24.649960 s : 9.857447 s : : 3, in-place swaps : 7.650484 s : 2.328508 s : :....................:.............:.............:

Wow, I think I will go with #3! Hold on while I update unsort... :^)

AMG: Per Lars H's suggestion, I improved the code again. As Lars explains in unsort, the old code doesn't have a perfectly uniform distribution because, for any given list, the size of the set of permutations from which it chooses is not a multiple of the size of the set of all possible permutations. This is similar to doing "random() % 3" in C and getting 0's more often than 2's.

proc shuffle {data} { set length [llength $data] for {} {$length > 1} {incr length -1} { set idx_1 [expr {$length - 1}] set idx_2 [expr {int($length * rand())}] set temp [lindex $data $idx_1] lset data $idx_1 [lindex $data $idx_2] lset data $idx_2 $temp } return $data }

That ought to do it! However, it's (theoretically) a little bit slower due to modifying more variables in the inner loop. I also made a less-readable version that incr's idx_1 rather than recalculating it with expr, for comparison's sake. Here are the numbers, using the same benchmark.

.................................................. : : 400 MHz : 1500 MHz : :....................:.............:.............: : 4 , more random : 8.428660 s : 2.286190 s : : 4a, less readable : 7.824165 s : 2.163990 s : :....................:.............:.............:

For reasonably-sized lists (under 500,000 elements, I guess), the speed difference between #3, #4, and #4a is negligible. So I choose #4, which has a more uniform distribution and doesn't have grody sources due to silly optimizations.

I wonder why the 400 MHz results for #4 and #4a are slower than for #3 yet the 1500 MHz results are the other way around...? I guess this proc is random in more than one way.

SMP: Here is what 4a would look like and a re-benchmark. I think a 4.1% speedup is worth it. I deal with list sizes in the millions. I also use upvar to prevent passing gigantic strings by value (I don't know if Tcl tries to optimize or not).

proc shuffle {in_list_ out_list_} { upvar 1 $in_list_ in_list upvar 1 $out_list_ out_list set out_list $in_list for {set idx_1 [expr {[llength $out_list] - 1}]} {$idx_1 > 0} {incr idx_1 -1} { set idx_2 [expr {int(($idx_1 + 1) * rand())}] set temp [lindex $out_list $idx_1] lset out_list $idx_1 [lindex $out_list $idx_2] lset out_list $idx_2 $temp } }

Tested using the benchmark method above.

........................................................... : 4 : 365282 microseconds per iteration : : 4a : 350104 microseconds per iteration : :....................:....................................:

Here's another algorithm. Basically you randomly select an element from the input list, remove it from the input list, and place it at the end of the output list. The reason I thought of it is, for unsort it's not necessary to maintain an output list; simply puts the elements as they come.

But this algorithm involves a lot of copying--- lset is nice for in-place modifies, but there's no in-place element removal. So it's liable to be slower than #4.