0
$\begingroup$

I have a binary array like this:

$$A = [0,1,0,0,1,0]\,.$$

I'm trying to find a way to calculate how many arrays of the same length exist that have a Euclidean distance of 2 or less from this array.

So, how many arrays of length 6 exist where

$$\sqrt{\Sigma(A_{_i} - B_{_i})^2}\leq 2\,?$$

I'm trying to find or create a formula that takes an array like above and outputs a count of how many possible binary arrays exist that fit the conditions of the above formula.

I've looked online for a formula without success.

$\endgroup$
  • 4
    $\begingroup$ If the arrays are both binary, then your problem is equivalent to counting the number of arrays $B$ with Hamming distance at most $2^2 = 4$ from $A$, which is the same as the number of arrays $B$ with Hamming distance at most 4 from any specific array -- such as the array $[0, 0, 0, 0, 0, 0]$. This should give you a hint. $\endgroup$ – j_random_hacker Apr 10 '18 at 14:55
2
$\begingroup$

Don't search for a formula – you'll probably never find something so specific. Instead, try to break up the task into smaller units.

Since your arrays are binary, $$(A_i-B_i)^2 = \begin{cases}0 &\text{if }A_i=B_i\\ 1&\text{if }A_i\neq B_i\,.\end{cases}$$

So $\sqrt{\sum(A_i-B_i)^2}\leq 2$ if, and only if there are at most four values of $i$ such that $A_i\neq B_i$. So you just need to compute the number of ways that $B$ could have zero, one, two, three or four different entries from $A$ (or, more simply, the number of ways that it could have five or six different entries, and subtract that from the total possible values of $B$). This calculation is high-school combinatorics. Note that, because the arrays are binary, there's only one value of $B_i$ that's the same as $A_i$ and only one that's different.

$\endgroup$
  • $\begingroup$ Problem is much more interesting if the numbers are integers, not just 0/1. $\endgroup$ – gnasher729 Apr 11 '18 at 8:30

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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