从指定二元向量集中选取k个差异最大化向量的技术问询

Is this an open problem in coding theory? #

Yes, this problem ties directly to constant-weight codes—a well-studied but still active area of coding theory. Constant-weight codes are exactly sets of binary vectors of length n with exactly m 1s, where every pair has a minimum Hamming distance d. Finding the maximum size of such a code for arbitrary n, m, and d is an open problem; there’s no universal closed-form solution, so researchers rely on bounds, constructive algorithms, and heuristics. Your goal of selecting k vectors to maximize pairwise differences is equivalent to finding the largest possible d such that a constant-weight code of size k exists for your n and m.

Is Hamming distance the right performance metric here? #

Absolutely. Hamming distance counts the number of positions where two vectors differ, which is exactly the "difference" you want to maximize between pairs. For constant-weight vectors, note that the Hamming distance between any two is 2t, where t is the number of positions where one has a 1 and the other has a 0 (since each such pair contributes two to the distance: one 1→0 and one 0→1). So maximizing pairwise Hamming distance perfectly aligns with your goal.

Algorithms for High-Quality Solutions #

Addressing Your Random Greedy Method’s Limitations #

Your current random approach is a common heuristic, but here’s how to handle its shortcomings:

• Multiple initial vectors: Yes, different starting vectors can lead to different subsets SS for the same d. To get a better solution, run the algorithm 10-20 times with random initial vectors and keep the subset that either has the largest size or the highest minimum pairwise distance.
• When SS size < k: If even with d=2 (the smallest non-trivial distance for constant-weight vectors) you can’t reach k vectors, you’ll need to relax the strict minimum distance requirement. Instead, try a greedy approach that adds the vector with the largest average Hamming distance to all vectors already in SS. This will give you a subset where pairwise differences are as large as possible on average, even if some pairs fall below your initial d threshold.

Implementing Binary Lexicographic Search (Section 2.3) #

Binary lexicographic search is a deterministic way to build constant-weight codes with strong minimum distances. Here’s a step-by-step implementation guide:

1. Generate lex-ordered vectors: First, create all vectors in S sorted lexicographically. You can do this by generating all combinations of m positions out of n (to place the 1s), then converting each combination to a binary vector. For example, for n=4, m=2, the lex order is [1,1,0,0], [1,0,1,0], [1,0,0,1], [0,1,1,0], [0,1,0,1], [0,0,1,1].
2. Build the subset deterministically: Start with the first vector in the sorted list. Then iterate through each subsequent vector:
   • For the candidate vector, compute its Hamming distance to every vector already in your subset.
   • If all distances are ≥ d, add it to the subset.
3. Optimize distance checks: To speed things up, represent vectors as integers (each bit corresponds to a position). The Hamming distance between two vectors is the number of set bits in their XOR result—use built-in functions like bin(x ^ y).count('1') (in Python) for fast calculations.

The "binary" part refers to using a binary search-like strategy to efficiently verify the distance condition against existing subset members (though for smaller subsets, a naive check is often sufficient). This method avoids randomness and tends to produce consistent, high-quality subsets.

Extra Tips #

• Use Johnson bounds to get a sense of the maximum possible size of a constant-weight code for your parameters. This helps you evaluate how good your solution is compared to the theoretical upper limit.
• For larger n and m, consider metaheuristics like simulated annealing or genetic algorithms. These can explore the solution space more thoroughly than greedy methods, leading to better subsets.

内容的提问来源于stack exchange，提问作者din