```"Bill Kelly" <billk / cts.com> wrote in
....
>
> class Array   # from http://www.rubygarden.org/ruby?OneLiners
>     def shuffle!
>       each_index {|j| i = rand(size-j); self[j], self[j+i] = self[j+i],
self[j]}
>     end
> end

Note that this one liner does not create an even distribution
of shuffles.
....
>
> . . . Anyway, I'd be interested in anyone's thoughts on what's
> going on here......  (Hope I didn't botch the tests somehow -
> but I don't think so!)

From the output of my little benchmarks script which generates
``one_in_each''  random square (matrix) examples,  I'd say that most
published solutions (including yours) are on the average O(n^3)  (n x n
= size of the matrix) solutions, but one can write solutions which are
on the average O(n^2).

---
# other good values to try are  50, 100, 150, 300
# and 1000? (if you  have the time).

N = 200

def one_in_each(i,r)
...
end

class Array
def shuffle!
s = size
0.upto(size-1) do |i|
j = i + rand(size-i)
tmp = self[i]
self[i] = self[j]
self[j] = tmp
end
self
end
end

Const = 2<<29
def create_problem(m)
items = Array.new(m)
rows = (0...m).collect do |i|
tmp = Array.new(m) do rand(Const) end
items[i] = tmp[rand(m)] = -rand(Const) - 1
tmp
end
return items.shuffle!, rows
end

require 'benchmark'
include Benchmark

bmbm { |x|
i,r = nil, nil
x.report("create"){ i,r = create_problem(N) }
GC.start
x.report("one_in_each") { one_in_each(i,r) }
}
---

/Christoph

```