直接用遍历就可以了吧？

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为３，４，５时都没问题，　但是６就很慢，还有优化的空间
暂时没有证明问题２，但看起来是成立的