从一组中找到多个最大不同的二元向量

考虑集合，S，所有长度的二进制向量n其中每个恰好包含m那些;所以有n-m每个向量中的零。
我的目标是构建一个数字，k，向量来自S使得这些向量彼此尽可能不同。

举个简单的例子，n=4, m=2 and k=2，那么可能的解是：[1,1,0,0]和[0,0,1,1]。

这似乎是编码理论文献中的一个开放问题（？）。

有什么方法（即算法）可以找到次优但良好的解决方案吗？
在这种情况下，汉明距离是正确的性能衡量标准吗？

一些想法：
In 这张纸 http://emis.impa.br/EMIS/journals/EJC/Volume_13/PDF/v13i1a2.pdf，作者提出了几种算法来查找向量子集，使得成对汉明距离 >= 某个值，d.
我已经实现了随机方法如下：取一组SS，它由任意向量初始化S。然后，我考虑剩余的向量 在S。对于每个向量，我检查该向量是否至少有一个距离d对于每个向量SS。如果是这样，则将其添加到SS.
通过取最大可能的d，如果大小为SS是 >=k，然后我考虑SS作为最佳解决方案，我选择的任何子集k向量来自SS。 使用这种方法，我认为结果SS将取决于初始向量的身份SS;是。有多种解决方案（？）。
但如果尺寸SS是 k ?
从论文中提出的算法来看，我只了解了随机算法。我对二进制词典搜索（第 2.3 节）感兴趣，但我不知道如何实现它（？）。

也许你会发现这张纸 http://btw2017.informatik.uni-stuttgart.de/slidesandpapers/F8-11-13/paper_web.pdf有用（我写的）。它包含有效创建位串排列的算法。

例如，inc()算法：

long  inc(long h_in , long m0 , long m1) {
    long  h_out = h_in | (~m1); //pre -mask
    h_out ++;
    // increment
    h_out = (h_out & m1) | m0; //post -mask
    return  h_out;
}

它需要一个输入h_in并返回下一个更高的值，该值至少比h_in并“匹配”边界m0 and m1。 “匹配”意味着：结果有一个1无论在哪里m0 has a 1，结果有一个0无论在哪里m1 has a 0。不是那个h_in必须是关于以下方面的有效值mo and m1！另外，请注意m0必须按位小于m1， 意思就是m0不能有一个1处于一个位置m1 has a 0.

这可用于生成与给定输入字符串具有最小编辑距离的排列：

假设你有0110，你首先将其否定1001（编辑距离=k）。 设置“m0=1001”和“m1=1001”。使用它只会导致“1001”本身。

现在获取具有编辑距离的所有值k-1，您可以执行以下操作，只需翻转其中一位m0 or m1, then inc()将返回所有位串的有序序列，其差异为k or k-1.

我知道，还不是很有趣，但是你可以修改k位，以及inc()将始终返回具有最大允许编辑差异的所有排列关于m0 and m1.

现在，为了得到all排列，您将不得不使用所有可能的组合重新运行算法m0 and m1.

示例：获取所有可能的排列0110与编辑距离2，您必须使用以下排列来运行 inc()m0=0110 and m1=0110（为了获得排列，必须有一个位位置expanded， 意思是m0被设定为0 and m1被设定为1:

• 位 0 和 1expanded: m0=0010 and m1=1110
• 位 0 和 2expanded: m0=0100 and m1=1110
• 位 0 和 3expanded: m0=0110 and m1=1111
• 位 1 和位 2expanded: m0=0000 and m1=0110
• 位 1 和位 3expanded: m0=0010 and m1=0111
• 位 2 和位 3expanded: m0=0100 and m1=0111

作为起始值h_0我建议简单地使用m0。迭代可以中止一次inc()回报m1.

Summary上述算法生成O(x) all x至少有差异的二元向量y来自给定向量的位（可配置）v.

使用你的定义n=number of bits in a vector v， 环境y=n生成 1 个与输入向量完全相反的向量v. For y=n-1，它会生成n+1向量：n除一位以外所有位均不同的向量和所有位均不同的 1 个向量。等等不同的值y.

**编辑：在上面的文本中添加了摘要并用“NEGATE”替换了错误的“XOR”。