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"]

Comments are closed.