Problème d'anniversaire généralisé

12

Ce soir, ma fiancée m'a emmené dîner pour fêter mon anniversaire. Pendant notre absence, j'ai entendu Happy Birthday chanté devant 5 invités différents (moi y compris), dans un restaurant de 50 personnes. Cela m'a fait me demander - le problème d'anniversaire d'origine (trouver la probabilité que 2 personnes dans une pièce de Npersonnes partagent le même anniversaire) est très simple et direct. Mais qu'en est-il du calcul de la probabilité qu'au moins des kpersonnes sur des Npersonnes partagent le même anniversaire?

Au cas où vous vous poseriez la question, la probabilité qu'au moins 5 personnes sur 50 au total partagent le même anniversaire est d'environ 1/10000.

Le défi

Étant donné deux nombres entiers Net k, où N >= k > 0, produire la probabilité qu'au moins les kpersonnes d'un groupe de Npersonnes partagent le même anniversaire. Pour simplifier les choses, supposons qu'il y a toujours 365 anniversaires possibles et que tous les jours sont également probables.

Pour k = 2, cela se résume au problème d'anniversaire d'origine, et la probabilité est 1 - P(365, N)/(365)**N(où P(n,k)est le nombre de permutations de longueur k formées de n éléments ). Pour des valeurs plus grandes de k, cet article de Wolfram MathWorld peut s'avérer utile.

Règles

  • La sortie doit être déterministe et aussi précise que possible pour la langue choisie. Cela signifie aucune estimation de Monte Carlo ou approximation de Poisson.
  • Net kne sera pas plus grand que le plus grand entier représentable dans la langue choisie. Si votre langue choisie n'a pas de maximum dur sur les entiers (à part les contraintes de mémoire), alors Nelle kpeut être arbitrairement grande.
  • Les erreurs de précision résultant d'inexactitudes en virgule flottante peuvent être ignorées - votre solution doit supposer des flottants parfaitement précis et de précision infinie.

Cas de test

Format: k, N -> exact fraction (float approximation)

2, 4 -> 795341/48627125 (0.016355912466550306)
2, 10 -> 2689423743942044098153/22996713557917153515625 (0.11694817771107766)
2, 23 -> 38093904702297390785243708291056390518886454060947061/75091883268515350125426207425223147563269805908203125 (0.5072972343239854)
3, 3 -> 1/133225 (7.5060987051979735e-06)
3, 15 -> 99202120236895898424238531990273/29796146005797507000413918212890625 (0.0033293607910766013)
3, 23 -> 4770369978858741874704938828021312421544898229270601/375459416342576750627131037126115737816349029541015625 (0.01270542106874784)
3, 88 -> 121972658600365952270507870814168157581992420315979376776734831989281511796047744560525362056937843069780281314799508374037334481686749665057776557164805212647907376598926392555810192414444095707428833039241/238663638085694198987526661236008945231785263891283516149752738222327030518604865144748956653519802030443538582564040039437134064787503711547079611163210009542953054552383296282869196147657930850982666015625 (0.5110651106247305)
4, 5 -> 1821/17748900625 (1.0259790386313012e-07)
4, 25 -> 2485259613640935164402771922618780423376797142403469821/10004116148447957520459906484225353834116619892120361328125 (0.0002484237064787077)
5, 50 -> 786993779912104445948839077141385547220875807924661029087862889286553262259306606691973696493529913926889614561937/7306010813549515310358093277059651246342214174497508156711617142094873581852472030624097938198246993124485015869140625 (0.00010771867165219201)
10, 11 -> 801/8393800448639761033203125 (9.542757239717371e-23)
10, 20 -> 7563066516919731020375145315161/4825745614492126958810682272575693836212158203125 (1.5672327389589693e-18)
10, 100 -> 122483733913713880468912433840827432571103991156207938550769934255186675421169322116627610793923974214844245486313555179552213623490113886544747626665059355613885669915058701717890707367972476863138223808168550175885417452745887418265215709/1018100624231385241853189999481940942382873878399046008966742039665259133127558338726075853312698838815389196105495212915667272376736512436519973194623721779480597820765897548554160854805712082157001360774761962446621765820964355953037738800048828125 (1.2030611807765361e-10)
10, 200 -> 46037609834855282194444796809612644889409465037669687935667461523743071657580101605348193810323944369492022110911489191609021322290505098856358912879677731966113966723477854912238177976801306968267513131490721538703324306724303400725590188016199359187262098021797557231190080930654308244474302621083905460764730976861073112110503993354926967673128790398832479866320227003479651999296010679699346931041199162583292649095888379961533947862695990956213767291953359129132526574405705744727693754517/378333041587022747413582050553902956219347236460887942751654696440740074897712544982385679244606727641966213694207954095750881417642309033313110718881314425431789802709136766451022222829015561216923212248085160525409958950556460005591372098706995468877542448525403291516015085653857006548005361106043070914396018461580475651719152455730181412523297836008507156692430467118523245584181582255037664477857149762078637248959905010608686740872875726844702607085395469621591502118462813086807727813720703125 (1.21685406174776e-07)
code-golf combinatorics probability-theory Mego
la source
9
Bon anniversaire en retard)!
Luis Mendo
Peut-être ajouter quelques cas de test pour les petits nombres?
Luis Mendo
@LuisMendo J'en ajouterai plus après avoir dormi quelques heures :)
Mego
6
Il convient de noter que la probabilité que les gens mangent dans un restaurant n'est probablement pas indépendante de savoir si c'est leur anniversaire, de sorte que la probabilité de cinq anniversaires sur 50 personnes est probablement plus élevée que la logique du problème d'anniversaire ne le suggère.
Glen O
@GlenO Bon point!
Luis Mendo

Réponses:

3

Gelée , 17 16 octets

ĠZL
365ṗÇ€<¬µS÷L

Extrêmement inefficace. Essayez-le en ligne! (mais gardez N en dessous de 3 )

Comment ça fonctionne

365ṗÇ€<¬µS÷L  Main link. Left argument: N. Right argument: K

365ṗ          Cartesian product; generate all lists of length N that consist of
              elements of [1, ..., 365].
    ǀ        Map the helper link over all generated lists. It returns the highest
              amount of people that share a single birthday.
      <       Compare each result with K.
       ¬      Negate.
        µS÷L  Take the mean by dividing the sum by the length.


ĠZL           Helper link. Argument: A (list of integers)

Ġ             Group the indices have identical values in A.
 Z            Zip; transpose rows with columns.
  L           Take the length of the result, thus counting columns.
Dennis
la source
1
"garder N en dessous de 3" ... n'est-ce pas trop restrictif?
Neil
2
@Neil La solution est valable pour toutes les entrées, mais l'interpréteur en ligne ne pourra pas exécuter les entrées où N> 3, en raison de contraintes de mémoire et de temps.
Mego
@Mego Je pensais juste que parce que cela n'a pas beaucoup de sens si vous n'avez pas k > 1, alors donné k <= N, si vous voulez ensuite garder N < 3, cela ne laisse pas beaucoup de choix pour les valeurs de Net kque vous pouvez essayer.
Neil
4

MATL , 16 octets

365:Z^!tXM=s>~Ym

La première entrée est N, la seconde est k.

Essayez-le en ligne!

Il s'agit d'une approche basée sur l'énumération, comme la réponse Jelly de Dennis , donc les nombres d'entrée doivent être réduits en raison des limitations de mémoire.

365:   % Vector [1 2 ... 365]
Z^     % Take N implicitly. Cartesian power. Gives a 2D array with each
       % "combination" on a row
!      % Transpose
t      % Duplicate
XM     % Mode (most frequent element) of each column
=      % Test for equality, element-wise with broadcast. For each column, gives
       % true for elements equal to that column's mode, false for the rest
s      % Sum of each column. Gives a row vector
>~     % Take k implicitly. True for elements equal or greater than k
Ym     % Mean of each column. Implicitly display
Luis Mendo
la source
2
Vous avez déjoué Dennis, bon travail.
m654
4
@ m654 Voyons voir quand il se réveille :-D
Luis Mendo
2
Eh bien, je me suis réveillé, mais le mieux que j'ai réussi a été une égalité. Jelly a vraiment besoin d'un atome méchant ...
Dennis
@Dennis Je pensais la même chose. Peut-être aussi un atome de mode ?
Luis Mendo
0

J, 41 36 octets

(+/%#)@(<:365&(#~>./@(#/.~)@#:i.@^))

Approche simple similaire aux autres. Exécute des problèmes de mémoire à n> 3 .

Usage

Prend la valeur de ksur le LHS et nsur le RHS.

   f =: (+/%#)@(<:365&(#~>./@(#/.~)@#:i.@^))
   0 f 0
0
   0 f 1
1
   1 f 1
1
   0 f 2
1
   1 f 2
1
   2 f 2
0.00273973
   0 f 3
1
   1 f 3
1
   2 f 3
0.00820417
   3 f 3
7.5061e_6

Sur mon PC, en utilisant un i7-4770k et le minuteur étranger 6!:2, le calcul pour n = 3 nécessite environ 25 secondes.

   timer =: 6!:2
   timer '2 f 3'
24.7893
   timer '3 f 3'
24.896

Explication

(+/%#)@(<:365&(#~>./@(#/.~)@#:i.@^)) Input: k on LHS, n on RHS
          365&                       The number 365
               #~                    Create n copies of 365
                                 ^   Calculate 365^n
                              i.@    The range [0, 1, ..., 365^n-1]
                            #:       Convert each value in the range to base-n and pad
                                     with zeroes to the right so that each has n digits
                     (#/.~)@         Find the size of each set of identical values
                 >./@                Find the max size of each
        <:                           Test each if greater than or equal to k
(+/%#)@                              Apply to the previous result
 +/                                  Find the sum of the values
    #                                Count the number of values
   %                                 Divide the sum by the count and return
miles
la source