生成n个二进制向量,其中每个向量与每个其他向量的汉明距离为d

Question

我正在尝试生成n一些任意长度的二进制向量l,其中每个向量i的汉明距离d(其中d是偶数)来自每个其他向量j.我不知道是否有任何之间的关系的理论n,l以及d,但如果有这个任务的任何实现我不知道.我目前的实施如下所示.有时候,我成功了,其他时间的代码挂起,这表明无论是)这是不可能找到n这样的载体给定l和d,或b)的搜索需要很长的时间,特别是对于大的值l.

我的问题是:

• 这项任务是否有效实施？

• 之间存在着什么样的理论关系n,l和d？

  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

Answer 1

让我们构建一个图G，其中每L一位二进制向量v都是一个顶点。并且只有当和(vi, vj)之间的汉明距离等于 时才存在边缘。现在我们需要找到一个大小就是这个图的派系。vivjdn

团是无向图的顶点子集，团中每两个不同的顶点都是相邻的。

在任意图中找到给定大小的派系的任务是 NP 完全的。您可以在这篇维基百科文章中阅读有关此问题和一些算法的信息。

这个问题有很多特殊情况。例如，对于完美图，有一种多项式算法。不知道是否可以证明我们的图表是这些特殊情况之一。