5
\$\begingroup\$

Consider \$3\$ binary strings of length \$n\$ chosen independently and uniformly at random. We are interested in computing the exact expected minimum Hamming distance between any pair. The Hamming distance between two strings of equal length is the number of positions at which the corresponding symbols are different.

Task

Given an input n between 2 and 10, inclusive, consider \$3\$ binary strings of length \$n\$ chosen independently and uniformly at random. Output the exact expected minimum Hamming distance between any pair.

Output should be given as a fraction.

Your code should run in TIO without timing out.

\$\endgroup\$
  • 1
    \$\begingroup\$ Challenges should be self-contained: Please add the definition of Hamming Distance. \$\endgroup\$ – AlienAtSystem Jan 31 at 19:10
  • 4
    \$\begingroup\$ Could you please provide some test cases? \$\endgroup\$ – lolad Jan 31 at 20:25
  • 1
    \$\begingroup\$ 0.375, 0.75, 1.125, 1.5234375, 1.93505859375, ...? \$\endgroup\$ – Jonathan Allan Jan 31 at 22:53
  • 1
    \$\begingroup\$ The denominator will be a power of two, so the decimal will terminate. \$\endgroup\$ – Christian Sievers Feb 1 at 0:42
  • 1
    \$\begingroup\$ @xnor My code may have three loops, but it only iterates over the \$n+3 \choose 3\$ ways to write \$n\$ as a sum of four nonnegative integers. For \$n=10\$ that is 286 cases. \$\endgroup\$ – Christian Sievers Feb 1 at 1:14
7
\$\begingroup\$

Pari/GP, 92 90 bytes

2 bytes saved thanks to @Nicolas!

n->sum(a=0,n,sum(b=0,n-a,sum(c=0,n-a-b,n!/a!/b!/c!/(n-a-b-c)!*min(a+b,min(a+c,b+c)))))/4^n

Try it online!

$$ f(n) = \frac{1}{4^n} \sum_{\substack{a+b+c+d=n\\a,b,c,d\geq 0}} \binom{n}{a,b,c,d}\min(a+b,a+c,b+c)$$

A more direct brute force approach may be shorter in some languages, but I'm not sure if that's true for Pari. Anyway, it's a shame that Pari's min only accepts two arguments.

I can avoid the min and be about 6 times faster, but the compensating additional code makes it longer. Maybe in another language this is the shorter way. And maybe it is possible to simplify further and get rid of the innermost sum.

n->sum(a=0,n,sum(b=a,n-a,sum(c=b,n-a-b,n!/a!/b!/c!/(n-a-b-c)!*(a+b)*6/(1+(a==b)+(b==c))!)))/4^n

Try it online!

\$\endgroup\$
  • \$\begingroup\$ This is a really elegant mathematical solution! \$\endgroup\$ – Anush Feb 1 at 18:04
  • \$\begingroup\$ Would it be acceptable to place the f(n)= in the header section and save 5 bytes ? Asking as a new code-golfer. \$\endgroup\$ – Nicolas Feb 4 at 15:47
  • \$\begingroup\$ @Nicolas The remaining part would be a term with n as free variable which is not okay, but I can rewrite it as f=n->... and don't count f=, then the remaining part states the function without binding it to a name. Thanks for reminding me! \$\endgroup\$ – Christian Sievers Feb 4 at 18:37
2
\$\begingroup\$

Jelly, 31 bytes

Ḷṗ4S⁼¥Ƈɓ!×Ṗṁ4SƝṂƲ}:!P$}ð€S,4*$}

A monadic Link accepting an integer which yields a pair of integers, [numerator, denominator] (not reduced to simplest form).

Try it online! Or see all of n=2 to 10 reduced to simplest form.

How?

Uses the same approach as Christian Sievers' Pari/GP answer

Ḷṗ4S⁼¥Ƈɓ!×Ṗṁ4SƝṂƲ}:!P$}ð€S,4*$} - Link: integer, n
Ḷ                               - lowered range -> [0..n-1]
 ṗ4                             - Cartesian power 4 (all length 4 tuples using alphabet [0..n-1]
      Ƈ                         - filter keep those for which:
     ¥                          -   last two links as a dyad:
   S                            -     sum
    ⁼                           -     equals n?
       ɓ               ð€       - for each tuple do f(n, tuple):
        !                       -   factorial = n*(n-1)*...*1
                 }              -   use right argument:
                Ʋ               -     last four links as a monad:
          Ṗ                     -       pop i.e. (a,b,c,d)->(a,b,c)
           ṁ4                   -       mould like 4 -> (a,b,c,a)
              Ɲ                 -       for neighbours:
             S                  -         sum -> (a+b,b+c,c+a)
               Ṃ                -       minimum
         ×                      -   multiply
                      }         -   use right argument:
                     $          -     last two links as a monad:
                   !            -       factorial -> (a!,b!,c!,d!)
                    P           -       product -> a!×b!×c!×d!
                  :             -   integer division
                         S      - sum
                              } - use right argument:
                             $  -   last two links as a monad:
                           4    -     four
                            *   -     exponentiate -> 4^n
                          ,     - pair
\$\endgroup\$
  • \$\begingroup\$ Very nice. Maybe I should have made the range 2..30 :) \$\endgroup\$ – Anush Feb 1 at 18:04
  • 1
    \$\begingroup\$ This does \$n=30\$ in ~18 seconds. It's much slower than the Pari/GP because I create all \$n^4\$ (a,b,c,d) tuples and filter to those that sum to \$n\$ (because it's golf). \$\endgroup\$ – Jonathan Allan Feb 1 at 18:11
2
\$\begingroup\$

05AB1E, 26 bytes

Ý4ãʒOQ}ε¨Ćü+ßI!*y!P÷}O4Im‚

Port of @JonathanAllan's Jelly answer, which uses the same formula as @ChristianSievers's Pari/GP answer.
Just like his answer, the output is not reduced to its simplest form.

Try it online or verify all test cases.

Explanation:

Ý                 # Push a list in the range [0, (implicit) input-integer]
                  # (NOTE: Jonathan's Jelly answer uses the range [0,input) instead of
                  #  [0,input], but that doesn't pose an issue, since the mapped value will
                  #  result in 0, not affecting the total sum)
 4ã               # Create all possible quartets by using the cartesian product with 4
   ʒ              # Filter these quartets by:
    O             #  Take the sum
     Q            #  And check if it's equal to the (implicit) input-integer
   }ε             # After the filter: map each remaining quartet [a,b,c,d] to:
     ¨            #  Remove the last item d: [a,b,c]
      Ć           #  Enclose the list, appending its own head: [a,b,c,a]
       ü+         #  Sum each consecutive pair: [a+b,b+c,c+a]
         ß        #  Pop and push the minimum of this
          I!      #  Push the input, and take its factorial
            *     #  Multiply both by each other
             y!   #  Take the factorial of each value in the quartet: [a!,b!,c!,d!]
               P  #  Take the product of this: a!*b!*c!*d!
                ÷ #  Integer-divide the two: (min(a+b,b+c,c+a)*n!) // (a!*b!*c!*d!)
    }O            # After the map: take the sum of all values in the list
       I          # Push the input-integer again
      4 m         # And take 4 to the power this
         ‚        # And finally pair both together
                  # (after which this pair is output implicitly as result)
\$\endgroup\$

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.