早起的鸟儿有虫吃

早起的鸟儿有虫吃 查看完整档案

填写现居城市  |  填写毕业院校  |  填写所在公司/组织填写个人主网站
编辑
_ | |__ _ _ __ _ | '_ \| | | |/ _` | | |_) | |_| | (_| | |_.__/ \__,_|\__, | |___/ 该用户太懒什么也没留下

个人动态

早起的鸟儿有虫吃 回答了问题 · 2013-12-15

长度为 2^k + k - 1 的 binary string,使其任意一个长度为 k 的 substring 都是唯一的

直接用遍历就可以了吧?

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,但看起来是成立的

   

关注 0 回答 4

认证与成就

  • 获得 1 次点赞
  • 获得 0 枚徽章 获得 0 枚金徽章, 获得 0 枚银徽章, 获得 0 枚铜徽章

擅长技能
编辑

(゚∀゚ )
暂时没有

开源项目 & 著作
编辑

(゚∀゚ )
暂时没有

注册于 2013-12-15
个人主页被 113 人浏览