Randomize a List problem

[Albert Chan]

Random shuffling must produce all permutations with equal probabilities.

We pick a random element from the list, and moved out of the way
Do this repeatedly, like this. (we can skip the 1 element list case)

Code:

function shuffle(lst)
    local n = #lst
    for i = n, 2, -1 do
        local j = random(i)
        lst[i], lst[j] = lst[j], lst[i]
    end
end

1st loop, random element is swapped to lst[n], and never touched again.
2nd loop, random element is swapped to lst[n-1] ...

lua> pat = setmetatable({}, {__index = function(a,i) return 0 end})
lua> for i=1,120000 do
:            lst = {'1','2','3'}
:            shuffle(lst)
:            x = table.concat(lst,'')
:            pat[x] = pat[x] + 1
:      end
lua> table.foreach(pat, print)
321       20104
312       19844
132       20026
123       20096
231       19890
213       20040