прикреплённый файл:BurrowsWheeler.py к странице LecturesVMSH/2012-04-18

   1 #!/usr/bin/env python
   2 # coding: utf
   3 '''
   4 Постройте все циклические перестановки строки, отсортируйте их и выпишите последний столбец. Вводится строка, состоящая из маленьких латинских букв, ее длина не превосходит 30000 символов
   5 '''
   6 
   7 import sys, os
   8 
   9 def stamp(comment=""):
  10     global T,t
  11     T, t = os.times()[0], os.times()[0]-T
  12     print >> sys.stderr, comment, t
  13 
  14 K=0
  15 if len(sys.argv)<2:
  16     for s in file(sys.argv[0]):
  17         if s.startswith("##"):
  18             K+=1
  19             print K, s[3:-1]
  20     sys.exit(0)
  21 
  22 T=os.times()[0]
  23 S=sys.stdin.read()
  24 stamp("INITIAL")
  25 N=len(S)
  26 
  27 ## Use custom cmp() for sort indexes
  28 K+=1
  29 if str(K) in sys.argv[1]:
  30     C=range(N)
  31     def Scmp(i1,i2): return cmp(S[i1:]+S[:i1],S[i2:]+S[:i2])
  32     print >> sys.stderr, os.times()[0]-T,
  33     C.sort(Scmp)
  34     print >> sys.stderr, os.times()[0]-T,
  35     print "".join((S[c-1] for c in C))
  36     stamp()
  37 
  38 ## Use custom cmp() for sort indexes, avoid "..."+"..."
  39 K+=1
  40 if str(K) in sys.argv[1]:
  41     C=range(N)
  42     SS=S+S
  43     def Scmp(i1,i2): return cmp(S[i1:i1+N],S[i2:i2+N])
  44     print >> sys.stderr, os.times()[0]-T,
  45     C.sort(Scmp)
  46     print >> sys.stderr, os.times()[0]-T,
  47     print "".join((S[c-1] for c in C))
  48     stamp()
  49 
  50 ## Use custom cmp() for sort indexes, avoid slicing
  51 K+=1
  52 if str(K) in sys.argv[1]:
  53     C=range(N)
  54     def Scmp(i1,i2):
  55         for i in xrange(N):
  56             r=cmp(S[(i+i1)%N],S[(i+i2)%N])
  57             if r: return r
  58         return r
  59     print >> sys.stderr, os.times()[0]-T,
  60     C.sort(Scmp)
  61     print >> sys.stderr, os.times()[0]-T,
  62     print "".join((S[c-1] for c in C))
  63     stamp()
  64 
  65 ## Use custom key() for sort indexes
  66 K+=1
  67 if str(K) in sys.argv[1]:
  68     C=range(N)
  69     def Key(i): return S[i:]+S[:i]
  70     print >> sys.stderr, os.times()[0]-T,
  71     C.sort(key=Key)
  72     print >> sys.stderr, os.times()[0]-T,
  73     print "".join((S[c-1] for c in C))
  74     stamp()
  75 
  76 ## Use custom key() for sort indexes, avoid "..."+"..."
  77 K+=1
  78 if str(K) in sys.argv[1]:
  79     C=range(N)
  80     SS=S+S
  81     def Key(i): return SS[i:i+N]
  82     print >> sys.stderr, os.times()[0]-T,
  83     C.sort(key=Key)
  84     print >> sys.stderr, os.times()[0]-T,
  85     print "".join((S[c-1] for c in C))
  86     stamp()
  87 
  88 ## Use array type and custom key() for sort indexes
  89 K+=1
  90 if str(K) in sys.argv[1]:
  91     import array
  92     C=range(N)
  93     SS=array.array('c',S+S)
  94     def Key(i): return SS[i:N+i]
  95     print >> sys.stderr, os.times()[0]-T,
  96     C.sort(key=Key)
  97     print >> sys.stderr, os.times()[0]-T,
  98     print "".join((S[c-1] for c in C))
  99     stamp()
 100 
 101 ## Use numpy array type and custom cmp() for sort indexes
 102 K+=1
 103 if str(K) in sys.argv[1]:
 104     from numpy import *
 105     C=range(N)
 106     SS=array([ord(c) for c in S+S])
 107     def Scmp(i1,i2):
 108         for i in xrange(N):
 109             r=cmp(SS[(i+i1)%N],SS[(i+i2)%N])
 110             if r: return r
 111         return r
 112     print >> sys.stderr, os.times()[0]-T,
 113     C.sort(Scmp)
 114     print >> sys.stderr, os.times()[0]-T,
 115     print "".join((S[c-1] for c in C))
 116     stamp()
 117 
 118 ## Generate full sequence and sort it directly
 119 K+=1
 120 if str(K) in sys.argv[1]:
 121     C=[S[i:]+S[:i] for i in xrange(len(S))]
 122     print >> sys.stderr, os.times()[0]-T,
 123     C.sort()
 124     print >> sys.stderr, os.times()[0]-T,
 125     print "".join(s[-1] for s in C)
 126     stamp()