我正在尝试生成长度为
l
的任意二进制向量i
,其中每个向量i
与其他所有向量j
的汉明距离为d
(其中d
为偶数),需要生成n
个这样的二进制向量。我不确定n
、l
和d
之间是否存在任何理论关系,但我想知道是否有任何实现可以完成此任务。我的当前实现如下所示。有时成功,有时代码会挂起,这表明要么a)无法在给定l
和d
的情况下找到n
这样的向量,要么b)搜索需要很长时间,特别是对于大的l
值。
我的问题是:
- Are there any efficient implementations of this task?
What kind of theoretical relationships exist between
n
,l
, andd
?import numpy as np def get_bin(n): return ''.join([str(np.random.randint(0, 2)) for _ in range(n)]) def hamming(s1, s2): return sum(c1 != c2 for c1, c2 in zip(s1, s2)) def generate_codebook(n, num_codes, d): codebooks = [] seen = [] while len(codebooks) < num_codes: code = get_bin(n) if code in seen: continue else: if len(codebooks) == 0: codebooks.append(code) print len(codebooks), code else: if all(map(lambda x: int(hamming(code, x)) == d, codebooks)): codebooks.append(code) print len(codebooks), code seen.append(code) codebook_vectorized = map(lambda x: map(lambda b: int(b), x), codebooks) return np.array(codebook_vectorized)
例子:
codebook = generate_codebook(4,3,2)
codebook
1 1111
2 1001
3 0101