This is a Java Script calculator that counts the number of combinations of k objects in a set of n objects and can list those combinations.
To operate the calculator, enter the total number of objects in the set and the size of the subset of objects. Press the Count button to compute the number of combinations. Press the Listing button to compute the result and generate the listing of combinations.
On invalid entries, the Combinations window will display:
Error
Return to Contents
The Java Script source code for this program can be viewed by using the View|Source command of your web browser.
You may use or modify this source code in any way you find useful, provided that you agree that the author has no warranty, obligations or liability. You must determine the suitability of this source code for your use.
Return to Contents
number of combinations
The formula for finding the number of combinations of k objects you can choose from a set of n objects is:
n!
nCk = ----------
k!(n - k)!
For selecting 2 objects out of 3 we get
3! 3·2·1 6
3C2 = ------ = ------ = -- = 3
2!·1! 2·1·1 2
For selecting 4 objects out of 10 we get
10! 10·9·8·7·6!
10C4 = ------ = --------------
4!·6! (4·3·2·1)·6!
10·9·8·7 5040
= -------- = ---- = 210
4·3·2·1 24
listing the combinations
An algorithm to generate combinations is shown below. Starting from the first combination of k objects from a set of n objects, the algorithm generates the next combination in lexicographic order.
a0 <-- 1, a1 <-- 2, ... ak-1 <-- k % first combination is: 1 2 3 ... k
loop
i <-- k - 1 % start at last item
while ai = (n - k + i + 1) % find next item to increment
decr i
end while
exit when (i < 0) % all done
incr ai % increment
for j <-- i + 1 ... k - 1 do % reset elements to the right
aj <-- ai + j - i
end for
end loop
Return to Contents
AbCd Classics - free on-line books