直接用遍历就可以了吧?
import sys
# list all bitstring with a length 2^k + k - 1, and
# each k substring is different
class bitString:
def __init__(self, k):
self.k = k
self.num = 0
def generate(self):
self.num += 1
def getString(self):
s = bin(self.num)[2:]
return "0"*(self.k - len(s)) + s
def tryAppend(bitStr, k, oneBit, stringSet):
#print "tring: ", bitStr, " : ", oneBit
newString = bitStr[-(k-1):] + oneBit
if int(newString,2) in stringSet:
return
elif len(bitStr) == 2**k + k - 2:
print "found: ", bitStr+oneBit
return
stringSet.add(int(newString,2))
#print stringSet
tryAppend(bitStr+oneBit, k, "0", stringSet)
tryAppend(bitStr+oneBit, k, "1", stringSet)
stringSet.discard(int(newString,2))
def generatBitString(initString, k):
s = set()
s.add(int(initString, 2))
#print s
tryAppend(initString, k, "0", s)
tryAppend(initString, k, "1", s)
def generatBitStringAll(k):
b = bitString(k)
for i in range(2**k):
generatBitString(b.getString(), k)
b.generate()
pass
if __name__ == "__main__":
k = int(sys.argv[1])
generatBitStringAll(k)
要生成全部,就调用generatBitStringAll,只要生成部分,就只需要调用generatBitStrings
测试了一下,计算k为3,4,5时都没问题, 但是6就很慢,还有优化的空间
暂时没有证明问题2,但看起来是成立的