Help us understand the problem. What is going on with this article?

Python で Kautz 文字列を生成する

More than 1 year has passed since last update.

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)

参考

Why not register and get more from Qiita?
  1. We will deliver articles that match you
    By following users and tags, you can catch up information on technical fields that you are interested in as a whole
  2. you can read useful information later efficiently
    By "stocking" the articles you like, you can search right away
Comments
No comments
Sign up for free and join this conversation.
If you already have a Qiita account
Why do not you register as a user and use Qiita more conveniently?
You need to log in to use this function. Qiita can be used more conveniently after logging in.
You seem to be reading articles frequently this month. Qiita can be used more conveniently after logging in.
  1. We will deliver articles that match you
    By following users and tags, you can catch up information on technical fields that you are interested in as a whole
  2. you can read useful information later efficiently
    By "stocking" the articles you like, you can search right away
ユーザーは見つかりませんでした