2のべき乗個の組合せのスケジュールは簡単なアルゴリズムで得られるらしいことがわかったが、このスケジュールをPythonで求めるとかなり遅い。しかし、よく見るとこのスケジュールには規則性がある。例えば、n=16のときのスケジュールは次のようになる。
[0, 1][2, 3][4, 5][6, 7][8, 9][10, 11][12, 13][14, 15]
[0, 2][1, 3][4, 6][5, 7][8, 10][9, 11][12, 14][13, 15]
[0, 3][1, 2][4, 7][5, 6][8, 11][9, 10][12, 15][13, 14]
[0, 4][1, 5][2, 6][3, 7][8, 12][9, 13][10, 14][11, 15]
[0, 5][1, 4][2, 7][3, 6][8, 13][9, 12][10, 15][11, 14]
[0, 6][1, 7][2, 4][3, 5][8, 14][9, 15][10, 12][11, 13]
[0, 7][1, 6][2, 5][3, 4][8, 15][9, 14][10, 13][11, 12]
[0, 8][1, 9][2, 10][3, 11][4, 12][5, 13][6, 14][7, 15]
[0, 9][1, 8][2, 11][3, 10][4, 13][5, 12][6, 15][7, 14]
[0, 10][1, 11][2, 8][3, 9][4, 14][5, 15][6, 12][7, 13]
[0, 11][1, 10][2, 9][3, 8][4, 15][5, 14][6, 13][7, 12]
[0, 12][1, 13][2, 14][3, 15][4, 8][5, 9][6, 10][7, 11]
[0, 13][1, 12][2, 15][3, 14][4, 9][5, 8][6, 11][7, 10]
[0, 14][1, 15][2, 12][3, 13][4, 10][5, 11][6, 8][7, 9]
[0, 15][1, 14][2, 13][3, 12][4, 11][5, 10][6, 9][7, 8]
ペアのうち、右はわかりにくいが、左は規則性がわかりやすい。まず、上から1行、2行、4行、8行で同じ数字になっている。どの組合せも、右に行くにしたがって数字が大きくなっていくが、それにパターンがある。一番下は、1ずつ大きくなる。その上は、やはり1ずつ大きくなるが、5番目で跳躍する。その上は、3番目と5番目と7番目で跳躍する。この規則にしたがってペアの左側の並びを出すプログラムを簡単に作ることができる。
def get_bit(n):
bit = 0
while n != 0:
n >>= 1
bit += 1
return bitn = 16
for i in range(n - 1):
bit = get_bit(i + 1)
timing = 1 << (bit - 1)
jump = timing
a = [ 0 ]
b = 0
for j in range(1, n / 2):
b += 1
if j % timing == 0:
b += jump
a.append(b)
print a
しかし、右はそんなに簡単には見えない。ここで、ペアの和を計算してみる。こちらのほうが規則性がありそうである。
[ 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]
