Python で Kautz 文字列を生成する

Kautz 文字列

Kautz 文字列は，隣り合う文字がすべて異なるような文字列で，Kautz グラフの頂点ラベルに利用される．
より厳密に，基底 $b$，長さ $k$ の Kautz 文字列は，アルファベット $\Sigma = \mathbb{Z}_{b+1}$ 上の文字 $a_1, a_2, \dots a_k \in \Sigma$ が $a_1 \neq a_2, \dots, a_{k-1} \neq a_{k}$ を満たす文字列 $a_1 a_2 \dots a_k$ である．
位取り記数法における基底 (base) と Kautz 文字列における基底は，それぞれ用法が異なるので注意されたい．

ランダムな Kautz 文字列

ランダムな Kautz 文字列を得る実装は以下のとおり．

import random


def random_kautz_string(base):
    last = random.choice(range(base))
    prev = last
    yield last
    while True:
        last = random.choice(range(base + 1))
        if last != prev:
            prev = last
            yield last

ASCII 文字を使って str 型を返すように書くのが自然な実装だが，これだと基底がアルファベットサイズに制限されてしまうため，桁を表す整数のジェネレータとして実装した．

>>> g = random_kautz_string(base=8)
>>> tuple(next(g) for _ in range(128))
(4, 1, 2, 6, 7, 1, 3, 6, 4, 5, 7, 6, 2, 4, 6, 0, 4, 3, 5, 1, 7, 4, 3, 4, 7, 2, 7, 3, 5, 7, 3, 6, 1, 3, 1, 0, 1, 5, 1, 7, 2, 3, 4, 2, 5, 3, 6, 7, 1, 3, 5, 2, 1, 0, 4, 0, 4, 5, 3, 4, 5, 7, 6, 2, 3, 5, 2, 0, 7, 4, 2, 0, 5, 3, 2, 7, 5, 2, 5, 0, 1, 2, 5, 7, 2, 3, 5, 1, 3, 5, 6, 0, 4, 2, 1, 7, 6, 3, 2, 1, 4, 1, 6, 3, 5, 0, 5, 4, 6, 1, 7, 4, 5, 2, 4, 0, 2, 3, 4, 6, 1, 5, 2, 0, 6, 3, 4, 1)
>>> g = random_kautz_string(base=128)
>>> tuple(next(g) for _ in range(128))
(0, 83, 33, 113, 56, 102, 84, 0, 2, 99, 44, 1, 115, 64, 65, 101, 39, 45, 1, 0, 90, 75, 25, 106, 101, 83, 101, 54, 97, 75, 64, 54, 63, 57, 38, 5, 123, 35, 60, 110, 31, 11, 89, 0, 24, 109, 8, 19, 11, 10, 110, 103, 76, 78, 38, 87, 56, 100, 83, 47, 51, 107, 2, 60, 124, 22, 44, 115, 59, 120, 14, 78, 93, 71, 100, 21, 81, 75, 17, 16, 19, 85, 120, 102, 115, 107, 5, 50, 4, 38, 14, 47, 11, 99, 104, 107, 22, 30, 65, 58, 23, 106, 4, 92, 86, 39, 64, 15, 10, 121, 115, 80, 58, 76, 93, 124, 11, 84, 116, 63, 25, 111, 63, 100, 62, 46, 98, 106)

Kautz ハッシュ

出力が Kautz 文字列となるようなハッシュ化手法も提案されている．

import itertools
import hashlib


def kautz_hash(b: bytes, base: int, length: int):
    s = base_hash(b, base)
    while len(s) < length:
        s += base_hash(s, base)
    return tuple(s)[:length]


def base_hash(b: bytes, base: int):
    s = hashlib.sha3_256(b).digest()
    s = bytes_base_convert(s, base + 1)
    s = deduplicate_adjacent(s)
    return s


def bytes_base_convert(b: bytes, base: int):
    return base_convert(b, 256, base)


def deduplicate_adjacent(iterable):
    t = type(iterable)
    return t(k for k, g in itertools.groupby(iterable))


def base_convert(iterable, ibase: int, obase: int):
    t = type(iterable)
    d = list(iterable)
    o = list()
    while any(d):
        c = 0
        for i in range(len(d)):
            c = c * ibase + d[i]
            d[i], c = divmod(c, obase)
        o.append(c)
    return t(reversed(o))

出力は以下のようになる．

>>> kautz_hash(b'Hello, world!', base=10, length=128)
(10, 5, 1, 6, 10, 5, 0, 2, 9, 7, 2, 7, 5, 1, 3, 2, 4, 6, 8, 3, 9, 4, 2, 4, 6, 1, 2, 10, 7, 8, 10, 4, 2, 1, 10, 4, 8, 3, 9, 7, 10, 1, 6, 0, 4, 1, 10, 7, 0, 5, 0, 7, 0, 8, 4, 6, 9, 10, 4, 10, 3, 6, 3, 1, 2, 1, 5, 10, 1, 6, 8, 2, 7, 1, 6, 9, 10, 1, 6, 2, 7, 1, 10, 9, 7, 8, 6, 5, 6, 5, 0, 10, 1, 5, 3, 0, 6, 0, 3, 5, 10, 1, 7, 6, 2, 4, 2, 5, 7, 9, 7, 1, 8, 10, 9, 7, 10, 7, 3, 6, 0, 7, 6, 1, 7, 5, 7, 3)
>>> kautz_hash(b'Hello, world.', base=10, length=128)
(4, 3, 9, 3, 0, 8, 2, 3, 4, 9, 7, 8, 6, 2, 7, 9, 3, 6, 10, 4, 7, 5, 7, 4, 8, 2, 9, 10, 5, 9, 3, 1, 4, 8, 10, 5, 4, 6, 0, 10, 3, 5, 4, 7, 10, 2, 8, 9, 8, 1, 8, 4, 9, 5, 8, 0, 3, 0, 8, 1, 9, 10, 2, 0, 4, 9, 10, 6, 5, 6, 9, 4, 3, 10, 6, 9, 7, 10, 9, 1, 10, 9, 8, 2, 0, 10, 8, 3, 2, 1, 10, 5, 8, 0, 8, 5, 7, 0, 3, 9, 2, 8, 3, 10, 0, 3, 8, 3, 8, 0, 6, 1, 6, 8, 10, 7, 1, 3, 1, 0, 8, 5, 9, 2, 1, 10, 2, 3)

参考

• http://d.hatena.ne.jp/cheeseshop/20081217/1237077843
• https://stackoverflow.com/questions/6647174/enforcing-no-2-same-contiguous-elements-in-random-list-generation
• Y. Zhang, X. Lu, and D. Li, “SKY: efficient peer-to-peer networks based on distributed Kautz graphs,” Sci. China Ser. F Inf. Sci., vol. 52, no. 4, pp. 588–601, Apr. 2009.