スケジューリングしたペアの左側がわかったので、ペアの和もわかればよい。その和を再掲すると、
[ 1, 5, 9, 13, 17, 21, 25, 29]
[ 2, 4, 10, 12, 18, 20, 26, 28]
[ 3, 3, 11, 11, 19, 19, 27, 27]
[ 4, 6, 8, 10, 20, 22, 24, 26]
[ 5, 5, 9, 9, 21, 21, 25, 25]
[ 6, 8, 6, 8, 22, 24, 22, 24]
[ 7, 7, 7, 7, 23, 23, 23, 23]
[ 8, 10, 12, 14, 16, 18, 20, 22]
[ 9, 9, 13, 13, 17, 17, 21, 21]
[10, 12, 10, 12, 18, 20, 18, 20]
[11, 11, 11, 11, 19, 19, 19, 19]
[12, 14, 16, 18, 12, 14, 16, 18]
[13, 13, 17, 17, 13, 13, 17, 17]
[14, 16, 14, 16, 14, 16, 14, 16]
[15, 15, 15, 15, 15, 15, 15, 15]
それぞれの配列が規則性を持っているように思える。
そこで、次の配列に分解してみる。
f0 = [ 1, 1, 1, 1, 1, 1, 1, 1]
f1 = [-1, -1, -1, -1, 1, 1, 1, 1]
f2 = [-1, -1, 1, 1, -1, -1, 1, 1]
f3 = [-1, 1, -1, 1, -1, 1, -1, 1]
内積を<,>で表すと、直行性が現れる。
<fi,fj> = 8δij
だから、最初の15個の配列をaiとして、
ai = bijfj
とすると（Einsteinの略記法を用いている）、
aifk = bijfjfk = 8bik
となる。このbを計算すると、
[15, 8, 4, 2]
[15, 8, 4, 1]
[15, 8, 4, 0]
[15, 8, 2, 1]
[15, 8, 2, 0]
[15, 8, 0, 1]
[15, 8, 0, 0]
[15, 4, 2, 1]
[15, 4, 2, 0]
[15, 4, 0, 1]
[15, 4, 0, 0]
[15, 0, 2, 1]
[15, 0, 2, 0]
[15, 0, 0, 1]
[15, 0, 0, 0]
と、かなり規則性がわかりやすい。これを組んでみた（コードは下）。
しかし、よく考えると、もっと簡単なスケジューリングがある。
class pair_set:
def __init__(self, n):
self.n = n
self.pair_table = [ ]
self.check_table = [ ]
def calc(self):
for p in self.pair_generator():
self.put_pair(p)
def put_pair(self, p):
for i in range(len(self.check_table)):
if self.is_empty(i, p):
self.set_pair(i, p)
return
self.append()
self.set_pair(len(self.pair_table) - 1, p)
def pair_generator(self):
for i in range(self.n - 1):
for j in range(i + 1, self.n):
yield [ i, j ]
def is_empty(self, i, p):
turn = self.check_table[i]
return not turn[p[0]] and not turn[p[1]]
def set_pair(self, i, p):
self.pair_table[i].append(p)
self.check_table[i][p[0]] = True
self.check_table[i][p[1]] = True
def append(self):
self.pair_table.append([])
self.check_table.append([ False for i in range(self.n)])
def __str__(self):
buff = ""
for pairs in self.pair_table:
for pair in pairs:
buff += pair.__str__()
buff += "\n"
return buff
def sum(self, i):
return [ a[0] + a[1] for a in self.pair_table[i] ]def get_bit(n):
bit = 0
while n > 1:
bit += 1
n >>= 1
return bitdef inner_product(a, b):
sum = 0
for i in range(len(a)):
sum += a[i] * b[i]
return sum
n = 16
nbit = get_bit(n)
ps = pair_set(n)
ps.calc()
print psperiod_function = [ [ 1 for i in range(n / 2) ] ]
period = n / 2
while period > 1:
b = [ ]
for i in range(0, n / 2 / period):
for j in range(0, period / 2):
b.append(-1)
for j in range(0, period / 2):
b.append(1)
period_function.append(b)
period /= 2for i in range(n - 1):
a = ps.sum(i)
b = [ inner_product(f, a) / (n / 2) for f in period_function ]
c = [ inner_product(b, [ f[k] for f in period_function ]) for k in range(n/2) ]
d = [ n - 1 ]
for k in range(1, nbit):
l = nbit - k
if i < (1 << l) - 1:
d.append(1 << l)
else:
d.append( (~(i + 1)) & (1 << (l - 1)))
e = [ inner_product(d, [ f[k] for f in period_function ]) for k in range(n/2) ]
print e
