Random Permutation in Ruby
This post on Algo Blog about random permutation shows a cool a little algorithm for randomizing an array which apparently impresses interviewers. I thought it might be fun to write it in Ruby:
def permute_array(a) 1.upto(a.length - 1) do |i| j = rand(i + 1) a[i], a[j] = a[j], a[i] end a end # alternate version def permute_array2(a) 0.upto(a.length - 2) do |i| j = rand(a.length - i) a[i], a[j] = a[j], a[i] end a end
This is actually a pretty fun little function to use. For example – to find all the unique possible combinations of letters in my name: (Secret Scrabble weapon)
(1..5000).map{ permute_array("scott".split("")).join }.uniq.sort => ["costt", "cotst", "cotts", "csott", "cstot", "cstto", "ctost", "ctots", "ctsot", "ctsto", "cttos", "cttso", "ocstt", "octst", "octts", "osctt", "ostct", "osttc", "otcst", "otcts", "otsct", "otstc", "ottcs", "ottsc", "scott", "sctot", "sctto", "soctt", "sotct", "sottc", "stcot", "stcto", "stoct", "stotc", "sttco", "sttoc", "tcost", "tcots", "tcsot", "tcsto", "tctos", "tctso", "tocst", "tocts", "tosct", "tostc", "totcs", "totsc", "tscot", "tscto", "tsoct", "tsotc", "tstco", "tstoc", "ttcos", "ttcso", "ttocs", "ttosc", "ttsco", "ttsoc"]