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