Problema generalizado de aniversário

Hoje à noite, minha noiva me levou para jantar para comemorar meu aniversário. Enquanto estávamos fora, ouvi Parabéns a você cantando para 5 convidados diferentes (inclusive eu), em um restaurante cheio de 50 pessoas. Isso me fez pensar - o problema original do aniversário (encontrar a probabilidade de duas pessoas em uma sala Ncompartilharem o mesmo aniversário) é muito simples e direto. Mas o que sobre como calcular a probabilidade de que pelo menos kas pessoas fora de Npessoas compartilham o mesmo aniversário?

Caso você esteja se perguntando, a probabilidade de pelo menos 5 em cada 50 pessoas compartilhar o mesmo aniversário é de cerca de 1/10000.

O desafio

Dado dois números inteiros Ne k, onde N >= k > 0, gera a probabilidade de que pelo menos kpessoas em um grupo Ncompartilhem o mesmo aniversário. Para simplificar, suponha que sempre haja 365 aniversários possíveis e que todos os dias sejam igualmente prováveis.

Pois k = 2, isso se resume ao problema original de aniversário e a probabilidade é 1 - P(365, N)/(365)**N(onde P(n,k)é o número de permutações de comprimento k formadas a partir de n elementos ). Para valores maiores de k, este artigo Wolfram MathWorld pode ser útil.

Regras

A saída deve ser determinística e o mais precisa possível para o idioma escolhido. Isso significa que não há estimativa de Monte Carlo ou aproximação de Poisson.
Ne knão será maior que o maior número inteiro representável no idioma escolhido. Se o idioma escolhido não tem máxima duro em números inteiros (com exceção de restrições de memória), em seguida, Ne kpode ser arbitrariamente grande.
Erros de precisão decorrentes de imprecisões de ponto flutuante podem ser ignorados - sua solução deve assumir flutuações perfeitamente exatas e infinitas.

Casos de teste

Formato: 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
fonte

Feliz aniversário atrasado)!

Luis Mendo

Talvez adicione alguns casos de teste para números pequenos?

Luis Mendo

@LuisMendo vou acrescentar um pouco mais depois que eu conseguir algumas horas de sono :)

Mego

Vale a pena notar que a probabilidade de as pessoas comerem em um restaurante provavelmente não é independente do aniversário, portanto, a probabilidade de cinco aniversários entre 50 pessoas é provavelmente maior do que a lógica do Problema do aniversário sugere.

Glen O

@GlenO Bom ponto!

Luis Mendo

Respostas:

Geléia , 17 16 bytes

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

Extremamente ineficiente. Experimente online! (mas mantenha N abaixo de 3 )

Como funciona

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
fonte

"mantenha N abaixo de 3" ... isso não é excessivamente restritivo?

Neil

@ Nee A solução é válida para todas as entradas, mas o intérprete on-line não poderá executar entradas onde N> 3, devido a restrições de memória e tempo.

Mego 10/06

@Mego Eu estava pensando que, porque não faz muito sentido se você não tem k > 1, então dado k <= N, se você deseja manter N < 3, isso não deixa muita escolha para os valores Ne kque você pode tentar.

21416 Neil

MATL , 16 bytes

365:Z^!tXM=s>~Ym

A primeira entrada é N, a segunda é k.

Experimente online!

Esta é uma abordagem baseada em enumeração, como a resposta de Dennis 'Jelly , portanto os números de entrada devem ser mantidos pequenos devido a limitações de memória.

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
fonte

Você superou Dennis, bom trabalho.

M654

@ de m654 Vamos ver quando ele acorda :-D

Luis Mendo

Bem, eu acordei, mas o melhor que consegui foi um empate. Jelly realmente precisa de uma média átomo ...

Dennis

@ Dennis eu estava pensando o mesmo. Talvez um átomo de modo também?

Luis Mendo

J, 41 36 bytes

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

Abordagem direta semelhante aos outros. Executa problemas de memória em n> 3 .

Uso

Assume o valor de kno LHS e nno 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

No meu PC, usando um i7-4770k e o timer estrangeiro 6!:2, calcular n = 3 requer cerca de 25 segundos.

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

Explicação

(+/%#)@(<: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

milhas
fonte