algorithm - 从一个集合中找到多个最大不同的二元向量

Question

考虑所有长度为 n 的二进制向量的集合 S，其中每个向量恰好包含 m 个；所以每个向量中有 n-m 个零点。
我的目标是从 S 构造一个 k 向量，使这些向量彼此尽可能不同。

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

这似乎是编码理论文献中的一个悬而未决的问题(？)。

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

一些想法:
在 this paper ，作者提出了几个算法来找到向量的子集，使得成对汉明距离 >= 某个值 d。
我已经按如下方式实现了随机方法:取一个集合 SS，它由 S 中的任何向量初始化。然后，我考虑剩余的向量 在 S 中。对于这些向量中的每一个，我检查该向量是否至少有 d 相对于 SS 中每个向量的距离。如果是，则将其添加到 SS。
通过取最大可能的 d，如果 SS 的大小 >= k，那么我将 SS 视为最佳解决方案，然后我从 SS 中选择 k 个向量的任意子集。 使用这种方法，我认为生成的 SS 将取决于 SS 中初始向量的身份；即有多种解决方案(？)。
但是如果 SS 的大小是 <k 怎么办？
从论文中提出的算法中，我只了解了随机算法。我对二进制词典搜索(第 2.3 节)很感兴趣，但我不知道如何实现它(？)。

Answer 1

也许你会找到this paper有用(我写的)。它包含可有效创建位串排列的算法。

例如，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 至少大 1 的下一个更高值并“匹配”边界 m0和 m1 . “匹配”意味着:结果有一个 1无论在哪里m0有一个 1 , 结果有一个 0无论在哪里m1有一个 0 .不是那个h_in必须是关于 mo 的有效值和 m1 !另外，请注意 m0必须按位小于 m1 ，这意味着 m0不能有 1在m1的位置有一个 0 .

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

假设您有 0110 ，您首先将其否定为 1001 (编辑距离 = k)。 设置“m0=1001”和“m1=1001”。使用它只会产生“1001”本身。

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

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

现在，要获得所有 排列，您必须使用m0 的所有可能组合重新运行算法。和 m1 .

示例:获取 0110 的所有可能排列与编辑距离 2 ，您必须使用 m0=0110 的以下排列运行 inc()和 m1=0110 (要获得排列，必须扩展位位置，这意味着 m0 设置为 0 并且 m1 设置为 1 :

• 第 0 位和第 1 位展开:m0=0010和 m1=1110
• 第 0 位和第 2 位展开:m0=0100和 m1=1110
• 第 0 位和第 3 位展开:m0=0110和 m1=1111
• 第 1 位和第 2 位展开:m0=0000和 m1=0110
• 第 1 位和第 3 位展开:m0=0010和 m1=0111
• 第 2 位和第 3 位展开:m0=0100和 m1=0111

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

总结 上述算法在 O(x) 中生成所有 x至少有 y 不同的二元向量来自给定向量的位(可配置)v .

使用您对 n 的定义= number of bits in a vector v , 设置 y=n正好生成 1 个向量，它与输入向量 v 相反.对于 y=n-1 , 它将生成 n+1矢量:n除一位以外所有位都不同的向量和所有位都不同的 1 个向量。依此类推 y 的不同值.

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