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

Question

我正在尝试生成长度为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, and 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

- Sean Saito

---

你的问题是什么？ - SaiBot

好问题，请查看编辑 - Sean Saito

如果_d_是奇数，则_n_最多为2（在1的数量的奇偶性上有3个不同值是不可能的）。 - danbanica

@rici 我认为这个问题是关于寻找具有_精确_汉明距离的序列集，而不是最小值，但也许OP可以澄清一下。 - jdehesa

@jdehesa：我知道，而且我已经在括号里说了。但是，正如我所说，我不认为OP的问题更简单，而最小距离问题的困难程度是有指示意义的。（此外，我真的看不出精确距离集的实际好处。这是一个有趣的数学问题，可能更适合在[math.se]上提问。但也许有一些好处。） - rici

Answer 1

让我们构建一个图 G，其中每个 L 位二进制向量 v 是一个顶点。只有当 vi 和 vj 之间的汉明距离等于 d 时，才会有一条边 (vi, vj)。现在我们需要在这个图中找到一个大小为 n 的 团。

团是无向图的一个顶点子集，使得团中任意两个不同的顶点都有边相连。

在任意图中寻找给定大小的团的问题是 NP 完全问题。您可以在这篇维基百科文章中了解这个问题以及一些算法。

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

- DAle

---

这是一个有趣的解决问题的方法，但它丢弃了一些可能使问题更容易解决的信息。 - jdehesa

@jdehesa，图形只是数据的不同表示方式。当然，我们的图形并不是任意的，但我不能证明它属于以下某种特殊情况 https://en.wikipedia.org/wiki/Clique_problem#Special_classes_of_graphs，也许有人可以证明。 - DAle

Answer 2

不是一个真正的解决方案，而是关于生成向量过程中 l、d 和 n 之间关系的部分讨论。无论如何，您可以考虑将问题发布到 Mathematics Stack Exchange（或类似的更正式的论坛）。我在写作时一边推理，但希望没有犯错。

假设我们有 l = 6。由于汉明距离仅取决于位置差异，您可以决定从集合中的第一个任意向量开始（如果有解，某些解可能不包括它，但至少应该有一个）。所以让我们从初始的 v1 = 000000 开始。现在，如果 d = 1，那么显然 n 只能是 1 或 2（与 111111）。如果 d = 1，您会发现 n 也只能是 1 或 2；例如，您可以添加 000001，但任何其他可能的向量都将与您拥有的至少一个向量的距离为 2 或更大。

假设 d = 4。您需要改变4个位置并保留另外2个位置，因此您可以从一个6元素集合中选择4-组合，即15个选择项，例如 001111，010111 等 - 现在您可以看到二项式系数 C(n, d) 加上1是 n 的上限。让我们选择 v2 = 001111，并说保留的位置为 T = [1, 2]，需要更改的位置为 S = [3, 4, 5, 6]。现在，我们可以考虑对 v2 进行更改；但是，为了保持正确的距离，我们必须遵循以下规则：

• 我们必须对 v2 进行4次更改。
• 如果我们更改了 S 中的一个位置，则必须在 T 中的一个位置进行另一次更改（反之亦然）。否则，与 v1 的距离将无法保持。

逻辑上，如果 d 是奇数，现在你已经完成了（只能形成两个元素的集合），但幸运的是，你已经说过你的距离数字是偶数。因此，我们将我们的数字除以二，即 2，并需要从 S 中选择 2 个元素，C(4, 2) = 6，以及从 T 中选择 2 个元素，C(2, 2) = 1，给我们 6 * 1 = 6 个选项——现在你应该注意到，如果 d 是偶数，则 C(d, d/2) * C(l - d, d/2) + 2 是一个新的、更低的上界，用于 n。让我们选择 v3 = 111100。现在，v3 有四种位置：相对于 v1 和 v2 都发生了变化的位置，P1 = [1, 2]；既没有相对于 v1 也没有相对于 v2 发生变化的位置，P2 = []（在这种情况下没有）；相对于 v1 发生了变化但相对于 v2 没有发生变化的位置，P3 = [3, 4]；以及相对于 v2 发生了变化但相对于 v1 没有发生变化的位置，P4 = [5, 6]。同样的情况，我们需要进行 4 次更改，但现在我们对 P1 位置所做的每一次更改都必须意味着对 P2 位置的更改，而我们对 P3 位置所做的每一次更改都必须意味着对 P4 位置的更改。唯一剩下的选择是 v4 = 110011，那么最大的 n 就是 4。

所以，从组合学的角度来看问题，在每次更改后，您将有指数级增长的“位置类型”数量（第一次更改后为2个，第二次为4个，然后是8、16...），这些类型是根据它们在先前添加的向量中是否相等来定义的，并且可以通过“对称”或“补充”关系成对排列。在每个步骤中，您可以（我认为，这是我不太确定的推理部分）贪心地从这些对中选择一组更改，并计算下一步的“位置类型”的大小。如果这一切都正确，您应该能够编写一个基于此的算法，以生成和/或计算给定特定l、d和n的可能向量集合。

- jdehesa