长度为 2^k + k - 1 的 binary string，使其任意一个长度为 k 的 substring 都是唯一的
要求找出长度为
2^k + k -1
的 binary string，其任意一个长度为
k
的 substring 都是唯一的。
例如，当
k = 2
时，需要找到长度为
5
的 binary string，使其任意连续两位在整个 string 内是唯一的。满足条件的解共有 4 个：
00110
、
10011
、
11001
、
01100
。以
00110
为例，
00
、
01
、
11
、
10
都只出现了一次。
k = 3
时，就需要找到长度为
10
的 binary string，使其任意连续三位在整个 string 内是唯一的。一共有 16 个解，其中字典序最小一个是
0001011100
。
k = 4
时，有 256 个解，其中字典序最小的一个是
0000100110101111000
。
k = 5
时，有 65536 个解，其中一个是
000001000110010100111010110111110000
。
现在我想问的两个问题是：
1、有什么算法可以快速找出一个任意解，或是找出所有的解？
2、看起来似乎 k = n 时的解的数量是 k = n-1 时的解的数量的平方。但是能否证明？
十分感谢诸大神。
火炎之纹章
10 years, 11 months ago
Answers
关于计算字符串的问题，用了个比较笨的办法，思路：
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()))
青丝半缳慵依床
answered 10 years, 11 months ago
