Imagine sorting a basket of laundry consisting of n pairs of socks, each of a different color. Randomly pulling out socks, one at a time, you will either put each on the sorting surface or match it up with its mate to make a pair and put them away in the sock drawer.
The maximum number of socks in the sorting space can then be any number from 1 to n. For example with 3 pairs, pulling them in the order AABBCC will only require one space, ABACCB requires two, and ABCABC will require three spaces.
Find the expected number of sorting spaces required in terms of n.
for n=2:17
alpha='aabbccddeeffgghhiijjkkllmmnnooppqqrrssttuuvvwwxxyyzz';
socks=alpha(1:2*n);
totspace=0;
for trial=1:1000000
srce=socks; space=''; mx=0;
while ~isempty(srce)
r=randi(length(srce));
c=srce(r);
srce(r)='';
sf=strfind(space,c);
if ~isempty(sf)
space(sf)='';
else
space=[space c];
end
if length(space)>mx
mx=length(space);
end
end
totspace=totspace+mx;
end
fprintf('%4d %10d %10d %10.8f\n',n,totspace,trial,totspace/trial)
end
finds for n= 2 to 17
total of expected
n needed trials value
spaces
2 1666101 1000000 1.666101
3 2332919 1000000 2.332919
4 2961024 1000000 2.961024
5 3574332 1000000 3.574332
6 4174017 1000000 4.174017
7 4762736 1000000 4.762736
8 5343320 1000000 5.343320
9 5919300 1000000 5.919300
10 6488262 1000000 6.488262
11 7054210 1000000 7.054210
12 7620058 1000000 7.620058
13 8177731 1000000 8.177731
14 8732739 1000000 8.732739
15 9289301 1000000 9.289301
16 9836566 1000000 9.836566
17 10387656 1000000 10.387656
|
|
Posted by Charlie
on 2023-09-30 12:59:31 |
random trials of one million each n
