Hilbert曲線のインデックスと配置座標

こんにちは。
二次元Hilbert曲線のインデックスと配置座標との関係を求めました。

$ ./hilbert.py 1
 0 1
 3 2
$ ./hilbert.py 2
  0  3  4  5
  1  2  7  6
 14 13  8  9
 15 12 11 10
$ ./hilbert.py 3
  0  1 14 15 16 19 20 21
  3  2 13 12 17 18 23 22
  4  7  8 11 30 29 24 25
  5  6  9 10 31 28 27 26
 58 57 54 53 32 35 36 37
 59 56 55 52 33 34 39 38
 60 61 50 51 46 45 40 41
 63 62 49 48 47 44 43 42

Source code

hilbert.py

#!/usr/bin/env python3

def hilbert(n):
    result = []
    range_j = [2**i for i in reversed(range(n))]
    for i in range(4**n):
        U = [[0, 0], [0, 1], [1, 1], [1, 0]]
        x, y = 0, 0
        for j in range_j:
            k = i // (j*j) % 4
            if k == 0:
                U[1], U[3] = U[3], U[1]
            elif k == 3:
                U[0], U[2] = U[2], U[0]
            x += U[k][0] * j
            y += U[k][1] * j
        result.append((x, y))
    return result

def hilbert_lookup(n):
    dict_ = dict(zip(hilbert(n),range(4**n)))
    return [[dict_[(i, j)] for j in range(2**n)] for i in range(2**n)]

import sys, math
n = 2 if len(sys.argv) == 1 else int(sys.argv[1])

n_digit = math.floor(math.log(4**n-1, 10)) + 1
for w in hilbert_lookup(n):
    for i in w:
        print(str(i).rjust(n_digit + 1, ' '), end="")
    print()