1module AllPairs
2  module_function
3
4  def make_prime(v)
5    return 2 if v < 2
6    ary = [true] * (v*2)
7    2.upto(Math.sqrt(ary.length).ceil) {|i|
8      return i if ary[i] && v <= i
9      (i*2).step(ary.length, i) {|j|
10        ary[j] = false
11      }
12    }
13    v.upto(ary.length-1) {|i|
14      return i if ary[i]
15    }
16    raise "[bug] prime not found greater than #{v}"
17  end
18
19  def make_basic_block(prime)
20    prime.times {|i|
21      prime.times {|j|
22        row = [i]
23        0.upto(prime-1) {|m|
24          row << (i*m + j) % prime
25        }
26        yield row
27      }
28    }
29  end
30
31  def combine_block(tbl1, tbl2)
32    result = []
33    tbl2.each {|row|
34      result << row * tbl1.first.length
35    }
36    tbl1.each_with_index {|row, k|
37      next if k == 0
38      result << row.map {|i| [i] * tbl2.first.length }.flatten
39    }
40    result
41  end
42
43  def make_large_block(v, prime)
44    if prime <= v+1
45      make_basic_block(v) {|row|
46        yield row
47      }
48    else
49      tbl = []
50      make_basic_block(v) {|row|
51        tbl << row
52      }
53      tbls = [tbl]
54      while tbl.first.length ** 2 < prime
55        tbl = combine_block(tbl, tbl)
56        tbls << tbl
57      end
58      tbl1 = tbls.find {|t| prime <= t.first.length * tbl.first.length }
59      tbl = combine_block(tbl, tbl1)
60      tbl.each {|row|
61        yield row
62      }
63    end
64  end
65
66  def each_index(*vs)
67    n = vs.length
68    max_v = vs.max
69    prime = make_prime(max_v)
70    h = {}
71    make_large_block(max_v, n) {|row|
72      row = vs.zip(row).map {|v, i| i % v }
73      next if h[row]
74      h[row] = true
75      yield row
76    }
77  end
78
79  # generate all pairs test.
80  def each(*args)
81    args.map! {|a| a.to_a }
82    each_index(*args.map {|a| a.length}) {|is|
83      yield is.zip(args).map {|i, a| a[i] }
84    }
85  end
86
87  # generate all combination in cartesian product.  (not all-pairs test)
88  def exhaustive_each(*args)
89    args = args.map {|a| a.to_a }
90    i = 0
91    while true
92      n = i
93      as = []
94      args.reverse_each {|a|
95        n, m = n.divmod(a.length)
96        as.unshift a[m]
97      }
98      break if 0 < n
99      yield as
100      i += 1
101    end
102  end
103end
104