2
$\begingroup$

Problem: Given an $n \times m$ matrix with binary values $(0,1)$, find a binary vector that minimizes the sum of Hamming Distances to the rows.

Example: If the matrix is {{$1,1,1$},{$0,0,0$},{$1,0,1$}} we want to return the vector {$1,0,1$} which has a sum of HammingDistances of $1 + 2 + 0 = 3$.

Current Attempt: We can use a pure function to compute the HammingDistances between the rows of the input matrix (x) and a vector(y).

agreement[x_, y_] := HammingDistance[#, y] & /@ x 

However, we can't plug this directly in to the built-in Minimize function. The following gives an invalid constraint error.

Minimize[agreement[{{1,1,1},{0,0,0},{1,0,1}}, y], y] 
$\endgroup$
3
  • $\begingroup$ Welcome to Mathematica.SE! I suggest the following: 1) As you receive help, try to give it too, by answering questions in your area of expertise. 2) Take the tour! 3) When you see good questions and answers, vote them up by clicking the gray triangles, because the credibility of the system is based on the reputation gained by users sharing their knowledge. Also, please remember to accept the answer, if any, that solves your problem, by clicking the checkmark sign! $\endgroup$
    – Michael E2
    Jul 15, 2022 at 18:16
  • $\begingroup$ Generally speaking, one question, one problem, unless there's a strong reason to think the same solution will solve both problems. There's probably some overlap in yours, but the problems seem distinct to me. (I take it, in the last example, the triplets of numbers should be vectors, right?) $\endgroup$
    – Michael E2
    Jul 15, 2022 at 18:19
  • $\begingroup$ You can format inline code and code blocks by selecting the code and clicking the {} button above the edit window. The edit window help button ? is useful for learning how to format your questions and answers. You may also find the meta Q&A, How to copy code from Mathematica so it looks good on this site, helpful $\endgroup$
    – Michael E2
    Jul 15, 2022 at 18:20

1 Answer 1

4
$\begingroup$

Keep agreement[] from evaluating on symbolic y with the _?... pattern tests. Also total up the Hamming distances.

ClearAll[agreement];
agreement[
  x_?(MatrixQ[#, NumericQ] &),
  y_?(VectorQ[#, NumericQ] &)] :=
   HammingDistance[#, y] & /@ x // Total;

Minimize[
 {agreement[{{1, 1, 1}, {0, 0, 0}, {1, 0, 1}}, Array[y, 3]],
  Thread[0 <= Array[y, 3] <= 1]},
 Array[y, 3] \[Element] Integers]

(*  {3, {y[1] -> 1, y[2] -> 0, y[3] -> 1}}  *)
$\endgroup$
3
  • $\begingroup$ Beautiful, thank you! $\endgroup$
    – B A
    Jul 15, 2022 at 18:38
  • $\begingroup$ This strategy of using pattern tests to prevent evaluating on the symbolic expressions for maximizing/minimizing user-defined functions seems generally applicable so I appreciate the explanation! $\endgroup$
    – B A
    Jul 15, 2022 at 18:40
  • $\begingroup$ @BA I believe it works here with Minimize because the domain is bounded. If it's infinite, you probably have to use NMinimize.... $\endgroup$
    – Michael E2
    Jul 15, 2022 at 18:45

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.