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

kmxz
  • 4.3k

要求找出长度为 2^k + k -1 的 binary string,其任意一个长度为 k 的 substring 都是唯一的。

例如,当 k = 2 时,需要找到长度为 5 的 binary string,使其任意连续两位在整个 string 内是唯一的。满足条件的解共有 4 个:
00110100111100101100。以 00110 为例,00011110 都只出现了一次。

k = 3 时,就需要找到长度为 10 的 binary string,使其任意连续三位在整个 string 内是唯一的。一共有 16 个解,其中字典序最小一个是 0001011100
k = 4 时,有 256 个解,其中字典序最小的一个是 0000100110101111000
k = 5 时,有 65536 个解,其中一个是 000001000110010100111010110111110000

现在我想问的两个问题是:
1、有什么算法可以快速找出一个任意解,或是找出所有的解?
2、看起来似乎 k = n 时的解的数量是 k = n-1 时的解的数量的平方。但是能否证明?

十分感谢诸大神。

回复
阅读 4k
4 个回答

关于计算字符串的问题,用了个比较笨的办法,思路:

1、将字符串形成一个有向图,这个图是有环的,图论算法掌握的不是太好啊,有谁有这方面研究的请指导;
2、然后选择某个节点做起点,求取可以遍历不重复节点的全部路径
3、按照节点顺序组合成字符串,如果字符串长度符合长度要求,则加回到结果集中,否则丢弃
4、计算结果集的空间大小,则得出全部结果数量,如果只要一条路径,在求得一个结果集的时候跳出就可以了

下面是用Python做的代码,有兴趣的可以一起研究算法优化的办法。

import sys
import types

def find_path(s_map, slen):
    res = set()
    if (s_map):
        for i in s_map:
            used = list()
            used.append(i)
            res = find_sub(s_map, used, res, slen)

    return len(res),res

def find_sub(s_map, used, res, slen):
    if (set(used) != set(s_map)):
        for x in s_map[used[-1]]:
            if (x not in used):
                used.append(x)
                print used

                if (set(used) == set(s_map)):
                    sub = used[:-1]
                    s = ''
                    for i in sub:
                        s += i[0]
                    s += used[-1]
                    print s, len(s), len(s_map)
                    if (len(s) == slen):
                        print s
                        res.add(s)
                else:
                    find_sub(s_map, used, res, slen)
                used.remove(x)
            else:
                continue

    return res

def build_map(s_list):
    s_map = dict()

    for s in s_list:
        l = (s_list[0:])
        l.remove(s)
        s_map[s] = [i for i in l if s[1:] == i[:-1]]

    return s_map        

def binary_strings(k):
    if type(k) is types.IntType:
        return [(str(bin(i))[2:]).rjust(k, '0') for i in xrange(2 ** k) ]

def main():
    print find_path(build_map(binary_strings(2)), 2**2+2-1)
    print find_path(build_map(binary_strings(3)), 2**3+3-1)
    print find_path(build_map(binary_strings(4)), 2**4+4-1)

if __name__ == '__main__':
    sys(exit(main()))

直接用遍历就可以了吧?

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

   

生成一个格雷码码表,其中任意连续 2^k <<即 (2^k + k - 1) - (k - 1)>> 个码字可以构成本命题的一个解。

其他的自己发散思考吧……(以上内容理解有错)

2^k + k -1长度的串,共有2^k个substring。长度为k的string也就是2^k个,所以每个string都要出现有且仅有一次。

假设串的k-1前缀是s,串就是sx。我们有如下的顺序满足。sx->ys!x->!ys,其中!x表示x取反,!y同理。->表示中间可能存在其它字符(不能有包含s前缀或者后缀的子串)。

待续。。。

你知道吗?

宣传栏