"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