Sweet Combinations (Result)
Vector 4:3, page 109
Transcribed from the printed issue; not yet reviewed. Read it in the PDF of the issue, page 109
The problem was to write a function COLOURS which returns the probability of having exactly 1, 2, 3, … N different colours in a pack of sweets. There are N colours available, equally probable, and the pack is filled randomly with M sweets. For example:
The competition attracted thirteen entries from Canada, Australia, USA and the UK, using VS APL, APL*PLUS PC and IBM PC APL, and the approaches used to tackle the problem can be categorized roughly in four ways.
1. By Induction / Recursion¶
The problem can be solved by induction on the number of sweets, M, because if there are R distinct sweets in a pack of size M, then either
a) There were R distinct sweets in the first (M-1) sweets and the next sweet is the same as one already chosen, or
b) There were (R-1) distinct sweets in the first (M-1) and the next one is a new colour.
The initial conditions are easy to set up and this approach gives rise to recursive or iterative solutions.
Alternatively, the recursion can be done on the number of colours present using the following logic provided by Zeke Hoskin:
There are N*M ways to pick M sweets of N colours but
((N-1)*M) x (N-1)!N of these will show fewer than N colours, but
((N-2)*M) x (N-2)!N of those will show fewer than (N-1) colours etc. etc.
Several of the solutions followed this kind of theme.
2. Exact Mathematical Expression¶
Various entrants built on the logic described above to arrive at an exact mathematical expression for the answer, and some found the answer in Statistics textbooks (Feller was the favourite).
One expression is :
3. Counting the Options¶
This involves calculating all the different option and counting up those which meet the criteria. Various entrants devised neat means of doing this using local functions and matrix division to speed up the calculations and reduce the sizes of the intermediate arrays.
4. Simulation¶
Richard Connor belied his statement that “I recognize the Candy packing machine is a stochastic process, but my knowledge of them is confined to spelling ‘stochastic’” by submitting two simulation functions and asking the judges to spin a coin to decide between them!
Not surprisingly those solutions in the first two categories were the most efficient, but I don’t dismiss the simulation or counting approaches too readily. Faced with a practical one-off problem of this type the Marketing Manager is interested in the speed of obtaining an answer which is correct to 3 or 4 decimal places; not that it was achieved using an APL function which took 134 milliseconds to run and and which was index origin independent! If the hypotheses of randomness or that the colours are equally likely are altered in any way then a theoretical approach is well nigh impossible.
By testing the entries with different values of N and M it was fairly easy to arrive at the three best solutions without having to resort to pathological input data, although it was interesting to see that some of the non-looping solutions produced nonsense if a value of N much greater than M was used. Those entrants who went to a lot of trouble to remove loops or recursion will be annoyed to learn that the iterative solutions are much quicker for larger values of M.
Prizes¶
Joint first prize goes to Prof. Alan Hawkes of Swansea and Dr. Roger Glassey of Berkeley whose solutions are both efficient and very readable, and third prize to John Buckland of Camberley whose answer uses different algorithms depending on the size of the input data.
Thanks to them and to all the other entrants.
Z←N COLOURS C;R
---------------
[1] ⍝ RECURSIVE SOLUTION BY ALAN HAWKES TO COLOURS PROBLEM
[2] ⍝ PROBLEM FROM VECTOR VOL3 NO4 (APRIL 1987), P 114
[3] ⍝ RESULT IS VECTOR OF PROBABILITIES OF 1 TO C DIFFERENT COLOURS
[4] ⍝ IN N INDEPENDENT SELECTIONS FROM C EQUALLY LIKELY COLOURS.
[5] ⍝ N AND C ARE POSITIVE INTEGER SCALARS.
[6] →(N=1)/INIT
[7] R←(1-⎕IO)+⍳C
[8] Z←((R×Z)+¯1↓0,(C-R)×Z←(N-1)COLOURS C)÷C
[9] →0
[10] INIT:Z←C↑1
∇
P←S COLOURS C;I;K
-----------------
[1] ⍝ P[K] is prob that K colours of a possible C will be found
[2] ⍝ in a pack of S sweets
[3] ⍝ Solves a difference equation to calculate prob vector P.
[4] ⍝ At iteration I, P[K] is probability for I sweets
[5] ⍝ Adding 1 more sweet to the box adds a new colour with
[6] ⍝ prob (C-K)÷C, but a matching colour with prob K÷C.
[7] ⍝ If S=0, return the 0 vector, else P[1]←1
[8]
[9]
[10] P←(S>0),1↓C⍴0 ⋄ I←0
[11] K←(1-⎕IO)+⍳C
[12] LOOP:→(S≤I←I+1)↑0
[13] P←((P×K)+(0,¯1↓P)×1+C-K)÷C
[14] →LOOP
[15]
[16] ⍝ Roger Glassey
[17] ⍝ Dept of IE&OR
[18] ⍝ University of California Berkeley
[19] ⍝ 10 June 1987
∇
R←S COLOURS N;I;W;X;Y;Z
-----------------------
[1] ⍝R IS PROB OF 1-N COLOURS APPEARING IN PACKSIZE S - FOR SMALL W/S
[2] →(~⍴R←⍳∧/2=(⍴I),+/×I,-1|I←S,N)/0 ⋄ →(20<+/I)/L1 ⍝ POS INTS ONLY
[3] W←¯1↓Y←!X←0,⍳N ⍝ FOR SMALL S AND N
[4] R←((¯1↑Y)÷⌽W)×-⌿(X∘.≤X)×(-X←¯1↓X)⌽⍉(((1↓X÷N)*S)÷1↓Y)∘.÷W ⋄ →E
[5] L1:→(S=1↑R←N↑I←1)/0 ⋄ X←X,[1.5]⌽X←(⍳N)÷N ⍝FOR LARGE S AND N
[6] L2:R←+/X×R,[1.5]0,¯1↓R ⋄ →(S>I←I+1)/L2
[7] E:R←,'F14.11' ⎕FMT R
[8] ⍝ JCL Buckland
∇