# Pseudo random number generator
# From: http://gnuvince.wordpress.com/2005/11/24/pseudo-random-number-generator
# Author: Vincent Foley-Bourgon

def random_number
  t = Time.now.to_f / (Time.now.to_f % Time.now.to_i)
  random_seed = t * 1103515245 + 12345;
  (random_seed / 65536) % 32768;
end

10.times { puts random_number }

cnt = Array.new(10,0)
20000.times { cnt[(random_number % 10).to_i] += 1 }
p cnt
puts


# Ruby Gaussian Random Number Generator
# Author: Glenn
# http://webhost101.net/rails/typo/articles/2007/07/31/ruby-gaussian-random-number-generator

def gaussian_rand 
   u1 = u2 = w = g1 = g2 = 0  # declare
   begin
     u1 = 2 * rand - 1
     u2 = 2 * rand - 1
     w = u1 * u1 + u2 * u2
   end while w >= 1
   
   w = Math::sqrt( ( -2 * Math::log(w)) / w )
   g2 = u1 * w;
   g1 = u2 * w;
   # g1 is returned  
end

sum = 0
sumsq = 0
n = 1000
0.upto(n) do 
  #r = gaussian_rand
  r = gaussian_rand * 100 + 50   # new_random_number = gaussian_rand * standard_deviation + average
  #puts r
  sum += r
  sumsq += (r*r)
end

ave = sum/n
stddev = Math::sqrt(sumsq/n - ave * ave)
puts "Average = #{ave}"
puts "StdDev = #{stddev}"
puts


# Random Number Generator
# http://scutigena.sourceforge.net/test-random.html
# http://scutigena.sourceforge.net/sources/ruby-1.7.2/random.html
# $Id: random.ruby,v 1.2 2003/12/30 01:25:05 davidw Exp $

IM = 139968
IA = 3877
IC = 29573

$last = 42.0
def gen_random (max) (max * ($last = ($last * IA + IC) % IM)) / IM end

10.times do
    puts gen_random(100000.0)
end

printf "%.5f\n", gen_random(100.0)
puts


# From: http://matt.blogs.it/entries/00002641.html
# Author: Matt Mower
# cf. http://www.taygeta.com/random/gaussian.html
# cf. http://www.bearcave.com/misl/misl_tech/wavelets/hurst/random.html

def box_mueller( mean = 0.0, stddev = 1.0 )
  x1 = 0.0, x2 = 0.0, w = 0.0

  until w > 0.0 && w < 1.0
    x1 = 2.0 * rand - 1.0
    x2 = 2.0 * rand - 1.0
    w = ( x1 * x2 ) + ( x2 * x2 )
  end

  w = Math.sqrt( -2.0 * Math.log( w ) / w )
  r = x1 * w

  mean + r * stddev
end

10.times { puts box_mueller(5.0, 1.0) }
puts


# Generating random numbers with a specified distribution
# From: http://www.cs.nyu.edu/~michaels/blog/?p=24
# Author: Michael Schidlowsky

def gen
  (x=rand)>0.5 ? x : (x < rand/2.0) ? 1.0 - x : x
end

def gen2
   (x = rand) && rand ? 1.0 - x : x
end

def compute_distribution(numSamples, &block)
   samples = []
   values = 10
   numSamples.times{samples << yield}
   dist = Array.new(values, 0)
   samples.each{ |s| dist[(s*values).floor] += 1 }
   dist
end

p compute_distribution(1000){rand}
p compute_distribution(1000){gen}
p compute_distribution(1000) { gen2 }
puts


# Random number generation for a triangular distribution
# From: http://www.brighton-webs.co.uk/distributions/triangular.asp
# cf. http://en.wikipedia.org/wiki/Triangular_distribution

def rng(m, low, high)

   # cf. the parameter info at http://www.brighton-webs.co.uk/distributions/triangular.asp
   return nil unless high > low && m > low && m < high    

   u = rand

   if u <= (m-low)/(high-low)
      r = low+ Math.sqrt(u*(high-low)*(m-low))
   else
      r = high - Math.sqrt((1.0-u)*(high-low)*(high-m))
   end

end

10.times do
  #puts rng(0.0, -25.0, 25.0)
  puts rng(50.0, 25.0, 75.0)
end
puts


# From: http://www.ruby-forum.com/topic/95931
# Author: Christoffer Lernö

class Range
  def rand
    return first if exclude_end? && last == first
    Kernel::rand(last - first + (exclude_end? ? 0 : 1)) + first
  end
end

r1 = -9..9
r2 = -90...100
p r1.rand, r2.rand

r3 = 0..9

num = []
10.times do
   num << r3.rand
   if num.first.zero? then num.shift; redo end
end

p num
puts num.to_s.to_i
puts


# See:
# http://redcorundum.blogspot.com/2008/01/randomizing-array-revisited.html
# http://redcorundum.blogspot.com/2006/12/randomizing-array-and-other-faqs.html
# http://szeryf.wordpress.com/2007/06/19/a-simple-shuffle-that-proved-not-so-simple-after-all/

class Array
  def shuffle
    array = dup
    size.downto 2 do |j|
      r = rand j
      array[j-1], array[r] = array[r], array[j-1]
    end
    array
  end
end

array = (1..50).to_a

10.times { p array.shuffle.first(10) }


#-------------------


class RNG

   def num(min=8,max=min+5,iter=1)

      return nil unless min.is_a?(Integer) && max.is_a?(Integer) && max > min && iter.is_a?(Integer)

      ret = []
      stats = Hash.new(0)     # optional; cf. stats[random_num] += 1
      digits = Array(0..9).sort_by {rand}
      #digits = (Array(0..9) * (rand(4)+1)).sort_by {rand}
      digits_size = digits.size

      iter.times do
         count = 0
         len = min + rand(max-min+1)
         ar = []
         while count < len
            i = rand(digits_size)    # get a random array index
            random_num = digits.at(i)
            stats[random_num] += 1
            ar << random_num
            digits = digits.sort_by {rand}
            count += 1
            if count == 1 && ar.first.zero? then ar.shift; stats[0] -= 1; count = 0 end
         end
         ret << ar.to_s.to_i
      end  # iter
      #ret
      ret << stats   # optional
   end

end

puts

min = 8
max = 13
iter = 10000
result =  RNG.new.num(min, max, iter)
stats = result.pop

t = 0
stats.each_value { |v| t += v }  # get the overall frequency

n = 0
t = t * 1.0
m = t / 10.0 

stats.sort.each do |k,v| 
   i = (v / t) * 100.0
   x = v > m ? v - m : m - v
   y = (x / m) * 100.0
   n += i
   puts "#{k}  ::  #{"%.2f" % m}  ::  #{v}  ::  #{"%.2f" % i} %  ::  #{ "%.2f" % ((m-v) * -1) }  ::  #{"%.2f" % y} %"
end

puts n, m, t

puts
puts RNG.new.num(20, 25, 10)[0..-2]

puts
rn = RNG.new.num(80, 100)
puts rn[0..-2]
p rn.last

require 'benchmark' 

module Enumerable
   def map_with_index
      index = -1
      (block_given? && self.class == Range || self.class == Array)  ?  map { |x| index += 1; yield(x, index) }  :  self
   end
end


class Array

   def find_dups
      inject(Hash.new(0)) { |h,e| h[e] += 1; h }.select { |k,v| v > 1 }.collect { |x| x.first }
   end


   # Based on hungryblank's version in the comments
   # see http://www.ruby-forum.com/topic/122008

   def find_dups2
      uniq.select{ |e| (self-[e]).size < self.size - 1 }
   end

   def find_ndups     # also returns the number of items
      uniq.map { |v| diff = (self.size - (self-[v]).size); (diff > 1) ? [v, diff] : nil}.compact
   end


   # cf. http://www.ruby-forum.com/topic/122008
   def dups_indices   
      (0...self.size).to_a - self.uniq.map{ |x| index(x) }
   end

   def dup_indices(obj)
      i = -1
      ret = map { |x| i += 1; x == obj ? i : nil }.compact
      #ret = map_with_index { |x,i| x == obj ? i : nil }.compact
      ret.shift
      ret
   end

   def delete_dups(obj)
      indices = dup_indices(obj)
      return self if indices.empty?
      indices.reverse.each { |i| self.delete_at(i) }
      self
   end

end  


array = [1,3,5,5,6,7,9,10,14,18,22,22,4,4,4,3,6]

dups = nil


Benchmark.bm(14) do |t| 

 t.report('find_dups:') do
    dups = array.find_dups
 end 

end 

p dups   #=> [5, 22, 6, 3, 4]


p %w(a b a c c d).dups_indices
p %w(a b a c c d).dup_indices('c')
p %w(a b a c c d).delete_dups('a')

# From: http://www.rubyonrailsblog.com/articles/2006/08/31/permutations-in-ruby-can-be-fun (in the comments)
# Author: Brian Mitchell

class Array
  # The accumulation is a bit messy but it works ;-)
  def sequence(i = 0, *a)
    return [a] if i == size
    self[i].map {|x|
      sequence(i+1, *(a + [x]))
    }.inject([]) {|m, x| m + x}     # this has to be used instead of flatten so I can sequence something
                                    # like [[[4]]] -> [[[4]]] rather than -> [[4]]; ruby 1.9 has an option for flatten
  end
end


p [(0..3), [4,6]].sequence             #=> [[0, 4], [0, 6], [1, 4], [1, 6], [2, 4], [2, 6], [3, 4], [3, 6]]      
p [(0..3).collect, [4, 6]].sequence



# http://wiki.rubygarden.org/Ruby/page/show/ArrayPermute
# Permute an array, and call a block for each permutation
# Author: Paul Battley

    class Array
        def permute(prefixed=[])
            if (length < 2)
                # there are no elements left to permute
                yield(prefixed + self)
            else
                # recursively permute the remaining elements
                each_with_index do |e, i|
                    (self[0,i]+self[(i+1)..-1]).permute(prefixed+[e]) { |a| yield a }
                end
            end
        end
    end


%w[a b c].permute { |x| puts(x.join('')) } 

[0, 1, 2, 3 ].permute { |x| puts(x.join('-')) } 



# http://blade.nagaokaut.ac.jp/cgi-bin/scat.rb/ruby/ruby-talk/32844
# Author: Steven Grady

class Array
  def permutations
    return [self] if size < 2
    perm = []
    each { |e| (self - [e]).permutations.each { |p| perm << ([e] + p) } }
    perm
  end
end

p (1..4).to_a.permutations



# http://blade.nagaokaut.ac.jp/~sinara/ruby/math/combinatorics/array-perm.rb
# Author: Shin-ichiro Hara
# For many more permutation snippets see: 
# http://blade.nagaokaut.ac.jp/~sinara/ruby/math/combinatorics/

class Array
  def perm(n = size)
    if size < n or n < 0
    elsif n == 0
      yield([])
    else
      self[1..-1].perm(n - 1) do |x|
	(0...n).each do |i|
	  yield(x[0...i] + [first] + x[i..-1])
	end
      end
      self[1..-1].perm(n) do |x|
	yield(x)
      end
    end
  end
end

if $0 == __FILE__
  ["a", "b", "c", "d"].perm(3) do |x|  
    p x
  end
end



# Based on:
# http://blade.nagaokaut.ac.jp/cgi-bin/scat.rb/ruby/ruby-talk/139290
# Author: Endy Tjahjono

class String
   def perm
       return [self] if self.length < 2
       ret = []
    
       0.upto(self.length - 1) do |n|
          #rest = self.split('')                
          rest = self.split(//u)            # for UTF-8 encoded strings
          picked = rest.delete_at(n)
          rest.join.perm.each { |x| ret << picked + x }
       end

       ret
   end
end

p "abc".perm      #=>  ["abc", "acb", "bac", "bca", "cab", "cba"]



require 'permutation'

# http://permutation.rubyforge.org 
# http://permutation.rubyforge.org/doc/classes/Permutation.html
# sudo gem install permutation --remote
# For more examples see permutation-0.1.4/examples/tsp.rb and permutation_0.1.4/lib/permutation.rb:
# curl http://files.rubyforge.vm.bytemark.co.uk/permutation/permutation-0.1.4.tgz | tar xfz -

perm = Permutation.new(3)   
p perm.map { |p| p.value }        #=>  [[0, 1, 2], [0, 2, 1], [1, 0, 2], [1, 2, 0], [2, 0, 1], [2, 1, 0]]

#class Array 
module Enumerable
  def comprehend(&block) 
    block ? map(&block).compact : self 
  end 
end 


old_data = *(1..5)          # alternatives to the splat operator: (1..5).to_a or (1..5).collect
new_data = *(3..9)


# some reinventing going on here ...
added = new_data.comprehend { |x| x if not old_data.include?(x) } 
removed = old_data.comprehend { |x| x if not new_data.include?(x) } 
same = new_data.comprehend { |x| x if old_data.include?(x) } 
modified = new_data.comprehend { |x| x**2 if not x % 2 == 0 }

p added                                            #=> [6, 7, 8, 9]
p added = new_data - old_data                      #=> [6, 7, 8, 9]

p removed                                         #=> [1, 2]
p removed = old_data - new_data                   #=> [1, 2]

p same                                              #=> [3, 4, 5]
p same = old_data & new_data                        #=> [3, 4, 5]
 
p modified                                        #=> [9, 25, 49, 81]


new_data = [[5, 9], [22, 3], [99, 564]]
bool_vals = new_data.comprehend { |x, y| x <= y }
p bool_vals                                      #=> [true, false, true]

# ---------------------------------------------------------------------------
# collect_every(n [,fill=false[,offset=0]])                  => an array
# collect_every(n [,fill=false[,offset=0]]) {|item| block}   => an_array
# ---------------------------------------------------------------------------
# If a block is given, it invokes the block passing in an array of n elements.
# The last array passed may not contain n elements if size % 2 does not equal
# zero. If no block is given, it returns an array containing the collections.
#
# If the optional argument fill is set to true, the empty spaces will be
# filled with nils. The optional argument offset allows the collection to 
# start at that index in the array.
#
# a = (1..10).to_a
# a.collect_every(5)               #=> [[1, 2, 3, 4, 5], [6, 7, 8, 9, 10]]
# a.collect_every(5) {|x| p x}     #=> [1, 2, 3, 4, 5]
#                                      [6, 7, 8, 9, 10]
# b = (1..7).to_a
# b.collect_every(3)               #=> [[1, 2, 3], [4, 5, 6], [7]]
# b.collect_every(3,true)          #=> [[1, 2, 3], [4, 5, 6], [7,nil,nil]]
# b.collect_every(3,true,1)        #=> [[2, 3, 4], [5, 6, 7]]


class Array

 def collect_every(n, fill=false, offset = 0)

  if block_given?
     while  offset < size
          ret = []

          if fill
             n.times do |x| 
                  if offset + x > size - 1 then ret << nil 
                  else  ret << self[offset + x] end
             end
          else
             n.times { |x| ret << self[offset + x] unless offset + x > size - 1}
          end 

          offset += n
          yield ret
          ret = nil
     end   

  else

   ret = []
   while  offset < size
     ret << []
     if fill
         n.times do |x|  
            if offset + x > size - 1 then ret.last << nil
            else ret.last << self[offset + x]; end
         end
     else
         n.times { |x| ret.last << self[offset + x] unless offset + x > size - 1 }
     end

     offset += n
   end
   return ret

  end 

 end
end


a = (1..10).to_a
puts a.collect_every(5).inspect                     #->  [[1, 2, 3, 4, 5], [6, 7, 8, 9, 10]]
a.collect_every(5) { |x| puts x.inspect }         #->  [1, 2, 3, 4, 5] and [6, 7, 8, 9, 10]
puts a.collect_every(3, true).inspect             #->  [[1, 2, 3], [4, 5, 6], [7, 8, 9], [10, nil, nil]]
puts a.collect_every(3, true,1).inspect          #->  [[2, 3, 4], [5, 6, 7], [8, 9, 10]]
puts a.collect_every(3, true,4).inspect          #->  [[5, 6, 7], [8, 9, 10]]

puts a.inspect                                              #->  [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]



# ------------------------------------------------------------------------



class Array

 def subdivide(n)
   return self if n <= 0 || n >= self.size
   result = []
   max_subarray_size = n - 1

     while self.size > 0
       result << self.slice!(0..max_subarray_size)
     end

   result
 end

end

a = ('a'..'g').to_a
b = a.subdivide(3)

puts b.inspect       #->  [["a", "b", "c"], ["d", "e", "f"], ["g"]]
puts a.inspect       #->  [] 

class Class
  def extract(included, inherit_from = [ Object ])
    included = included.map { |m| m.to_s }
    inherited = inherit_from.inject([]) do |i, modul|
      i.concat modul.instance_methods
    end
    klass = dup
    klass.instance_eval do
      instance_methods.each do |m|
        unless included.member? m or inherited.member? m
          undef_method m
        end
      end
    end
    klass
  end

  def rename(names = {})
    names.each do |old_name, new_name|
      instance_eval do
        alias_method new_name, old_name
        undef_method old_name
      end
    end
    self
  end

  def alias(names = {})
    names.each do |old_name, new_name|
      instance_eval do
        alias_method new_name, old_name
      end
    end
    self
  end

  def define(*args, &block)
    define_method(*args, &block)
    self
  end
end




Stack = Array.extract([
  :last,
  :push,
  :pop,
  :size,
  :clear,
  :inspect,
  :to_s
])

if $0 == __FILE__
  s = Stack.new
  s.push 1
  s.push 2
  s.push 3
  puts s.inspect       # => [1, 2, 3]
  s.last  # => 3
  s.pop   # => 3
  puts s.inspect       # => [1, 2]
end

Queue = Array.extract([
  :first,
  :push,
  :shift,
  :clear,
  :size,
  :inspect,
  :to_s
]).rename(
  :push   =>  :enqueue,
  :shift  =>  :dequeue
)

if $0 == __FILE__
  q = Queue.new
  q.enqueue 1
  q.enqueue 2
  q.enqueue 3
  puts q.inspect         # => [1, 2, 3]
  q.first   # => 1
  q.dequeue # => 1
  puts q.inspect         # => [2, 3]
end

List = Array.extract([
  :first,
  :last,
  :push,
  :insert,
  :delete,
  :delete_at,
  :[],
  :[]=,
  :size,
  :each,
  :length,
  :inspect,
  :to_s
], [ Object, Enumerable ]).rename(
  :push   =>  :add
).alias(
  :[]     =>  :get,
  :[]=    =>  :put
).define(:sum) { |*start|
  inject(start[0] || 0) { |s,x| s + x }
}

if $0 == __FILE__
  l = List.new
  l.add 1
  l.add 2
  l.add 3
  puts l.inspect             # => [1, 2, 3]
  l.delete 2    # => 2
  puts l.inspect            # => [1, 3]
  l.add 2
  puts l.inspect             # => [1, 3, 2]
  l.delete_at 1 # => 3
  puts l.inspect             # => [1, 2]
  l.get 0       # => 1
  l.put 0, 23   # => 23
  puts l.inspect             # => [23, 2]
  l.sum         # => 25
  m = List.new
  m.add "foo"
  m.add "bar"
  m.sum ""      # => "foobar"
end

class Array

   def subar_indices(ar=[], temp=[])
      temp = temp.dup
      self.each_with_index { |item, index| 
         if item.class == Array
            temp << index
            ar << temp
            ar = item.subar_indices(ar, temp)
         end
      }
      ar.uniq
   end


   def extract_subar_indices
      subarray_indices = self.subar_indices  # subarray_indices is a two-dimensional array
      # puts subarray_indices.inspect
      
      return subarray_indices if subarray_indices.empty?

      first_subar = subarray_indices.shift   # the first subarray contains all two-dimensional subarray indices                

      subarray_indices.each do |subar|
         subar_size = subar.size
         str = ""
         count = -1
         (subar_size - 1).times { count += 1; str << ".fetch(subar[#{count}], [])" }
         str << ".fetch(subar[#{count + 1}], {}"
         str = "self" << str
         if eval(str).class == Hash then subar.shift; redo end
      end

      first_subar.reverse.each do |item| subarray_indices.unshift([item]) end
      subarray_indices
   end

end


array = [1, 2, [3, 4, [5, 6]], 7, 8, [9]]

indices = array.extract_subar_indices

puts indices.inspect  # [[2], [5], [2, 2]]

class Array

   def mda(*mds)

      count = -1

      mdarray = lambda { |*ds| 
        Array.new( ds.shift || 0 ).collect {
            x = mdarray[*ds] unless ds.empty?
            if x == nil then count += 1; x = self.at(count); end
            x
            }
      }

      mdarray.call(*mds)    

   end

end


ar1 = (1..24).to_a    # input data

ar2 = ar1.