Birthday problem: Difference between revisions

{{Wikipedia pre 15 June 2009|pagename=Birthday Problem|lang=en|oldid=296054030|timedate=21:44, 12 June 2009}}

{{draft task}}

 

 

* Wolfram entry:   {{Wolfram|Birthday|Problem}}

<br><br>

=={{header|11l}}==

{{trans|D}}

 

V eq = 0

L 0 .< rep

group_est = gs

print(‘#. independent people in a group of #. share a common birthday. (#3.1)’.format(sharers, gs, eq))

 

{{out}}

5 independent people in a group of 313 share a common birthday. ( 50.4)

</pre>

=={{header|Ada}}==

 

This solution assumes a 4-year cycle, with three 365-day years and one leap year.

 

 

procedure Birthday_Test is

" persons sharing a common birthday.");

end loop;

 

{{out}}

An interesting observation:

The probability for groups of 313 persons having 5 persons sharing a common birthday is almost exactly 0.5. Note that a solution based on 365-day years, i.e., a solution ignoring leap days, would generate slightly but significantly larger probabilities.

=={{header|ALGOL 68}}==

{{works with|ALGOL 68|Revision 1}}

{{works with|ALGOL 68G|Any - tested with release [http://sourceforge.net/projects/algol68/files/algol68g/algol68g-2.6 algol68g-2.6].}}

{{wont work with|ELLA ALGOL 68|Any (with appropriate job cards) - tested with release [http://sourceforge.net/projects/algol68/files/algol68toc/algol68toc-1.8.8d/algol68toc-1.8-8d.fc9.i386.rpm/download 1.8-8d] - due to extensive use of '''format'''[ted] ''transput''.}}

# -*- coding: utf-8 -*- #

 

required common +:= 1

FI

<pre>

upb year: 365.2500; upb common: 5; upb sample size: 100000;

required common: 5; group size: 314; %age of years with required common birthdays: 50.66%;

</pre>

=={{header|C}}==

Computing probabilities to 5 sigmas of confidence. It's very slow, chiefly because to make sure a probability like 0.5006 is indeed above .5 instead of just statistical fluctuation, you have to run the simulation millions of times.

#include <stdlib.h>

#include <string.h>

 

return 0;

{{out}}

<pre>

5 collision: 313 people, P = 0.500641 +/- 0.000128174

</pre>

=={{header|C++}}==

{{trans|Java}}

#include <random>

#include <vector>

 

return 0;

{{out}}

<pre>2 independant people in a group of 23 share a common birthday. ( 50.6)

4 independant people in a group of 186 share a common birthday. ( 50.0)

5 independant people in a group of 313 share a common birthday. ( 50.5)</pre>

=={{header|D}}==

{{trans|Python}}

 

/// For sharing common birthday must all share same common day.

}

}

{{out}}

<pre>2 independent people in a group of 23 share a common birthday. ( 50.5)

Alternative version:

{{trans|C}}

 

enum nDays = 365;

writefln("%d collision: %d people, P = %g +/- %g", nCollisions, np, p, d);

}

{{out}}

<pre>2 collision: 23 people, P = 0.521934 +/- 0.00728933

{{libheader| System.SysUtils}}

{{Trans|C}}

program Birthday_problem;

 

writeln('Press enter to exit');

readln;

{{out}}

<pre>Wait for calculate

5 collision: 313 people, P = 0,50093354 +/- 0,00031116

Press enter to exit</pre>

 

=={{header|Go}}==

{{trans|C}}

 

import (

n, np, p, d)

}

<pre>

2 collision: 23 people, P = 0.5081 ± 0.0016

</pre>

'''Also based on the C version:'''

 

import (

}

return

{{Out}}

<pre>

5 collision: 313 people, P = 0.5011 ± 0.0002

</pre>

=={{header|Hy}}==

 

We use a simple but not very accurate simulation method.

 

[numpy :as np]

[random [randint]])

(print (birthday 3))

(print (birthday 4))

=={{header|J}}==

 

Quicky approach (use a population of 1e5 people to get a quick estimate and then refine against a population of 1e8 people):

 

PopBig=: 1e8 ?@# 365

 

assert. (2+y) > |approx-refine

refine, refine PopBig probShared y

 

Task cases:

 

23 0.507254

estGroupSz 3

187 0.502878

estGroupSz 5

 

So, for example, we need a group of 88 to have at least a 50% chance of 3 people in the group having the same birthday in a year of 365 days. And, in that case, the simulated probability was 51.0737%

=={{header|Java}}==

Translation of [[Birthday_problem#Python|Python]] via [[Birthday_problem#D|D]]

{{works with|Java|8}}

import java.util.Random;

 

}

}

 

<pre>2 independent people in a group of 23 share a common birthday. ( 50,6)

4 independent people in a group of 187 share a common birthday. ( 50,1)

5 independent people in a group of 314 share a common birthday. ( 50,2)</pre>

=={{header|Julia}}==

{{works with|Julia|0.6}}

{{trans|Python}}

 

eq = 0

for _ in 1:nrep

push!(gsizes, gsize)

@printf("%i independent people in a group of %s share a common birthday. (%5.3f)\n", sh, gsize, freq)

 

{{out}}

4 independent people in a group of 187 share a common birthday. (0.500)

5 independent people in a group of 314 share a common birthday. (0.507)</pre>

=={{header|Kotlin}}==

{{trans|Java}}

 

import java.util.Random

}

}

 

{{out}}

5 independent people in a group of 314 share a common birthday (50.2%)

</pre>

=={{header|Lasso}}==

define randomgen(len::integer,max::integer)::array => {

#len <= 0 ? return

'Threshold: '+#threshold+', qty: '+#qty+' - probability: '+#probability+'\r'

#qty += 1

 

{{out}}

Threshold: 5, qty: 314 - probability: 50.000000

</pre>

=={{header|Nim}}==

{{trans|Kotlin}}

 

proc equalBirthdays(nSharers, groupSize, nRepetitions: int): float =

break

 

 

{{out}}

4 independent people in a group of 187 share a common birthday (50.2%)

5 independent people in a group of 313 share a common birthday (50.2%)</pre>

=={{header|PARI/GP}}==

find(n)=my(guess=365*n-342,t);while(1, t=sum(i=1,1e3,simulate(guess)>=n)/1e3; if(t>550, guess--); if(t<450, guess++); if(450<=t && t<=550, return(guess)))

find(2)

find(3)

find(4)

=={{header|Perl}}==

{{trans|Raku}}

use warnings;

use List::AllUtils qw(max min uniqnum count_by any);

}

 

{{out}}

<pre>2 people in a group of 23 share a common birthday. (0.5083)

4 people in a group of 187 share a common birthday. (0.5034)

5 people in a group of 313 share a common birthday. (0.5008)</pre>

=={{header|Phix}}==

{{trans|D}}

<span style="color: #008080;">constant</span> <span style="color: #000000;">nDays</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">365</span>

<span style="color: #7060A8;">printf</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"%d collision: %d people, P = %g +/- %g\n"</span><span style="color: #0000FF;">,</span> <span style="color: #0000FF;">{</span><span style="color: #000000;">nCollisions</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">np</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">p</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">d</span><span style="color: #0000FF;">})</span>

<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>

{{out}}

<pre>

6 collision: 460 people, P = 0.502901 +/- 0.000580137

</pre>

=={{header|PL/I}}==

bd: Proc Options(main);

/*--------------------------------------------------------------------

End;

End;

Output:

<pre>

1182 496957 503043 50.304% <-

1183 494414 505586 50.559% <-</pre>

=={{header|Python}}==

Note: the first (unused), version of function equal_birthdays() uses a different but equally valid interpretation of the phrase "common birthday".

from random import randint

 

break

group_est.append(groupsize)

 

{{out}}

===Enumeration method===

The following enumerates all birthday distributation of n people in a year. It's patentedly unscalable.

days = 365

 

n, good, combos = find_half(x)

print "%d of %d people sharing birthday: %d out of %d combos"% (x, n, good, combos)

{{out}}

<pre>2 of 23 people sharing birthday: 43450860051057961364418604769486195435604861663267741453125 out of 85651679353150321236814267844395152689354622364044189453125 combos

</pre>

===Enumeration method #2===

# factorial

def fact(n, cache={0:1}):

return

 

{{out}}

<pre>

313 of 5 people: 498385488882289...2578125/99464149835930...2578125 combos

</pre>

=={{header|Racket}}==

{{trans|Python}}Based on the Python task. For three digits precision use 250000 repetitions. For four digits precision use 25000000 repetitions, but it’s very slow. See discussion page.

 

#;(define repetitions 25000000) ; for \sigma=1/10000

(search-from sharers (search-coarse-group-size sharers))])

(printf "~a independent people in a group of ~a share a common birthday. (~a%)\n"

'''Output'''

<pre>2 independent people in a group of 23 share a common birthday. (50.80%)

5 independent people in a group of 313 share a common birthday. (50.17%)

</pre>

=={{header|Raku}}==

(formerly Perl 6)

Gives correct answers, but more of a proof-of-concept at this point, even with max-trials at 250K it is too slow to be practical.

my $max-trials = 250_000;

my $min-trials = 5_000;

}

 

{{out}}

<pre>2 people in a group of 23 share a common birthday. (0.506)

4 people in a group of 187 share a common birthday. (0.500)

5 people in a group of 313 share a common birthday. (0.507)</pre>

=={{header|REXX}}==

===version 1===

 

This REXX version doesn't need a precalculated group size to find the percentage required to exceed 50%.

parse arg dups samp seed . /*get optional arguments from the CL. */

if dups=='' | dups=="," then dups= 10 /*Not specified? Then use the default.*/

end /*try=start.g*/ /* [↑] where the try─outs happen. */

say right(g, 15) right(try, 15) center( format( s / samp * 100, , 4)'%', 30)

{{out|output|text= &nbsp; when using the default inputs:}}

<pre>

 

===version 2===

* 04.11.2013 Walter Pachl translated from PL/I

* Take samp samples of groups with gs persons and check

Say format(gs,10) cnt.0 cnt.1 100*hits||'%'||arrow

End

Output:

<pre>

461 49316 50684 50.68400% <-

462 49121 50879 50.87900% <-</pre>

=={{header|Ruby}}==

{{trans|Java}}

eq = 0

 

end

 

{{out}}

<pre>2 independant people in a group of 23 share a common birthday. ( 50.5)

4 independant people in a group of 187 share a common birthday. ( 50.3)

5 independant people in a group of 313 share a common birthday. ( 50.3)</pre>

 

=={{header|SQL}}==

birthday.sql

with

c as

from sol where rownum = 1

;

 

SQL> @ birthday.sql

----------

23

=={{header|Tcl}}==

for {set i 0} {$i < $num} {incr i} {

set b [expr {int(rand() * 365)}]

}

}

{{out}}

<pre>

level found: 315 people

</pre>

=={{header|Wren}}==

{{trans|Kotlin}}

{{libheader|Wren-fmt}}

 

var equalBirthdays = Fn.new { |nSharers, groupSize, nRepetitions|

}

}

 

{{out}}

 

=={{header|XPL0}}==

\Simulate birthdays and return number of people to have N same days

int N, I, People, R;

IntOut(0, N); Text(0, ": "); IntOut(0, Sum/10000); CrLf(0);

];

 

{{out}}

5: 311

</pre>

=={{header|zkl}}==

Pure simulation; adding a person to a population until there are the required number of collisions, then repeating that a bunch of times to get an average.

year:=(0).pump(365,List.createLong(365).write,0); // 365 days == one year

shared:=people:=0; do{ // add a new person to population

println("Average of %d people in a populatation of %s share birthdays"

.fmt(n,simulate(n,0d10_000)));

{{out}}

<pre>