Rosetta Code

Birthday problem: Difference between revisions

Page Discussion

Birthday problem (view source)

Revision as of 11:58, 20 January 2024

30,296 bytes added ,  3 months ago
Add Scala implementation
m (→‎version 1: added/changed comments and whitespace, used a template for the output section. optimized parts of the code.)
(Add Scala implementation)
 
(19 intermediate revisions by 12 users not shown)
Line 1:
{{Wikipedia pre 15 June 2009|pagename=Birthday Problem|lang=en|oldid=296054030|timedate=21:44, 12 June 2009}}
{{draft task}}
[[Category:Probability and statistics]]
[[Category:Discrete math]]
{{Wikipedia pre 15 June 2009|pagename=Birthday Problem|lang=en|oldid=296054030|timedate=21:44, 12 June 2009}}
{{draft task}}
 
 
Line 9:
 
;Task
Using simulation, estimate the number of independent people required in a groupsgroup before we can expect a ''better than even chance'' that at least 2 independent people in a group share a common birthday. Furthermore: Simulate and thus estimate when we can expect a ''better than even chance'' that at least 3, 4 & 5 independent people of the group share a common birthday. For simplicity assume that all of the people are alive...
 
 
Line 21:
* Wolfram entry:   {{Wolfram|Birthday|Problem}}
<br><br>
=={{header|11l}}==
{{trans|D}}
 
<syntaxhighlight lang="11l">F equal_birthdays(sharers, groupsize, rep)
V eq = 0
L 0 .< rep
V group = [0] * 365
L 0 .< groupsize
group[random:(group.len)]++
I any(group.map(c -> c >= @sharers))
eq++
R (eq * 100.) / rep
 
V group_est = 2
L(sharers) 2..5
V groupsize = group_est + 1
L equal_birthdays(sharers, groupsize, 100) < 50.
groupsize++
 
L(gs) Int(groupsize - (groupsize - group_est) / 4.) .< groupsize + 999
V eq = equal_birthdays(sharers, gs, 250)
I eq > 50.
groupsize = gs
L.break
 
L(gs) groupsize - 1 .< groupsize + 999
V eq = equal_birthdays(sharers, gs, 50'000)
I eq > 50.
group_est = gs
print(‘#. independent people in a group of #. share a common birthday. (#3.1)’.format(sharers, gs, eq))
L.break</syntaxhighlight>
 
{{out}}
<pre>
2 independent people in a group of 23 share a common birthday. ( 50.6)
3 independent people in a group of 87 share a common birthday. ( 50.1)
4 independent people in a group of 187 share a common birthday. ( 50.5)
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.
 
<langsyntaxhighlight Adalang="ada">with Ada.Command_Line, Ada.Text_IO, Ada.Numerics.Discrete_random;
 
procedure Birthday_Test is
Line 98 ⟶ 136:
" persons sharing a common birthday.");
end loop;
end Birthday_Test;</langsyntaxhighlight>
 
{{out}}
Line 119 ⟶ 157:
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''.}}
'''File: Birthday_problem.a68'''<langsyntaxhighlight lang="algol68">#!/usr/bin/a68g --script #
# -*- coding: utf-8 -*- #
 
Line 188 ⟶ 225:
required common +:= 1
FI
OD # group size #</langsyntaxhighlight>'''Output:'''
<pre>
upb year: 365.2500; upb common: 5; upb sample size: 100000;
Line 202 ⟶ 239:
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.
<langsyntaxhighlight lang="c">#include <stdio.h>
#include <stdlib.h>
#include <string.h>
Line 300 ⟶ 336:
 
return 0;
}</langsyntaxhighlight>
{{out}}
<pre>
Line 308 ⟶ 344:
5 collision: 313 people, P = 0.500641 +/- 0.000128174
</pre>
=={{header|C++}}==
{{trans|Java}}
<syntaxhighlight lang="cpp">#include <iostream>
#include <random>
#include <vector>
 
double equalBirthdays(int nSharers, int groupSize, int nRepetitions) {
std::default_random_engine generator;
std::uniform_int_distribution<int> distribution(0, 364);
std::vector<int> group(365);
 
int eq = 0;
for (int i = 0; i < nRepetitions; i++) {
std::fill(group.begin(), group.end(), 0);
for (int j = 0; j < groupSize; j++) {
int day = distribution(generator);
group[day]++;
}
if (std::any_of(group.cbegin(), group.cend(), [nSharers](int c) { return c >= nSharers; })) {
eq++;
}
}
 
return (100.0 * eq) / nRepetitions;
}
 
int main() {
int groupEst = 2;
 
for (int sharers = 2; sharers < 6; sharers++) {
// Coarse
int groupSize = groupEst + 1;
while (equalBirthdays(sharers, groupSize, 100) < 50.0) {
groupSize++;
}
 
// Finer
int inf = (int)(groupSize - (groupSize - groupEst) / 4.0f);
for (int gs = inf; gs < groupSize + 999; gs++) {
double eq = equalBirthdays(sharers, groupSize, 250);
if (eq > 50.0) {
groupSize = gs;
break;
}
}
 
// Finest
for (int gs = groupSize - 1; gs < groupSize + 999; gs++) {
double eq = equalBirthdays(sharers, gs, 50000);
if (eq > 50.0) {
groupEst = gs;
printf("%d independant people in a group of %d share a common birthday. (%5.1f)\n", sharers, gs, eq);
break;
}
}
}
 
return 0;
}</syntaxhighlight>
{{out}}
<pre>2 independant people in a group of 23 share a common birthday. ( 50.6)
3 independant people in a group of 87 share a common birthday. ( 50.2)
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}}
<langsyntaxhighlight lang="d">import std.stdio, std.random, std.algorithm, std.conv;
 
/// For sharing common birthday must all share same common day.
Line 359 ⟶ 458:
}
}
}</langsyntaxhighlight>
{{out}}
<pre>2 independent people in a group of 23 share a common birthday. ( 50.5)
Line 369 ⟶ 468:
Alternative version:
{{trans|C}}
<langsyntaxhighlight lang="d">import std.stdio, std.random, std.math;
 
enum nDays = 365;
Line 454 ⟶ 553:
writefln("%d collision: %d people, P = %g +/- %g", nCollisions, np, p, d);
}
}</langsyntaxhighlight>
{{out}}
<pre>2 collision: 23 people, P = 0.521934 +/- 0.00728933
Line 466 ⟶ 565:
4 collision: 187 people, P = 0.503229 +/- 0.000645587
5 collision: 313 people, P = 0.501105 +/- 0.000221016</pre>
=={{header|Delphi}}==
{{libheader| System.SysUtils}}
{{Trans|C}}
<syntaxhighlight lang="delphi">
program Birthday_problem;
 
{$APPTYPE CONSOLE}
 
uses
System.SysUtils;
 
const
_DAYS = 365;
 
var
days: array[0..(_DAYS) - 1] of Integer;
runs: Integer;
 
function rand_day: Integer; inline;
begin
Result := random(_DAYS);
end;
 
/// <summary>
/// given p people, if n of them have same birthday in one run
/// </summary>
function simulate1(p, n: Integer): Integer;
var
index, i: Integer;
begin
for i := 0 to High(days) do
begin
days[i] := 0;
end;
 
for i := 0 to p - 1 do
begin
index := rand_day();
inc(days[index]);
if days[index] = n then
Exit(1);
end;
Exit(0);
end;
 
/// <summary>
/// decide if the probability of n out of np people sharing a birthday
/// is above or below p_thresh, with n_sigmas sigmas confidence
/// note that if p_thresh is very low or hi, minimum runs need to be much higher
/// </summary>
function prob(np, n: Integer; n_sigmas, p_thresh: Double; var d: Double): Double;
var
p: Double;
runs, yes: Integer;
begin
runs := 0;
yes := 0;
 
repeat
yes := yes + (simulate1(np, n));
inc(runs);
p := yes / runs;
d := sqrt(p * (1 - p) / runs);
until ((runs >= 10) and (abs(p - p_thresh) >= (n_sigmas * d)));
 
Exit(p);
end;
 
/// <summary>
/// bisect for truth
/// </summary>
function find_half_chance(n: Integer; var p: Double; var d: Double): Integer;
var
lo, hi, mid: Integer;
label
reset;
begin
reset:
lo := 0;
hi := _DAYS * (n - 1) + 1;
repeat
mid := (hi + lo) div 2;
 
p := prob(mid, n, 3, 0.5, d);
if p < 0.5 then
lo := mid + 1
else
hi := mid;
if hi < lo then
goto reset;
 
until ((lo >= mid) and (p >= 0.5));
Exit(mid);
end;
 
var
n, np: Integer;
p, d: Double;
begin
Randomize;
writeln('Wait for calculate');
for n := 2 to 5 do
begin
np := find_half_chance(n, p, d);
writeln(format('%d collision: %d people, P = %.8f +/- %.8f', [n, np, p, d]));
end;
writeln('Press enter to exit');
readln;
end.</syntaxhighlight>
{{out}}
<pre>Wait for calculate
2 collision: 23 people, P = 0,50411600 +/- 0,00137151
3 collision: 88 people, P = 0,51060651 +/- 0,00352751
4 collision: 188 people, P = 0,50856493 +/- 0,00285022
5 collision: 313 people, P = 0,50093354 +/- 0,00031116
Press enter to exit</pre>
=={{header|FreeBASIC}}==
{{trans|XPL0}}
<syntaxhighlight lang="freebasic">Function Simulacion(N As Integer) As Integer
Dim As Integer i, dias(365)
For i = 0 To 365-1
dias(i) = 0
Next i
Dim As Integer R, personas = 0
Do
R = Rnd * 365
dias(R) += 1
personas += 1
If dias(R) = N Then Return personas
Loop
End Function
 
Dim As Integer N, grupo, t
For N = 2 To 5
grupo = 0
For t = 1 To 10000
grupo += Simulacion(N)
Next t
Print Using "Average of # people in a population of ### share birthdays"; N; Int(grupo/10000)
Next N
Sleep</syntaxhighlight>
=={{header|Go}}==
{{trans|C}}
Based on the C version but multithreaded using Go channels
<langsyntaxhighlight lang="go">package main
 
import (
"fmt"
"math"
"math/rand"
"time"
)
 
const (
DEBUG = 0
DAYS = 365
n_sigmas = 5.
WORKERS = 16 // concurrent worker processes
RUNS = 1000 // runs per flight
)
 
func simulate1(p, n int, r *rand.Rand) int {
var days [DAYS]int
for i := 0; i < p; i++ {
days[r.Intn(DAYS)]++
}
for _, d := range days {
if d >= n {
return 1
}
}
return 0
}
 
// send yes's per fixed number of simulate1 runs until canceled
func work(p, n int, ych chan int, cancel chan bool) {
r := rand.New(rand.NewSource(time.Now().Unix() + rand.Int63()))
for {
select {
case <-cancel:
return
default:
}
y := 0
for i := 0; i < RUNS; i++ {
y += simulate1(p, n, r)
}
ych <- y
}
}
 
func prob(np, n int) (p, d float64) {
ych := make(chan int, WORKERS)
cancel := make(chan bool)
for i := 0; i < WORKERS; i++ {
go work(np, n, ych, cancel)
}
var runs, yes int
for {
yes += <-ych
runs += RUNS
fr := float64(runs)
p = float64(yes) / fr
d = math.Sqrt(p * (1 - p) / fr)
if DEBUG > 1 {
fmt.Println("\t\t", np, yes, runs, p, d)
}
// .5 here is the "even chance" threshold
if !(math.Abs(p-.5) < n_sigmas*d) {
close(cancel)
break
}
}
if DEBUG > 1 {
fmt.Println()
}
return
}
 
func find_half_chance(n int) (mid int, p, dev float64) {
reset:
lo := 0
hi := DAYS*(n-1) + 1
for {
mid = (hi + lo) / 2
p, dev = prob(mid, n)
 
if DEBUG > 0 {
fmt.Println("\t", lo, mid, hi, p, dev)
}
if p < .5 {
lo = mid + 1
} else {
hi = mid
}
if hi < lo {
if DEBUG > 0 {
fmt.Println("\tMade a mess, will redo.")
}
goto reset
}
if !(lo < mid || p < .5) {
break
}
}
return
}
 
func main() {
for n := 2; n <= 5; n++ {
np, p, d := find_half_chance(n)
fmt.Printf("%d collision: %d people, P = %.4f ± %.4f\n",
n, np, p, d)
}
}</syntaxhighlight>
<pre>
2 collision: 23 people, P = 0.5081 ± 0.0016
3 collision: 88 people, P = 0.5155 ± 0.0029
4 collision: 187 people, P = 0.5041 ± 0.0008
5 collision: 313 people, P = 0.5015 ± 0.0003
</pre>
'''Also based on the C version:'''
<syntaxhighlight lang="go">package main
 
import (
"math/rand"
"fmt"
"time"
"math"
"math/rand"
"runtime"
"time"
)
 
type ProbeRes struct {
np int
p, d float64
}
 
type Frac struct {
n int
d int
}
 
var DaysInYear int = 365
 
func main() {
sigma := 5.0
for i := 2; i <= 5; i++ {
res, dur := GetNP(i, sigma, 0.5)
fmt.Printf("%d collision: %d people, P = %f.4f +/-± %f, took %s.4f\n",i,res.np,res.p,res.d,dur)
i, res.np, res.p, res.d)
}
}
 
func GetNP(n int, n_sigmas, p_thresh float64) (res ProbeRes,) dur time.Duration){
res.np = DaysInYear * (n - 1)
start := time.Now()
res.npfor i := 0; i < DaysInYear*(n-1); i++ {
tmp := probe(i, n, n_sigmas, p_thresh)
for i := 0; i < DaysInYear * (n-1);i++ {
if tmp.p :=> probe(i,n,n_sigmas,p_thresh) && tmp.np < res.np {
if tmp.p > p_thresh && tmp.np < res.np{
res = tmp
}
}
dur = time.Since(start)
return
}
 
func probe(np,n int, n_sigmas, p_thresh float64) ProbeRes{
var numCPU = runtime.NumCPU()
var p,d float64
 
func probe(np, n int, n_sigmas, p_thresh float64) ProbeRes {
var p, d float64
var runs, yes int
cRes := make(chan Frac,runtime.NumCPU() numCPU)
for i := 0; i < runtime.NumCPU()numCPU; i++ {
go SimN(np, n, 25, cRes)
}
for math.Abs(p - p_thresh) < n_sigmas * d || runs < 100 {
f := <-cRes
yes += f.n
Line 521 ⟶ 884:
p = float64(yes) / float64(runs)
d = math.Sqrt(p * (1 - p) / float64(runs))
go SimN(np, n, runs/3, cRes)
 
}
return ProbeRes{np, p, d}
}
func SimN(np, n, ssize int, c chan Frac) {
r := rand.New(rand.NewSource(time.Now().UnixNano() + rand.Int63()))
yes := 0
for i := 0; i < ssize; i++ {
if Sim(np, n, r) {
yes++
}
 
}
c <- Frac{yes, ssize}
}
func Sim(p, n int, r *rand.Rand) ( res bool) {
Cal := make([]int, DaysInYear)
for i := 0; i < p ; i++ {
Cal[randr.Intn(DaysInYear)]++
}
for _, v := range Cal {
if v >= n {
res = true
Line 547 ⟶ 911:
}
return
}</langsyntaxhighlight>
{{Out}}
<pre>
<pre>2 collision: 23 people, P = 0.506375 +/- 0.001197, took 1.5777555s
32 collision: 8823 people, P = 0.5160455068 +/-± 0.002945, took 2m17.5473911s0013
43 collision: 18788 people, P = 0.5026435148 +/-± 0.000507, took 1m11.1573736s0028
54 collision: 313187 people, P = 0.5019075020 +/-± 0.000367, took 1m49.7901966s</pre>0004
5 collision: 313 people, P = 0.5011 ± 0.0002
 
</pre>
=={{header|Hy}}==
 
We use a simple but not very accurate simulation method.
 
<langsyntaxhighlight lang="lisp">(import
[numpy :as np]
[random [randint]])
Line 587 ⟶ 952:
(print (birthday 3))
(print (birthday 4))
(print (birthday 5))</langsyntaxhighlight>
 
=={{header|J}}==
 
Quicky approach (use a population of 1e5 people to get a quick estimate and then refine against a population of 1e8 people):
 
<langsyntaxhighlight Jlang="j">PopSmall=: 1e5 ?@# 365
PopBig=: 1e8 ?@# 365
 
Line 613 ⟶ 977:
assert. (2+y) > |approx-refine
refine, refine PopBig probShared y
)</langsyntaxhighlight>
 
Task cases:
 
<langsyntaxhighlight Jlang="j"> estGroupSz 2
23 0.507254
estGroupSz 3
Line 624 ⟶ 988:
187 0.502878
estGroupSz 5
313 0.500903</langsyntaxhighlight>
 
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}}
<langsyntaxhighlight lang="java">import static java.util.Arrays.stream;
import java.util.Random;
 
Line 684 ⟶ 1,047:
}
}
}</langsyntaxhighlight>
 
<pre>2 independent people in a group of 23 share a common birthday. ( 50,6)
Line 690 ⟶ 1,053:
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}}
 
<langsyntaxhighlight lang="julia">function equalbirthdays(sharers::Int, groupsize::Int; nrep::Int = 10000)
eq = 0
for _ in 1:nrep
Line 733 ⟶ 1,095:
push!(gsizes, gsize)
@printf("%i independent people in a group of %s share a common birthday. (%5.3f)\n", sh, gsize, freq)
end</langsyntaxhighlight>
 
{{out}}
Line 740 ⟶ 1,102:
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}}
<langsyntaxhighlight lang="scala">// version 1.1.3
 
import java.util.Random
Line 788 ⟶ 1,149:
}
}
}</langsyntaxhighlight>
 
{{out}}
Line 798 ⟶ 1,159:
5 independent people in a group of 314 share a common birthday (50.2%)
</pre>
 
=={{header|Lasso}}==
<langsyntaxhighlight Lassolang="lasso">if(sys_listunboundmethods !>> 'randomgen') => {
define randomgen(len::integer,max::integer)::array => {
#len <= 0 ? return
Line 829 ⟶ 1,189:
'Threshold: '+#threshold+', qty: '+#qty+' - probability: '+#probability+'\r'
#qty += 1
^}</langsyntaxhighlight>
 
{{out}}
Line 853 ⟶ 1,213:
Threshold: 5, qty: 314 - probability: 50.000000
</pre>
=={{header|Nim}}==
{{trans|Kotlin}}
<syntaxhighlight lang="nim">import random, sequtils, strformat
 
proc equalBirthdays(nSharers, groupSize, nRepetitions: int): float =
randomize(1)
var eq = 0
for _ in 1..nRepetitions:
var group: array[1..365, int]
for _ in 1..groupSize:
inc group[rand(1..group.len)]
eq += ord(group.anyIt(it >= nSharers))
result = eq * 100 / nRepetitions
 
proc main() =
 
var groupEst = 2
for sharers in 2..5:
 
# Coarse.
var groupSize = groupEst + 1
while equalBirthdays(sharers, groupSize, 100) < 50:
inc groupSize
 
# Finer.
let inf = (groupSize.toFloat - (groupSize - groupEst) / 4).toInt()
for gs in inf..(groupSize+998):
let eq = equalBirthdays(sharers, groupSize, 250)
if eq > 50:
groupSize = gs
break
 
# Finest.
for gs in (groupSize-1)..(groupSize+998):
let eq = equalBirthdays(sharers, gs, 50_000)
if eq > 50:
groupEst = gs
echo &"{sharers} independent people in a group of {gs:3} ",
&"share a common birthday ({eq:4.1f}%)"
break
 
main()</syntaxhighlight>
 
{{out}}
<pre>2 independent people in a group of 23 share a common birthday (50.7%)
3 independent people in a group of 87 share a common birthday (50.0%)
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}}==
<langsyntaxhighlight lang="parigp">simulate(n)=my(v=vecsort(vector(n,i,random(365))),t,c=1); for(i=2,n,if(v[i]>v[i-1],t=max(t,c);c=1,c++)); t
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)
find(5)</langsyntaxhighlight>
=={{header|Perl}}==
{{trans|Raku}}
<syntaxhighlight lang="perl">use strict;
use warnings;
use List::AllUtils qw(max min uniqnum count_by any);
use Math::Random qw(random_uniform_integer);
 
sub simulation {
my($c) = shift;
my $max_trials = 1_000_000;
my $min_trials = 10_000;
my $n = int 47 * ($c-1.5)**1.5; # OEIS/A050256: 16 86 185 307
my $N = min $max_trials, max $min_trials, 1000 * sqrt $n;
 
while (1) {
my $yes = 0;
for (1..$N) {
my %birthday_freq = count_by { $_ } random_uniform_integer($n, 1, 365);
$yes++ if any { $birthday_freq{$_} >= $c } keys %birthday_freq;
}
my $p = $yes/$N;
return($n, $p) if $p > 0.5;
$N = min $max_trials, max $min_trials, int 1000/(0.5-$p)**1.75;
$n++;
}
}
 
printf "$_ people in a group of %s share a common birthday. (%.4f)\n", simulation($_) for 2..5</syntaxhighlight>
{{out}}
<pre>2 people in a group of 23 share a common birthday. (0.5083)
3 people in a group of 88 share a common birthday. (0.5120)
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}}
<!--<syntaxhighlight lang="phix">(phixonline)[very/too slow]-->
<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: #000080;font-style:italic;">-- 5 sigma confidence. Conventionally people think 3 sigmas are
-- good enough, but for the case of 5 people sharing a birthday,
-- 3 sigmas actually sometimes gives a slightly wrong answer.</span>
<span style="color: #008080;">constant</span> <span style="color: #000000;">nSigmas</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">5.0</span><span style="color: #0000FF;">;</span> <span style="color: #000080;font-style:italic;">-- Change to 3 for smaller run time.</span>
<span style="color: #008080;">function</span> <span style="color: #000000;">simulate1</span><span style="color: #0000FF;">(</span><span style="color: #004080;">integer</span> <span style="color: #000000;">nPeople</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">nCollisions</span><span style="color: #0000FF;">)</span>
<span style="color: #000080;font-style:italic;">--
-- Given n people, if m of them have same birthday in one run.
--</span>
<span style="color: #004080;">sequence</span> <span style="color: #000000;">days</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">repeat</span><span style="color: #0000FF;">(</span><span style="color: #000000;">0</span><span style="color: #0000FF;">,</span><span style="color: #000000;">nDays</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">for</span> <span style="color: #000000;">p</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span> <span style="color: #008080;">to</span> <span style="color: #000000;">nPeople</span> <span style="color: #008080;">do</span>
<span style="color: #004080;">integer</span> <span style="color: #000000;">day</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">rand</span><span style="color: #0000FF;">(</span><span style="color: #000000;">nDays</span><span style="color: #0000FF;">)</span>
<span style="color: #000000;">days</span><span style="color: #0000FF;">[</span><span style="color: #000000;">day</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">+=</span> <span style="color: #000000;">1</span>
<span style="color: #008080;">if</span> <span style="color: #000000;">days</span><span style="color: #0000FF;">[</span><span style="color: #000000;">day</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">==</span> <span style="color: #000000;">nCollisions</span> <span style="color: #008080;">then</span>
<span style="color: #008080;">return</span> <span style="color: #004600;">true</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
<span style="color: #008080;">return</span> <span style="color: #004600;">false</span><span style="color: #0000FF;">;</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">function</span>
<span style="color: #008080;">function</span> <span style="color: #000000;">prob</span><span style="color: #0000FF;">(</span><span style="color: #004080;">integer</span> <span style="color: #000000;">np</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">nCollisions</span><span style="color: #0000FF;">,</span> <span style="color: #004080;">atom</span> <span style="color: #000000;">pThresh</span><span style="color: #0000FF;">)</span>
<span style="color: #000080;font-style:italic;">--
-- Decide if the probablity of n out of np people sharing a birthday
-- is above or below pThresh, with nSigmas sigmas confidence.
-- If pThresh is very low or hi, minimum runs need to be much higher.
--</span>
<span style="color: #004080;">atom</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: #000080;font-style:italic;">-- Probablity and standard deviation.</span>
<span style="color: #004080;">integer</span> <span style="color: #000000;">nRuns</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">0</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">yes</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">0</span><span style="color: #0000FF;">;</span>
<span style="color: #008080;">while</span> <span style="color: #000000;">nRuns</span><span style="color: #0000FF;"><</span><span style="color: #000000;">10</span> <span style="color: #008080;">or</span> <span style="color: #0000FF;">(</span><span style="color: #7060A8;">abs</span><span style="color: #0000FF;">(</span><span style="color: #000000;">p</span> <span style="color: #0000FF;">-</span> <span style="color: #000000;">pThresh</span><span style="color: #0000FF;">)</span> <span style="color: #0000FF;"><</span> <span style="color: #0000FF;">(</span><span style="color: #000000;">nSigmas</span> <span style="color: #0000FF;">*</span> <span style="color: #000000;">d</span><span style="color: #0000FF;">))</span> <span style="color: #008080;">do</span>
<span style="color: #000000;">yes</span> <span style="color: #0000FF;">+=</span> <span style="color: #000000;">simulate1</span><span style="color: #0000FF;">(</span><span style="color: #000000;">np</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">nCollisions</span><span style="color: #0000FF;">)</span>
<span style="color: #000000;">nRuns</span> <span style="color: #0000FF;">+=</span> <span style="color: #000000;">1</span>
<span style="color: #000000;">p</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">yes</span><span style="color: #0000FF;">/</span><span style="color: #000000;">nRuns</span>
<span style="color: #000000;">d</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">sqrt</span><span style="color: #0000FF;">(</span><span style="color: #000000;">p</span> <span style="color: #0000FF;">*</span> <span style="color: #0000FF;">(</span><span style="color: #000000;">1</span> <span style="color: #0000FF;">-</span> <span style="color: #000000;">p</span><span style="color: #0000FF;">)</span> <span style="color: #0000FF;">/</span> <span style="color: #000000;">nRuns</span><span style="color: #0000FF;">);</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">while</span>
<span style="color: #008080;">return</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;">function</span>
<span style="color: #008080;">function</span> <span style="color: #000000;">findHalfChance</span><span style="color: #0000FF;">(</span><span style="color: #004080;">integer</span> <span style="color: #000000;">nCollisions</span><span style="color: #0000FF;">)</span>
<span style="color: #000080;font-style:italic;">-- Bisect for truth.</span>
<span style="color: #004080;">atom</span> <span style="color: #000000;">p</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">dev</span>
<span style="color: #004080;">integer</span> <span style="color: #000000;">mid</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">1</span><span style="color: #0000FF;">,</span>
<span style="color: #000000;">lo</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">0</span><span style="color: #0000FF;">,</span>
<span style="color: #000000;">hi</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">nDays</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;">1</span><span style="color: #0000FF;">)</span> <span style="color: #0000FF;">+</span> <span style="color: #000000;">1</span><span style="color: #0000FF;">;</span>
<span style="color: #008080;">while</span> <span style="color: #000000;">lo</span> <span style="color: #0000FF;"><</span> <span style="color: #000000;">mid</span> <span style="color: #008080;">or</span> <span style="color: #000000;">p</span> <span style="color: #0000FF;"><</span> <span style="color: #000000;">0.5</span> <span style="color: #008080;">do</span>
<span style="color: #000000;">mid</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">floor</span><span style="color: #0000FF;">((</span><span style="color: #000000;">hi</span> <span style="color: #0000FF;">+</span> <span style="color: #000000;">lo</span><span style="color: #0000FF;">)</span> <span style="color: #0000FF;">/</span> <span style="color: #000000;">2</span><span style="color: #0000FF;">)</span>
<span style="color: #0000FF;">{</span><span style="color: #000000;">p</span><span style="color: #0000FF;">,</span><span style="color: #000000;">dev</span><span style="color: #0000FF;">}</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">prob</span><span style="color: #0000FF;">(</span><span style="color: #000000;">mid</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">nCollisions</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">0.5</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">if</span> <span style="color: #0000FF;">(</span><span style="color: #000000;">p</span> <span style="color: #0000FF;"><</span> <span style="color: #000000;">0.5</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">then</span>
<span style="color: #000000;">lo</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">mid</span> <span style="color: #0000FF;">+</span> <span style="color: #000000;">1</span><span style="color: #0000FF;">;</span>
<span style="color: #008080;">else</span>
<span style="color: #000000;">hi</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">mid</span><span style="color: #0000FF;">;</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #008080;">if</span> <span style="color: #0000FF;">(</span><span style="color: #000000;">hi</span> <span style="color: #0000FF;"><</span> <span style="color: #000000;">lo</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">then</span>
<span style="color: #008080;">return</span> <span style="color: #000000;">findHalfChance</span><span style="color: #0000FF;">(</span><span style="color: #000000;">nCollisions</span><span style="color: #0000FF;">)</span> <span style="color: #000080;font-style:italic;">-- reset</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">while</span>
<span style="color: #008080;">return</span> <span style="color: #0000FF;">{</span><span style="color: #000000;">p</span><span style="color: #0000FF;">,</span><span style="color: #000000;">dev</span><span style="color: #0000FF;">,</span><span style="color: #000000;">mid</span><span style="color: #0000FF;">}</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">function</span>
<span style="color: #008080;">for</span> <span style="color: #000000;">nCollisions</span><span style="color: #0000FF;">=</span><span style="color: #000000;">2</span> <span style="color: #008080;">to</span> <span style="color: #000000;">6</span> <span style="color: #008080;">do</span>
<span style="color: #004080;">atom</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: #000000;">np</span><span style="color: #0000FF;">}</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">findHalfChance</span><span style="color: #0000FF;">(</span><span style="color: #000000;">nCollisions</span><span style="color: #0000FF;">)</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>
<!--</syntaxhighlight>-->
{{out}}
<pre>
2 collision: 23 people, P = 0.520699 +/- 0.00688426
3 collision: 88 people, P = 0.507159 +/- 0.00238534
4 collision: 187 people, P = 0.504129 +/- 0.00137625
5 collision: 313 people, P = 0.501219 +/- 0.000406284
6 collision: 460 people, P = 0.502131 +/- 0.000710091
</pre>
Output with nSigmas = 5.0:
<pre>
2 collision: 23 people, P = 0.507817 +/- 0.00156278
3 collision: 88 people, P = 0.512042 +/- 0.00240772
4 collision: 187 people, P = 0.502546 +/- 0.000509275
5 collision: 313 people, P = 0.501218 +/- 0.000243516
6 collision: 460 people, P = 0.502901 +/- 0.000580137
</pre>
=={{header|PL/I}}==
<langsyntaxhighlight PLlang="pl/Ii">*process source attributes xref;
bd: Proc Options(main);
/*--------------------------------------------------------------------
Line 913 ⟶ 1,442:
End;
End;
End;</langsyntaxhighlight>
Output:
<pre>
Line 987 ⟶ 1,516:
1182 496957 503043 50.304% <-
1183 494414 505586 50.559% <-</pre>
 
=={{header|Perl 6}}==
{{incomplete|Perl 6}}
 
For a start, we can show off how to get the exact solution. If we pick n people, the total number of possible arrangements of birthdays is <tt>365<sup>n</sup></tt>. Among those possibilities, there are <tt>C<sup>n</sup><sub>365</sub></tt> where all birthdays are different. For each of these, there are <tt>n!</tt> possible ways to arrange the n people. So the solution is <tt>1 - n!C<sup>n</sup><sub>365</sub>/365<sup>n</sup></tt>, which in Perl 6 can be written:
 
<lang perl6>say "$_ :", 1 - combinations(365, $_)/365**$_ * [*] 1..$_ for ^365</lang>
{{out}}
<pre>0 : 0
1 : 0
2 : 0.002740
3 : 0.0082042
4 : 0.016355912
5 : 0.027135573700
6 : 0.04046248364911
7 : 0.0562357030959754
8 : 0.0743352923516690285
9 : 0.0946238338891667
^C</pre>
 
Now comparing with a simulation :
 
<lang perl6>sub theory($n) { 1 - combinations(365, $n)/365**$n* [*] 1..$n }
sub simulation(:number-of-people($n), :sample-size($N) = 1_000) {
$N R/ grep ?*, ((^365).roll($n).unique !== $n) xx $N;
}
 
for 2 .. 365 -> $n {
printf "%3d people, theory: %.4f, simulation: %.4f\n",
$n, theory($n), simulation(number-of-people => $n);
}</lang>
{{out}}
<pre> 2 people, theory: 0.0027, simulation: 0.0020
3 people, theory: 0.0082, simulation: 0.0080
4 people, theory: 0.0164, simulation: 0.0130
5 people, theory: 0.0271, simulation: 0.0260
6 people, theory: 0.0405, simulation: 0.0340
7 people, theory: 0.0562, simulation: 0.0590
8 people, theory: 0.0743, simulation: 0.0730
9 people, theory: 0.0946, simulation: 0.1080
10 people, theory: 0.1169, simulation: 0.1120
11 people, theory: 0.1411, simulation: 0.1220
12 people, theory: 0.1670, simulation: 0.1740
13 people, theory: 0.1944, simulation: 0.2200
14 people, theory: 0.2231, simulation: 0.2290
15 people, theory: 0.2529, simulation: 0.2540
16 people, theory: 0.2836, simulation: 0.2820
17 people, theory: 0.3150, simulation: 0.3190
18 people, theory: 0.3469, simulation: 0.3740
19 people, theory: 0.3791, simulation: 0.3720
20 people, theory: 0.4114, simulation: 0.3810
21 people, theory: 0.4437, simulation: 0.4340
22 people, theory: 0.4757, simulation: 0.4700
23 people, theory: 0.5073, simulation: 0.4960
24 people, theory: 0.5383, simulation: 0.5200
25 people, theory: 0.5687, simulation: 0.5990
26 people, theory: 0.5982, simulation: 0.5980
27 people, theory: 0.6269, simulation: 0.6520
28 people, theory: 0.6545, simulation: 0.6430
29 people, theory: 0.6810, simulation: 0.6690
30 people, theory: 0.7063, simulation: 0.7190
31 people, theory: 0.7305, simulation: 0.7450
^C</pre>
 
=={{header|Python}}==
Note: the first (unused), version of function equal_birthdays() uses a different but equally valid interpretation of the phrase "common birthday".
<langsyntaxhighlight lang="python">
from random import randint
 
Line 1,093 ⟶ 1,558:
break
group_est.append(groupsize)
print("%i independent people in a group of %s share a common birthday. (%5.1f)" % (sharers, groupsize, eq))</langsyntaxhighlight>
 
{{out}}
Line 1,103 ⟶ 1,568:
===Enumeration method===
The following enumerates all birthday distributation of n people in a year. It's patentedly unscalable.
<langsyntaxhighlight lang="python">from collections import defaultdict
days = 365
 
Line 1,143 ⟶ 1,608:
n, good, combos = find_half(x)
print "%d of %d people sharing birthday: %d out of %d combos"% (x, n, good, combos)
</syntaxhighlight>
</lang>
{{out}}
<pre>2 of 23 people sharing birthday: 43450860051057961364418604769486195435604861663267741453125 out of 85651679353150321236814267844395152689354622364044189453125 combos
Line 1,150 ⟶ 1,615:
</pre>
===Enumeration method #2===
<langsyntaxhighlight lang="python"># ought to use a memoize class for all this
# factorial
def fact(n, cache={0:1}):
Line 1,196 ⟶ 1,661:
return
 
for x in range(2, 6): find_half(x)</langsyntaxhighlight>
{{out}}
<pre>
Line 1,204 ⟶ 1,669:
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.
<langsyntaxhighlight Racketlang="racket">#lang racket
 
#;(define repetitions 25000000) ; for \sigma=1/10000
Line 1,255 ⟶ 1,719:
(search-from sharers (search-coarse-group-size sharers))])
(printf "~a independent people in a group of ~a share a common birthday. (~a%)\n"
sharers group-size (~r (* probability 100) #:precision '(= 2)))))</langsyntaxhighlight>
'''Output'''
<pre>2 independent people in a group of 23 share a common birthday. (50.80%)
Line 1,262 ⟶ 1,726:
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.
<syntaxhighlight lang="raku" line>sub simulation ($c) {
my $max-trials = 250_000;
my $min-trials = 5_000;
my $n = floor 47 * ($c-1.5)**1.5; # OEIS/A050256: 16 86 185 307
my $N = min $max-trials, max $min-trials, 1000 * sqrt $n;
 
loop {
my $p = $N R/ elems grep { .elems > 0 }, ((grep { $_>=$c }, values bag (^365).roll($n)) xx $N);
return($n, $p) if $p > 0.5;
$N = min $max-trials, max $min-trials, floor 1000/(0.5-$p);
$n++;
}
}
 
printf "$_ people in a group of %s share a common birthday. (%.3f)\n", simulation($_) for 2..5;</syntaxhighlight>
{{out}}
<pre>2 people in a group of 23 share a common birthday. (0.506)
3 people in a group of 88 share a common birthday. (0.511)
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===
The root finding method used is to find the average number of people to share a birthday, &nbsp; and then use the &nbsp; '''floor''' &nbsp; of that
<br>of that value &nbsp; (less the group size) &nbsp; as a starting point to find a new group size with an expected size that exceeds
<br>50% &nbsp; duplicate birthdays of the required size.
 
<lang rexx>/*REXX pgm examines the birthday problem via random # simulation (with specifable parms)*/
This REXX version doesn't need a precalculated group size to find the percentage required to exceed 50%.
<syntaxhighlight lang="rexx">/*REXX pgm examines the birthday problem via random# simulation (with specifiable parms)*/
parse arg dups samp seed . /*get optional arguments from the CL. */
if dups=='' | dups=="," then dups= 10 /*Not specified? Then use the default.*/
if samp=='' | samp=="," then samp= 10000 /* " " " " " " */
if datatype(seed, 'W') then call random ,,seed /*RANDOM seed given for repeatability ?*/
diy = 365 /*oralternative: diy=365.25 */ /*the number of Days In a Year. */
diyM= diy*100 /*this expands the RANDOM (BIF) range.*/
do g=2 to dups; s=0 0 /*perform through 2 ──► duplicate size*/
do samp; @.=0 0 /*perform some number of trials. */
do j=0 until @.day==g /*perform until G dup. birthdays found.*/
day= random(1, diyM) % 100 /*expand range RANDOM number generation*/
@.day= @.day + 1 /*record the number of common birthdays*/
end /*j*/ /* [↓] adjust for the DO loop index.*/
s=s s+ j /*add number of birthday hits to sum. */
end /*samp*/ /* [↓] % 1 rounds down the division.*/
start.g= s/samp % 1 - g /*define where the try─outs start. */
end /*g*/ /* [↑] get a rough estimate for %. */
say right('sample size is ' samp, 40); say /*display this run's sample size. */
say ' required trial % with required'
Line 1,290 ⟶ 1,778:
say ' ──────────── ─────── ──────────────────'
do g=2 to dups /*perform through 2 ──► duplicate size*/
do try=start.g until s/samp>=.5; s=0 0 /* " try─outs until average ≥ 50%.*/
do samp; @.=0 0 /* " some number of trials. */
do try; day= random(1, diyM) % 100 /* " until G dup. birthdays found.*/
@.day= @.day + 1 /*record the number of common birthdays*/
if @.day==g then do; s=s+1; leave; end /*found enough G (birthday) hits ? */
end /*try;*/
Line 1,299 ⟶ 1,787:
end /*try=start.g*/ /* [↑] where the try─outs happen. */
say right(g, 15) right(try, 15) center( format( s / samp * 100, , 4)'%', 30)
end /*g*/ /*stick a fork in it, we're all done. */</langsyntaxhighlight>
{{out|output|text= &nbsp; when using the default inputs:}}
<pre>
Line 1,319 ⟶ 1,807:
 
===version 2===
<langsyntaxhighlight lang="rexx"> /*--------------------------------------------------------------------
* 04.11.2013 Walter Pachl translated from PL/I
* Take samp samples of groups with gs persons and check
Line 1,350 ⟶ 1,838:
Say format(gs,10) cnt.0 cnt.1 100*hits||'%'||arrow
End
End</langsyntaxhighlight>
Output:
<pre>
Line 1,392 ⟶ 1,880:
461 49316 50684 50.68400% <-
462 49121 50879 50.87900% <-</pre>
=={{header|Ruby}}==
{{trans|Java}}
<syntaxhighlight lang="ruby">def equalBirthdays(nSharers, groupSize, nRepetitions)
eq = 0
 
for i in 1 .. nRepetitions
group = [0] * 365
for j in 1 .. groupSize
group[rand(group.length)] += 1
end
eq += group.any? { |n| n >= nSharers } ? 1 : 0
end
 
return (eq * 100.0) / nRepetitions
end
 
def main
groupEst = 2
for sharers in 2 .. 5
# Coarse
groupSize = groupEst + 1
while equalBirthdays(sharers, groupSize, 100) < 50.0
groupSize += 1
end
 
# Finer
inf = (groupSize - (groupSize - groupEst) / 4.0).floor
for gs in inf .. groupSize + 999
eq = equalBirthdays(sharers, groupSize, 250)
if eq > 50.0 then
groupSize = gs
break
end
end
 
# Finest
for gs in groupSize - 1 .. groupSize + 999
eq = equalBirthdays(sharers, gs, 50000)
if eq > 50.0 then
groupEst = gs
print "%d independant people in a group of %s share a common birthday. (%5.1f)\n" % [sharers, gs, eq]
break
end
end
end
end
 
main()</syntaxhighlight>
{{out}}
<pre>2 independant people in a group of 23 share a common birthday. ( 50.5)
3 independant people in a group of 90 share a common birthday. ( 53.3)
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|Scala}}==
{{trans|Java}}
<syntaxhighlight lang="Scala">
import scala.util.Random
import scala.util.control.Breaks._
 
object Test {
 
def equalBirthdays(
nSharers: Int,
groupSize: Int,
nRepetitions: Int
): Double = {
val rand = new Random(1)
var eq = 0
 
for (_ <- 1 to nRepetitions) {
val group = new Array[Int](365)
for (_ <- 1 to groupSize) {
val birthday = rand.nextInt(group.length)
group(birthday) += 1
}
if (group.exists(_ >= nSharers)) eq += 1
}
 
(eq * 100.0) / nRepetitions
}
 
def main(args: Array[String]): Unit = {
var groupEst = 2
 
for (sharers <- 2 until 6) {
// Coarse.
var groupSize = groupEst + 1
while (equalBirthdays(sharers, groupSize, 100) < 50.0)
groupSize += 1
 
// Finer.
val inf = (groupSize - (groupSize - groupEst) / 4.0).toInt
breakable({
for (gs <- inf until groupSize + 999) {
val eq = equalBirthdays(sharers, groupSize, 250)
if (eq > 50.0) {
groupSize = gs
break
}
}
})
 
// Finest.
breakable({
for (gs <- (groupSize - 1) until groupSize + 999) {
val eq = equalBirthdays(sharers, gs, 50000)
if (eq > 50.0) {
groupEst = gs
println(
f"$sharers independent people in a group of $gs share a common birthday. ($eq%5.1f)"
)
break
}
}
})
}
}
}
</syntaxhighlight>
{{out}}
<pre>
2 independent people in a group of 23 share a common birthday. ( 50.6)
3 independent people in a group of 87 share a common birthday. ( 50.4)
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|SQL}}==
birthday.sql
<syntaxhighlight lang="sql">
<lang SQL>
with
c as
Line 1,458 ⟶ 2,076:
from sol where rownum = 1
;
</syntaxhighlight>
</lang>
 
SQL> @ birthday.sql
Line 1,466 ⟶ 2,084:
----------
23
 
=={{header|Tcl}}==
<langsyntaxhighlight lang="tcl">proc birthdays {num {same 2}} {
for {set i 0} {$i < $num} {incr i} {
set b [expr {int(rand() * 365)}]
Line 1,501 ⟶ 2,118:
}
}
}</langsyntaxhighlight>
{{out}}
<pre>
Line 1,532 ⟶ 2,149:
level found: 315 people
</pre>
=={{header|Wren}}==
{{trans|Kotlin}}
{{libheader|Wren-fmt}}
<syntaxhighlight lang="wren">import "random" for Random
import "./fmt" for Fmt
 
var equalBirthdays = Fn.new { |nSharers, groupSize, nRepetitions|
var rand = Random.new(12345)
var eq = 0
for (i in 0...nRepetitions) {
var group = List.filled(365, 0)
for (j in 0...groupSize) {
var r = rand.int(group.count)
group[r] = group[r] + 1
}
eq = eq + (group.any { |i| i >= nSharers } ? 1 : 0)
}
return eq * 100 / nRepetitions
}
 
var groupEst = 2
for (sharers in 2..5) {
// Coarse
var groupSize = groupEst + 1
while (equalBirthdays.call(sharers, groupSize, 100) < 50) groupSize = groupSize + 1
 
// Finer
var inf = (groupSize - (groupSize - groupEst) / 4).floor
for (gs in inf...groupSize + 999) {
var eq = equalBirthdays.call(sharers, groupSize, 250)
if (eq > 50) {
groupSize = gs
break
}
}
 
// Finest
for (gs in groupSize - 1...groupSize + 999) {
var eq = equalBirthdays.call(sharers, gs, 50000)
if (eq > 50) {
groupEst = gs
Fmt.write("$d independent people in a group of $3d ", sharers, gs)
Fmt.print("share a common birthday $2.1f\%", eq)
break
}
}
}</syntaxhighlight>
 
{{out}}
<pre>
2 independent people in a group of 23 share a common birthday 51.0%
3 independent people in a group of 88 share a common birthday 51.0%
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.7%
</pre>
 
=={{header|XPL0}}==
<syntaxhighlight lang="xpl0">func Sim(N);
\Simulate birthdays and return number of people to have N same days
int N, I, People, R;
char Days(365);
[for I:= 0 to 365-1 do Days(I):= 0;
People:= 0;
loop [R:= Ran(365);
Days(R):= Days(R)+1;
People:= People+1;
if Days(R) = N then return People;
];
];
 
int N, Sum, Trial;
[for N:= 2 to 5 do
[Sum:= 0;
for Trial:= 1 to 10000 do
Sum:= Sum + Sim(N);
IntOut(0, N); Text(0, ": "); IntOut(0, Sum/10000); CrLf(0);
];
]</syntaxhighlight>
 
{{out}}
<pre>
2: 24
3: 88
4: 187
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.
<langsyntaxhighlight lang="zkl">fcn bdays(N){ // N is shared birthdays in a population
year:=(0).pump(365,List.createLong(365).write,0); // 365 days == one year
shared:=people:=0; do{ // add a new person to population
Line 1,548 ⟶ 2,250:
println("Average of %d people in a populatation of %s share birthdays"
.fmt(n,simulate(n,0d10_000)));
}</langsyntaxhighlight>
{{out}}
<pre>
Aspen138
337

edits

Retrieved from "https://rosettacode.org/wiki/Special:MobileDiff/232359...352157"