13
\$\begingroup\$

Preamble

There was a unit test in our codebase which was shuffling a string of length \$52\$ formed from the set of letters \$[A-Z]+[A-Z]\$ and then using the first \$20\$ characters of that shuffled string.
It failed quite a while after being written due to no repeated character being present in those twenty and we wondered how often such a test would be likely to fail. (A little more than one in five hundred and twenty-two times it turns out).

Challenge

Given an alphabet size (\$a\$), a number (\$n\$) of occurrences of each letter, and a prefix length (\$p\$), output the probability that a (uniformly chosen) random permutation of the \$a\times n\$ letters begins with \$p\$ distinct letters.

You may assume that:

  • There will be enough letters to make the prefix: \$p \le n\times a\$
  • Each of the three inputs will be non-negative integers: \$p,n,a\in\Bbb{Z}_{\ge 0}\$

Output in any reasonable format - e.g. a float, a fraction, a pair containing the numerator and denominator (no requirement to simplify); if you're unsure, just ask!

Potential method

This is the method we used to calculate the result we were interested in (from the preamble).

If one thinks of the \$n\times a\$ elements as a bag from which one repeatedly picks the next element of the prefix, then the probability of extending the prefix by one element such that it remains fully distinct is the number of elements remaining in the bag which do not yet appear in the prefix divided by the total number of elements remaining in the bag. As such the probability that the final length \$p\$ prefix will be fully distinct is the product of these probabilities starting with a full bag and an empty prefix:

$$ \prod_{i=0}^{p-1}\frac{n\times(a-i)}{n\times a-i} $$

Test cases

Floating point inaccuracy is acceptable; fractions, if used, do not need to be in simplest form.
Ideally these test cases will all be runnable in a reasonable amount of time, but if golf means crazy inefficiency so be it!

 a   n   p    output                          (as a fraction)
 2   1   0    1                               (1/1)
 2   1   1    1                               (1/1)
 2   1   2    1                               (1/1)
50   1  50    1                               (1/1)
 3   2   0    1                               (1/1)
 3   2   1    1                               (1/1)
 3   2   2    0.8                             (4/5)
 3   2   3    0.4                             (2/5)
 3   2   4    0                               (0/1)
26   2   0    1                               (1/1)
26   2   1    1                               (1/1)
26   2   2    0.9803921568627451              (50/51)
26   2  13    0.13417306435734888             (77824/580027)
26   2  20    0.001916063061695329            (2097152/1094510949)
32   8  11    0.1777403166811693              (31138512896/175191051065)
32   8  22    0.00014139946994082153          (3477211257894250479616/24591402353555723779476075)
32   8  33    0                               (0/1)
\$\endgroup\$
3
  • 1
    \$\begingroup\$ Better title welcome. Imaginary brownie points for beating my 10 byte Jelly answer. \$\endgroup\$ Apr 3, 2021 at 0:55
  • 1
    \$\begingroup\$ Just for completeness, a combinatorial proof of the equivalent formula: There are \$n\$ copies of each of \$a\$ letters; call them "tiles", as in Scrabble tiles. If you consider the \$an\$ tiles in a bag, there are \$an \choose p\$ ways of drawing \$p\$ letters from the bag—that's the denominator. The number of ways of picking them all distinct is: \$a \choose p\$ ways of choosing which letters of the alphabet are in the set of \$p\$, multiplied by \$n\$ choices of tile for each of those letters, giving the numerator \${a \choose p} n^p\$ and the probability \${a\choose p}n^p/{an \choose p}\$. \$\endgroup\$ Apr 4, 2021 at 20:42
  • 1
    \$\begingroup\$ @PedroA cool, let's delete the comment clutter... \$\endgroup\$ Apr 5, 2021 at 16:08

8 Answers 8

6
\$\begingroup\$

Wolfram Language (Mathematica), 32 bytes

#3~b~#/b[#2#3,#]#2^#&
b=Binomial

Try it online!

Input [p, n, a].

The formula can be rewritten \$\dfrac{a\choose p}{an\choose p}n^p\$.


Incidentally, this is fairly trivial using Mathematica's statistics built-ins:

Wolfram Language (Mathematica), 69 bytes

CDF[MultivariateHypergeometricDistribution[#~Max~1,a=Table@##2],1^a]&

Try it online!

Unfortunately, 38-character name aside (the longest name in the default namespace), MultivariateHypergeometricDistribution doesn't handle a nonpositive prefix length, and overall this approach is quite slow for this particular problem.

\$\endgroup\$
3
  • 1
    \$\begingroup\$ Even if MultivariateHypergeometricDistribution was abbreviated down to MHD, the second solution would still be 2 bytes longer than the binomial approach :P \$\endgroup\$ Apr 3, 2021 at 15:21
  • 2
    \$\begingroup\$ @ChartZBelatedly Who knows when I'd get another chance to mention MultivariateHypergeometricDistribution though :) \$\endgroup\$
    – att
    Apr 3, 2021 at 19:23
  • \$\begingroup\$ +1 purely for MultivariateHypergeometricDistribution. \$\endgroup\$ Apr 4, 2021 at 13:16
5
\$\begingroup\$

Haskell, 41 40 bytes

(a#n)p|p<1=1|i<-p-1=(a-i)/(a-i/n)*(a#n)i

Try it online!

Someone's got to post the trivial solution, right? ...Right?

The only reason I don't feel too ashamed is that I managed to save 2 bytes by using the formula (a-i)/(a-i/n) instead of the more obvious n*(a-i)/(n*a-i)

\$\endgroup\$
5
\$\begingroup\$

Jelly, 9 bytes

×\c÷/×Ṫ*¥

Try it online!

Uses att's formula. Takes [a, n] on the left and p on the right

Uses the formula

$$\frac {\binom a p} {\binom {an} p} n^p$$

Unfortunately, the more elegant version of this formula

$$\frac {a!} {(an)!} \frac {(an - p)!} {(a - p)!} n^p$$

takes a lot more bytes in Jelly due to its poor handling of 3 variables

How it works

×\c÷/×Ṫ*¥ - Main link. Takes [a, n] on the left and p on the right
×\        - Scan multiply. Yield [a, a×n]
  c       - Binomial with p. Yield [aCp, (a×n)Cp]
   ÷/     - Reduce by division; aCp ÷ (a×n)Cp
        ¥ - Previous 2 links as a dyad f([a, n], p):
      Ṫ   -   Extract n
       *  - Raise it to the power p
     ×    - Multiply aCp ÷ (a×n)Cp by nᵖ
\$\endgroup\$
1
  • 1
    \$\begingroup\$ Congrats! I didn't think of that kind of \ and combo, smart. \$\endgroup\$ Apr 3, 2021 at 14:30
3
\$\begingroup\$

Excel, 48 bytes

=IFERROR(COMBIN(A2,C2)*B2^C2/COMBIN(A2*B2,C2),0)

Using att's formula. 37 bytes if an error is acceptable when p > a.

Spreadsheet

\$\endgroup\$
4
  • \$\begingroup\$ Nope, errors are not an option for those test cases, only when \$p \ge n\times a\$. What errors? \$\endgroup\$ Apr 3, 2021 at 15:09
  • \$\begingroup\$ I didn't think that was acceptable. COMBIN returns an error when p > a. \$\endgroup\$
    – Axuary
    Apr 3, 2021 at 15:16
  • \$\begingroup\$ Ah, shame - it should give 0 really. \$\endgroup\$ Apr 3, 2021 at 15:35
  • 1
    \$\begingroup\$ There a lot of things Excel should do. Working around them is half the fun? \$\endgroup\$
    – Axuary
    Apr 3, 2021 at 17:45
3
\$\begingroup\$

Python 3, 48 47 bytes

Saved a byte thanks to xnor!!!

f=lambda a,n,p:p<1or(p+~a)/(~-p/n-a)*f(a,n,~-p)

Try it online!

Straightforward calculation of the given formula. Returns either a float or an int or True (for \$1\$).

\$\endgroup\$
2
2
\$\begingroup\$

JavaScript (ES6), 35 bytes

A trivial recursive function expecting (a)(n)(p). May return true instead of 1.

a=>n=>g=p=>!p--||(a-p)/(a-p/n)*g(p)

Try it online!

Commented

a =>            // 1st function taking a
n =>            // 2nd function taking n
g = p =>        // 3rd recursive function taking p
  !p-- ||       //   if p = 0, stop and yield true (coerced to 1)
                //   (decrement p afterwards)
                //   otherwise:
  (a - p) /     //     compute (a - p) / (a - p / n)
  (a - p / n) * //     (same formula as Delfad0r)
  g(p)          //     and multiply by the result of a recursive call
\$\endgroup\$
1
\$\begingroup\$

Retina, 116 114 bytes

.+,(.+),
*_,$'*$1*_,$1*_,
["1/1¶"Lv$`_(_*),\1(_*),\1(_*),(.+)
$.($4*$3)/$.2
+`.+/(.+)¶(.+)/(.+)
$.($2**)/$.($1*$3*

Try it online! Link includes test cases. Takes input in the order p,a,n. Explanation:

.*,(.*),
*_,$'*$1*_,$1*_,

Convert p, na and a to unary.

["1/1¶"Lv$`_(_*),\1(_*),\1(_*),(.+)

Loop i from the maximum of a and p-1 down to 0, also prefix a dummy 1/1 fraction in case p is 0. Calculate na-i and a-i. (If p>a, there will always be an entry where i=a so the final result is zero anyway.)

$.($4*$3)/$.2

Create the fraction n(a-i)/(na-i) in decimal.

+`.+/(.+)¶(.+)/(.+)
$.($2**)/$.($1*$3*

Multiply all of the fractions together.

Previous 116-byte solution:

\d+,
*_,
["1/1¶"Lv$`_(_*),(_*),(.+)
$3*$1,$3*$2/$1,$3*$2
+`_,_
,
+`(/.+)¶(.+)/
$2$1
_*,(_*)
,$.1
+`\d+,(\d+)
$.($1**

Try it online! Link includes test suite that reduces the output fraction to its lowest terms. Takes input in the order p,a,n. Explanation:

\d+,
*_,

Convert p and a to unary.

["1/1¶"Lv$`_(_*),(_*),(.+)

Loop i from p-1 down to 0, also prefix a dummy 1/1 fraction in case p is 0.

$3*$1,$3*$2/$1,$3*$2

Start calculating (na-ni)/(na-i).

+`_,_
,

Perform the subtractions.

+`(/.+)¶(.+)/
$2$1

Collect all the numerators and denominators together.

_*,(_*)
,$.1

Convert all the positive values to decimal. (Other values are converted to zero, but there is always at least one zero if there are any negative values, so extra zeros makes no difference.)

+`\d+,(\d+)
$.($1**

Take the products of all the numerators and denominators.

\$\endgroup\$
1
\$\begingroup\$

C (gcc), 66 59 54 bytes

f(a,n,p,r)float*r,n;{for(*r=1;p--;)*r*=(a-p)/(a-p/n);}

Try it online!

Calculates the given formula. Returns a float through its last parameter (which is a pointer to an uninitialized float).

\$\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.