bwt.py

SENTINEL = chr(ord('$'))

def rotations(s):
    for i in xrange(len(s)):
        yield '%s%s' % (s[i:], s[:i])

def bwt(s):
    if SENTINEL in s:
        raise ValueError('Input can\'t contain chr(%d)' % ord(SENTINEL))

    return ''.join(row[-1]
                   for row in sorted(rotations('%s%s' % (s, SENTINEL))))

def ibwt(s):
    rows = [''] * len(s)

    for _ in xrange(len(s)):
        for i in xrange(len(s)):
            rows[i] = '%s%s' % (s[i], rows[i])
        rows.sort()

    row = rows[0]
    idx = row.index(SENTINEL)

    return '%s%s' % (row[idx + 1:], row[:idx])


for line in 'BANANA', 'SIX MIXED PIXIES SIFT SIXTY PIXIE DUST BOXES':
    print line
    t = bwt(line)
    print 'BWT:', t
    print 'IBWT:', ibwt(t)