BlockSorting

BlockSortingを参考に試しの実装をしてみた。

# -*- coding: cp932 -*-
# Blocksorting

# 変換
data = "abracadabra"

mat = [
    data[i:] + data[:i]
    for i in range(len(data))]

for line in mat:
    print line
print

mat.sort()

for line in mat:
    print line
print

print "result:"

start = mat.index(data)
print start

tails = [line[-1] for line in mat]
print tails

# 復元
print "restore:"

heads = list(sorted(tails))
print heads

cur = start
i = 0
while True:
    tails[cur] = None
    c = heads[cur]
    print c,
    i += 1
    if i == len(tails): break
    cur = tails.index(c)

もちろんこの素朴な実装にでかいデータを食わせてはいけない。

で、実行結果。#以降はコメント

abracadabra # これが元データ
bracadabraa # 1個ずつずらしていく
racadabraab
acadabraabr
cadabraabra
adabraabrac
dabraabraca
abraabracad
braabracada
raabracadab
aabracadabr

aabracadabr # 上の表をソートする
abraabracad
abracadabra
acadabraabr
adabraabrac
braabracada
bracadabraa
cadabraabra
dabraabraca
raabracadab
racadabraab

result:
2 # 元データのあった位置
['r', 'd', 'a', 'r', 'c', 'a', 'a', 'a', 'a', 'b', 'b'] # 上の表の末尾をとったリストtails
# この二つから復元をする
restore:
['a', 'a', 'a', 'a', 'a', 'b', 'b', 'c', 'd', 'r', 'r'] # tailsをソートしたもの。つまり2番目の表の頭のリスト
a b r a b r a c a d a # 復元された

おおーー、復元された！
1文字ずらしの表を作るところは実際には元の文字列の適当なところを読むだけでいいから楽だけど、文字列の長さ分の要素数のソートがあるのがしんどいなぁ。

• • • • • -

あ、バグがある。

バグを発生させる最小限の入力を作ってみたら"aabbaa"でバグることが判明。

print start
print tails
print heads
while True:
    tails[cur] = None
    c = heads[cur]
    result.append(c)
    i += 1
    if i == len(tails): break
    print c, tails
    cur = tails.index(c)

print start
print tails
print heads
while True:
    tails[cur] = None
    c = heads[cur]
    result.append(c)
    i += 1
    if i == len(tails): break
    print c, tails
    cur = tails.index(c)

ほうほう。頭から探しちゃダメなんだな。

-     cur = tails.index(c)
+    try:
+        cur = tails.index(c, cur)
+    except:
+        cur = tails.index(c)

ありゃ、やっぱりダメだ。

aaaabb
aaabba
aabbaa
abbaaa
baaaab
bbaaaa
2
['b', 'a', 'a', 'a', 'b', 'a']
['a', 'a', 'a', 'a', 'b', 'b']
a ['b', 'a', None, 'a', 'b', 'a']
a ['b', 'a', None, None, 'b', 'a']
b ['b', 'a', None, None, 'b', None]
a [None, 'a', None, None, 'b', None]
a [None, None, None, None, 'b', None]

Traceback (most recent call last):
  File "c:/blocksorting.py", line 39, in <module>
    cur = tails.index(c)
ValueError: list.index(x): x not in list

うーん、aabまで来たときに、先に先頭にあるb→aが選ばれてしまうな…。

• • • • • -

そんなことしている場合じゃなかったかも。

• • • • • -

よく見たら最初のもちゃんと復元されてないし。
疲れているのか？