20
\$\begingroup\$

A deck of cards is the Cartesian product of S suits and R ranks. Many, though not all, card games use S=4 and R∊{6,8,13}. A hand of H cards is dealt from the deck. Its distribution, a.k.a. "hand pattern", is an array that describes how many cards you got from each suit, ignoring suit order (so, it's like a multi-set). Given a distribution D satisfying len(D)=S, 1≤sum(D)=H≤S×R, 0≤D[i]≤R, D[i]≥D[i+1], find the probability of it occurring.

Input: an integer R and an array D.

Output: the probability with at least 5 digits after the decimal mark; trailing zeroes may be skipped; scientific notation is ok.

Loopholes forbidden. Shortest wins.

Tests:

R    D               probability
13   4 4 3 2     ->  0.2155117564516334148528314355068773
13   5 3 3 2     ->  0.1551684646451760586940386335649517
13   9 3 1 0     ->  0.0001004716813294328274372174524508
13   13 0 0 0    ->  0.0000000000062990780897964308603403
8    3 2 2 1     ->  0.4007096203759162602321667950144035
8    4 2 1 1     ->  0.1431105787056843786543452839337155
8    2 2 1 0     ->  0.3737486095661846496106785317018910
8    3 1 1 0     ->  0.2135706340378197997775305895439377
15   4 4 3 2 1   ->  0.1428926269185580521441708109954798
10   3 0 0       ->  0.0886699507389162561576354679802956
10   2 1 0       ->  0.6650246305418719211822660098522167
10   1 1 1       ->  0.2463054187192118226600985221674877

See also Bridge hand patterns in Wikipedia.

EDIT: dropped unnecessary restriction H≤R

EDIT: added constraint H≥1

\$\endgroup\$
  • \$\begingroup\$ Can we assume that D is sorted? \$\endgroup\$ – orlp Nov 20 '17 at 0:18
  • 1
    \$\begingroup\$ @orip yes, that's what I meant by D[i]≥D[i+1] \$\endgroup\$ – ngn Nov 20 '17 at 0:26
  • \$\begingroup\$ Cards I know start from 1 not from 0... \$\endgroup\$ – RosLuP Nov 22 '17 at 15:10
  • \$\begingroup\$ @RosLuP what do you mean? \$\endgroup\$ – ngn Nov 22 '17 at 15:30
  • \$\begingroup\$ I'm sure i didn't understand something... If Cards are represented from number 1,2, ...,13 all * 4; so what does it mean "13 0 0 0" in example? 0 means card 0? \$\endgroup\$ – RosLuP Nov 22 '17 at 16:11
9
+300
\$\begingroup\$

APL (Dyalog Unicode), 30 chars

×/!⍨,z,1÷((z←!∘≢⊢)⌸⊢),×∘≢!⍨1⊥⊢

Try it online!

Using @orlp’s formula.

\$\endgroup\$
  • \$\begingroup\$ Excellent, well done! The "+100" button says I must wait 10 more hours before I can award the bounty. After that I'll set up another one for +200. \$\endgroup\$ – ngn Jun 14 '18 at 21:34
  • \$\begingroup\$ Yay I win! thanks @jayprich \$\endgroup\$ – FrownyFrog Jun 14 '18 at 21:41
  • \$\begingroup\$ @FrownyFrog How do you like Dyalog APL compared with J? \$\endgroup\$ – Jonah Jun 15 '18 at 4:12
8
\$\begingroup\$

Python 3, 134 bytes

b=lambda n,k:k<1or n*b(n-1,k-1)/k
f=lambda R,D,i=1,s=1,t=0:D and b(R,D[0])*i/s*f(R,D[1:],i+1,(D[0]in D[1:])*s+1,t+D[0])or 1/b(~-i*R,t)

Formula is the product of binom(R, d) for each element d in D, times factorial(len(D)), divided by the product of factorial(len(S)) for each S in the groupings of D (e.g. [4, 4, 3, 2] has groupings [[4, 4], [3], [2]]), finally divided by binom(len(D) * R, sum(D)).

Or in math notation, assuming m contains the multiplicities of the n unique elements in D:

$$ \frac{|D|!}{m_1!\cdot m_2!\cdots m_n!} \binom{|D|\cdot R}{\sum D}^{-1} \prod_{d\in D}\binom{R}{d} $$

\$\endgroup\$
  • 2
    \$\begingroup\$ for a brief moment you made me believe PPCG now supports LaTeX :) \$\endgroup\$ – ngn Nov 20 '17 at 1:18
  • \$\begingroup\$ Inlining the two functions I got 136 but maybe that can be golfed more (uses i=0 to mean b() and uses R,D for n,k). \$\endgroup\$ – Jonathan Allan Nov 20 '17 at 6:18
7
\$\begingroup\$

R, 90 85 83 bytes

function(R,D,l=sum(D|1),K=choose)prod(K(R,D),1:l,1/gamma(1+table(D)))/K(R*l,sum(D))

Try it online!

I observed the same thing as orlp, but I picked a nice language that has combinatorics builtins.

Explanation:

function(R,D,             # next are optional arguments
 l=sum(D|1),              # alias for length of D, aka S
 K=choose)                # alias for choose
  prod(                   # take the product of:
    K(R,D),               # "choose" is vectorized over R and D
    1:l,                  # S!
    1/gamma(1+            # gamma(n+1) = n! for integer n
     table(D))            # multiplicities of unique elements of D
  ) /                     # divide by
  K(R*l, sum(D))          # R*S choose H
                          # return last computation (which is all the computation)

\$\endgroup\$
  • \$\begingroup\$ You can save a few more with this: "<"=choose (outside of function) and potentially use seq depending on ngn's answer to the comment I posted this morning. \$\endgroup\$ – JayCe Jun 14 '18 at 20:57
6
\$\begingroup\$

Jelly,  22  20 bytes

-2 bytes using a new quick, ʋ, and a new monadic atom

ĠẈ!;L×c⁸S¤ʋ
L!;c@֍P

A dyadic link, taking the dealt-distribution, D, on the left and the number-of-ranks, R, on the right, which returns the probability of occurrence.

Try it online! or see the test-suite

How?

ĠẈ!;L×c⁸S¤ʋ - Link 1, denomParts: list, distribution (D); number, ranks (R)
                                                                 e.g. [3,3,3,2,2]; 8
Ġ           - group indices of D by their values                      [[4,5],[1,2,3]]
 Ẉ          - length of each group                                    [2,3]
  !         - factorial (vectorises)                                  [2,6]
          ʋ - last four links as a dyad
            - ... i.e. totalWaysToDeal = f(list, distribution (D); number, ranks (R)):
    L       - length of D                                             5
     ×      - multiply by R = total number of cards                   40
         ¤  - nilad followed by link(s) as a nilad:
       ⁸    -   chain's left argument, D                              [3,3,3,2,2]
        S   -   sum = total cards dealt                               13
      c     - binomial                                        40C13 = 12033222880
   ;        - concatenate                                             [2,6,12033222880]                                                  

L!;c@֍P - Main link: list, distribution (D); number, ranks (R)
         -                                                  e.g. [3,3,3,2,2]; 8
L        - length of D = number of suits                         5
 !       - factorial                                             120
   c@    - R binomial (vectorised across) D     (8C3=56;8C2=28)  [56,56,56,28,28]
  ;      - concatenate                                           [120,56,56,56,28,28]
      ç  - call the last link (1) as a dyad = denomParts(D,R)    [2,6,12033222880]
     ÷   - divide (vectorises)                                   [120/2,56/6,56/12033222880,56,28,28]
       P - product                                               0.11441900924883391
\$\endgroup\$
5
\$\begingroup\$

05AB1E, 21 bytes

cP¹g!*¹γ€g!P¹gI*¹Oc*/

Try it online!

Explanation

 P                      # product of
c                       # bin(input1,input2)
     *                  # multiplied by
    !                   # fac of
  ¹g                    # length of input1
                    /   # divided by
           P            # product of
          !             # fac of each
        €g              # length of each
      ¹γ                # chunk of consecutive equal elements of input1
                   *    # multiplied by
                  c     # bin of
            ¹g          # length of input1
              I*        # times input2
                ¹O      # and sum of input1
\$\endgroup\$
3
\$\begingroup\$

Pyth, 32 bytes

cc*.!lQ*F.cLvzQ*F.!hMr8Q.c*vzlQs

Try it here! or Verify all the test cases!

How this works?

cc*.!lQ*F.cLvzQ*F.!hMr8Q.c*vzlQs ~ Full program. D = list, R = number.

   .!                            ~ The factorial of...
     lQ                            ~ The length of D.
  *                              ~ Multiplied by...
       *F                          ~ The product of the elements of...
         .c                          ~ The nCr between...
           L  Q                        ~ Each element of D, and...
            vz                         ~ R.
 c                               ~ Divided by...
               *F                  ~ The product of the elements of...
                 .!                  ~ The factorial of each...
                   hM                  ~ Heads. Count of adjacent elements in...
                     r8Q                 ~ The run length encoding of D.
c                                ~ Divided by...
                        .c         ~ The nCr between...
                          *          ~ The product of...
                           vz          ~ R, and...
                             lQ        ~ The length of D.
                               s   ~ And the sum of D.
                                 ~ Output implicitly.
\$\endgroup\$
3
\$\begingroup\$

APL (Dyalog), 42 bytes

{×/(!≢⍵),(⍵!⍺),÷((+/⍵)!⍺×≢⍵),!≢¨⍵⊂⍨1,2≠/⍵}

Try it online!

Still golfing.

\$\endgroup\$
  • \$\begingroup\$ challenge: 30 bytes \$\endgroup\$ – ngn Nov 23 '17 at 10:01
  • \$\begingroup\$ @ngn challenge accepted \$\endgroup\$ – Uriel Nov 23 '17 at 13:31
  • \$\begingroup\$ Sorry, it's actually 30 chars. With the risk of giving away information: one of my chars is not in the Classic charset, I didn't realise that at first. \$\endgroup\$ – ngn Nov 23 '17 at 21:35
  • \$\begingroup\$ @ngn Can't you just use Adám's character set to make it 30 bytes? \$\endgroup\$ – Probie Jun 14 '18 at 10:40
  • \$\begingroup\$ @Probie yep, that's what I meant by "SBCS" in the bounty description \$\endgroup\$ – ngn Jun 14 '18 at 11:37
2
\$\begingroup\$

Clojure, 153 bytes

#(apply +(for[_(range 1e06):when(=(remove #{0}%)(reverse(sort(vals(frequencies(take(apply + %)(shuffle(for[i(range %2)j(range(count %))]j))))))))]1e-06))

Just a brute-force simulation, to get more precision increase the iteration count and the "1 / N" value at the end accordingly. First argument is the counts and 2nd argument is the number of cards in the deck per suite.

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

J, 57 bytes

](#@]%~[:+/[-:"1[:\:~@(#/.~)"1+/@[{."1])i.@!@(*+/)A.(##\)

Try it online!

This runs in O(golf) and will choke on many of the test cases (though works theoretically), which would be fine if it were golfier. But I'm stuck on trimming it down, especially with avoiding those repeated "1. If anyone wants to help, here's the parsed version...

The right side of the main fork is all possible deals of the deck, and the left side of the main fork is just the original right arg, ie, the suit mask we're matching against.

Inside, from each "shuffled" deck, we take the first hand elements, then group them using key /. and sort the result, and check if that matches the suit mask in question. We add add up the total number that do match, and divide that into the length of all possible decks.

┌─┬─────────────────────────────────────────────────────────────────────────────────────────────────┬─────────────────────────────────────┐
│]│┌───────┬─────┬─────────────────────────────────────────────────────────────────────────────────┐│┌──────────────────────┬──┬─────────┐│
│ ││┌─┬─┬─┐│┌─┬─┐│┌──┬─────┬──────────────────────────────────────────────────────────────────────┐│││┌────────┬─┬─────────┐│A.│┌─┬─────┐││
│ │││#│@│]│││%│~│││[:│┌─┬─┐│┌─┬────────┬─────────────────────────────────────────────────────────┐│││││┌──┬─┬─┐│@│┌─┬─────┐││  ││#│┌─┬─┐│││
│ ││└─┴─┴─┘│└─┴─┘││  ││+│/│││[│┌──┬─┬─┐│┌──┬───────────────────────────┬────────────────────────┐│││││││i.│@│!││ ││*│┌─┬─┐│││  ││ ││#│\││││
│ ││       │     ││  │└─┴─┘││ ││-:│"│1│││[:│┌─────────────────────┬─┬─┐│┌───────────┬────────┬─┐│││││││└──┴─┴─┘│ ││ ││+│/││││  ││ │└─┴─┘│││
│ ││       │     ││  │     ││ │└──┴─┴─┘││  ││┌──────┬─┬──────────┐│"│1│││┌─────┬─┬─┐│┌──┬─┬─┐│]││││││││        │ ││ │└─┴─┘│││  │└─┴─────┘││
│ ││       │     ││  │     ││ │        ││  │││┌──┬─┐│@│┌──────┬─┐││ │ ││││┌─┬─┐│@│[│││{.│"│1││ ││││││││        │ │└─┴─────┘││  │         ││
│ ││       │     ││  │     ││ │        ││  ││││\:│~││ ││┌─┬──┐│~│││ │ │││││+│/││ │ ││└──┴─┴─┘│ │││││││└────────┴─┴─────────┘│  │         ││
│ ││       │     ││  │     ││ │        ││  │││└──┴─┘│ │││#│/.││ │││ │ ││││└─┴─┘│ │ ││        │ ││││││└──────────────────────┴──┴─────────┘│
│ ││       │     ││  │     ││ │        ││  │││      │ ││└─┴──┘│ │││ │ │││└─────┴─┴─┘│        │ ││││││                                     │
│ ││       │     ││  │     ││ │        ││  │││      │ │└──────┴─┘││ │ ││└───────────┴────────┴─┘│││││                                     │
│ ││       │     ││  │     ││ │        ││  ││└──────┴─┴──────────┘│ │ ││                        │││││                                     │
│ ││       │     ││  │     ││ │        ││  │└─────────────────────┴─┴─┘│                        │││││                                     │
│ ││       │     ││  │     ││ │        │└──┴───────────────────────────┴────────────────────────┘││││                                     │
│ ││       │     ││  │     │└─┴────────┴─────────────────────────────────────────────────────────┘│││                                     │
│ ││       │     │└──┴─────┴──────────────────────────────────────────────────────────────────────┘││                                     │
│ │└───────┴─────┴─────────────────────────────────────────────────────────────────────────────────┘│                                     │
└─┴─────────────────────────────────────────────────────────────────────────────────────────────────┴─────────────────────────────────────┘
\$\endgroup\$
  • 1
    \$\begingroup\$ Orlp's formula scored 42 for APL, maybe that would score less than 58 on J? \$\endgroup\$ – Uriel Nov 20 '17 at 21:05
  • 1
    \$\begingroup\$ I get 45 so far that way f=:(([:!#)%[:*/[:!#/.~)@]**/@(]![)%+/@]![*#@] TIO \$\endgroup\$ – jayprich Jun 14 '18 at 18:27

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.