blob: 393d0c3288c1c3222374f1068e9a030133ddea3b (
plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
|
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
|
