问题描述
考虑所有长度为 n 的二元向量的集合 S ，其中每个精确地包含 m 个。因此每个向量中都有 nm 个零。
我的目标是从 S k 的向量>，使得这些向量彼此之间尽可能地不同。
Consider the set, S, of all binary vectors of length n where each contains exactly m ones; so there are n-m zeros in each vector.
My goal is to construct a number, k, of vectors from S such that these vectors are as different as possible from each other.
举一个简单的例子，取 n = 4， m = 2和 k = 2，那么可能的解决方案是：[1,1,0,0]和[0,0,1,1]。
As a simple example, take n=4, m=2 and k=2, then a possible solution is: [1,1,0,0] and [0,0,1,1].
似乎这是编码理论文献（？）中的一个开放问题。
It seems that this is an open problem in the coding theory literature (?).
有什么方法（即算法）来找到次优而又好的解决方案？
在这种情况下，汉明距离是否是正确的性能指标？ ？
Is there any way (i.e. algorithm) to find a suboptimal yet good solution ?
Is Hamming distance the right performance measure to use in this case ?
一些想法：
在，作者提出了一些算法来找到向量子集，从而使成对的汉明距离> =某个值 d 。
我实现了Random方法，如下所示：设置一个 SS 集合，该集合可以由任何 S 中的向量。然后，我考虑 S 中剩余的向量
。对于这些向量中的每一个，我检查该向量相对于 SS 中的每个向量是否至少具有距离 d 。如果是这样，则将其添加到 SS 。
如果 SS 的大小取最大可能的 d 是> = k ，那么我认为 SS 是最佳解决方案，我从 SS 中选择 k 个向量的任何子集。
使用这种方法，我认为生成的 SS 将取决于 SS 中初始矢量的身份。即有多个解决方案（？）。
但是，如果 SS 的大小小于< k ？
从本文提出的算法中，我仅了解随机算法。我对Binary lexicographic搜索（第2.3节）感兴趣，但我不知道如何实现它（？）。
Some thoughts:
In this paper, the authors propose a couple of algorithms to find the subset of vectors such that the pairwise Hamming distance is >= a certain value, d.
I have implemented the Random approach as follows: take a set SS, which is initialized by any vector from S. Then, I consider the remaining vectorsin S. For each of these vectors, I check if this vector has at least a distance d with respect to each vector in SS. If so, then it is added to SS.
By taking the maximal possible d, if the size of SS is >= k, then I consider SS as an optimal solution, and I choose any subset of k vectors from SS.Using this approach, I think that the resulting SS will depend on the identity of the initial vector in SS; i.e. there are multiple solutions(?).
But how to proceed if the size of SS is < k ?
From the proposed algorithms in the paper, I have only understood the Random one. I am interested in the Binary lexicographic search (section 2.3) but I don't know how to implement it (?).
推荐答案
也许您发现有用（我写的）。它包含有效创建位串置换的算法。
Maybe you find this paper useful (I wrote it). It contains algorithms that efficiently create permutations of bitstrings.
例如，设置 y = n 恰好生成1个向量，它与输入向量 v 完全相反。对于 y = n-1 ，它将生成 n + 1 个向量： n 矢量，除了一位外，其他所有位都不同；还有1个矢量，其所有位均不同。等等，以不同的值 y 。
Using your definition of n=number of bits in a vector v, setting y=n generates exactly 1 vector which is the exact opposite of the input vector v. For y=n-1, it will generate n+1 vectors: n vectors which differ in all but one bits and 1 vector that differs in all bits. And so on different values of y.
**编辑：添加了摘要，并用'替换了错误的'XOR'否定。
** Added summary and replaced erroneous 'XOR' with 'NEGATE' in the text above.
这篇关于从集合中找到多个最大不同的二元向量的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持！