allpairs.rb   [plain text]

module AllPairs
  module_function

  def make_prime(v)
    return 2 if v < 2
    ary = [true] * (v*2)
    2.upto(Math.sqrt(ary.length).ceil) {|i|
      return i if ary[i] && v <= i
      (i*2).step(ary.length, i) {|j|
        ary[j] = false
      }
    }
    v.upto(ary.length-1) {|i|
      return i if ary[i]
    }
    raise "[bug] prime not found greater than #{v}"
  end

  def make_basic_block(prime)
    prime.times {|i|
      prime.times {|j|
        row = [i]
        0.upto(prime-1) {|m|
          row << (i*m + j) % prime
        }
        yield row
      }
    }
  end

  def combine_block(tbl1, tbl2)
    result = []
    tbl2.each {|row|
      result << row * tbl1.first.length
    }
    tbl1.each_with_index {|row, k|
      next if k == 0
      result << row.map {|i| [i] * tbl2.first.length }.flatten
    }
    result
  end

  def make_large_block(v, prime)
    if prime <= v+1
      make_basic_block(v) {|row|
        yield row
      }
    else
      tbl = []
      make_basic_block(v) {|row|
        tbl << row
      }
      tbls = [tbl]
      while tbl.first.length ** 2 < prime
        tbl = combine_block(tbl, tbl)
        tbls << tbl
      end
      tbl1 = tbls.find {|t| prime <= t.first.length * tbl.first.length }
      tbl = combine_block(tbl, tbl1)
      tbl.each {|row|
        yield row
      }
    end
  end

  def each_index(*vs)
    n = vs.length
    max_v = vs.max
    prime = make_prime(max_v)
    h = {}
    make_large_block(max_v, n) {|row|
      row = vs.zip(row).map {|v, i| i % v }
      next if h[row]
      h[row] = true
      yield row
    }
  end

  # generate all pairs test.
  def each(*args)
    args.map! {|a| a.to_a }
    each_index(*args.map {|a| a.length}) {|is|
      yield is.zip(args).map {|i, a| a[i] }
    }
  end

  # generate all combination in cartesian product.  (not all-pairs test)
  def exhaustive_each(*args)
    args = args.map {|a| a.to_a }
    i = 0
    while true
      n = i
      as = []
      args.reverse_each {|a|
        n, m = n.divmod(a.length)
        as.unshift a[m]
      }
      break if 0 < n
      yield as
      i += 1
    end
  end
end