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が選ばれてしまうな…。
-
-
-
-
- -
-
-
-
そんなことしている場合じゃなかったかも。
-
-
-
-
- -
-
-
-
よく見たら最初のもちゃんと復元されてないし。
疲れているのか?