Input: A binary reference vector $r$, a multi-set of binary vectors $S$, and a distance function d between binary vectors of equal length. Assume that $r$ and all vectors in $S$ have the same length.
Objective: We want to find a binary vector $r'$ that maximizes the number of vectors $s \in S$ for which $d(r', s) \leq k$ for some fixed $k$.
Constraint: We require that the vector we find is within a certain distance $j$ of the reference vector, so $d(r, r') \leq j$.
Formally, we want $$arg \max\limits_{i : d(i,r) \leq j} \sum\limits_{s \in S} [[d(i,s) \leq k]]$$
Where $[[d(i,s) \leq k]]$ is 1 if $d(i,s) \leq k$, else 0.
Details: We specifically want to solve this problem when the distance function $d$ is the Hamming Distance, but it would be nice to be able to substitute any distance function, or at least any distance function built into Mathematica.
Attempts: The following code (adapted from a post here) computes the unconstrained version of the problem that doesn't enforce a maximum distance to a reference vector.
numApprovals[x_?(MatrixQ[#, NumericQ] &),
y_?(VectorQ[#, NumericQ] &), k_] :=
Length[Select[HammingDistance[#, y] & /@ x, # <= k &]];
length = 3;
maximizeApprovals[x_, k_] :=
Maximize[{numApprovals[x, Array[y, length], k],
Thread[0 <= Array[y, length] <= 1]},
Array[y, length] \[Element] Integers]
answerAssoc =
maximizeApprovals[{{1, 1, 1}, {0, 1, 0}, {1, 1, 1}},
Ceiling[length/2]];
answer = Values[answerAssoc[[2]]]
However, when I try to adding the additional constraint to the maximizeApprovals function, it doesn't work. The following code evaluates symbolically.
maximizeApprovals[x_, k_, ref_, j_] :=
Maximize[{numApprovals[x, Array[y, length], k],
Thread[0 <= Array[y, length] <= 1],
HammingDistance[ref, y] <= j},
Array[y, length] \[Element] Integers]
answerAssoc =
maximizeApprovals[{{1, 1, 1}, {0, 1, 0}, {1, 1, 1}},
Ceiling[length/2], {0, 1, 0}, 1]
Adding pattern testing to the inputs doesn't seem to solve the problem.
However, if I have a fixed length, say 3, I can hard-code the constraint corresponding to the HammingDistance by taking the sum of the absolute difference of the corresponding elements and it works fine.
maximizeApprovals[x_?(MatrixQ[#, NumericQ] &), k_?(IntegerQ[#] &),
ref_?(VectorQ[#, NumericQ] &), j_?(IntegerQ[#] &)] :=
Maximize[{numApprovals[x, Array[y, length], k],
Thread[0 <= Array[y, length] <= 1],
Abs[y[1] - ref[[1]]] + Abs[y[2] - ref[[2]]] +
Abs[y[3] - ref[[3]]] <= j}, {Array[y, length] \[Element]
Integers}]
But if I use the built-in HammingDistance function, or try to use BitXor, to get it to work for any length, neither works.
maximizeApprovals[x_?(MatrixQ[#, NumericQ] &), k_?(IntegerQ[#] &),
ref_?(VectorQ[#, NumericQ] &), j_?(IntegerQ[#] &)] :=
Maximize[{numApprovals[x, Array[y, length], k],
Total[BitXor[ref, y]] <= j,
Thread[
0 <= Array[y, length] <= 1]}, {Array[y, length] \[Element]
Integers}]
maximizeApprovals[x_?(MatrixQ[#, NumericQ] &), k_?(IntegerQ[#] &),
ref_?(VectorQ[#, NumericQ] &), j_?(IntegerQ[#] &)] :=
Maximize[{numApprovals[x, Array[y, length], k],
HammingDistance[ref, y] <= j,
Thread[
0 <= Array[y, length] <= 1]}, {Array[y, length] \[Element]
Integers}]
S
is a set but your example is a list{{1,1,1},{0,1,0},{1,1,1}}
where{1,1,1}
appears twice. In TeX you write $\leq k$ but in your code it is<k
. YournumIssues
is not defined. Please always run code in your post starting from a fresh kernel. Potential problems: Something likeHammingDistance[{a,b},{c,d}]
evaluates to2
right away, as it should according to the documentation, but this may be a problem ifa
,b
,c
,d
are symbols to be replaced by0|1
. $\endgroup$