Combinations Algorithm

 

http://computerserviceofsouthflorida.com/algorithms.html

 

Combinations Algorithm

Introduction
=========
This is a general algorithm for generating the combinations when x items are
chosen from y items. The number of combinations is given by the formula:
y!/((y-x)!x!), where ! denotes factorial. This number is easily calculated.
The problem that arises is listing the actual combinations. As an example:
How many ways can we choose 2 items from 3 items? From the formula :
3!/((3-2)!2!) = 3*2*1/((1)*(2*1) = 6/2 =3.
Now list the combinations. Let’s say the items are A, B and C. Then by
inspection, the list of choices would be : [A,B], [A,C], [B,C]. Easy enough,
in this case. But what if we were to choose 6 items from 9 items?
Again the number of combinations can be calculated from the formula:
9!/((9-6)!6!), which can be simplified to :
9*8*7/6 (since 9! = 9*8*7*6!, and (9-6)! = 3! =6.) = 84.
Now, how do we generate the 84 combinations? Inspection would be very tedious
here. Hence the need for a general algorithm to solve this problem.
Algorithm for generating the combinations when x items are chosen from y items
=============================================================
1. Define a storage array (AR) and store the y items.
2. Define x variables for loop counters.(will require nested loops from 1 to x)
(e.g., x = 6 could have loop counter variables i,j,k,l,m,n)
3. Calculate the number of iterations needed for the 1st loop (outermost) as:
(y-x) +1. (e.g., 6 from 9 would require (9-6) +1 = 4 1st loop iterations).
4.The second loop variable will iterate from 2 (1+1) to (y-x) +2.
;
;
;
5. The xth loop variable will iterate (innermost loop) from the value of
the (x-1)th variable +1 to y. (e.g., for x=6, y= 9, and counters
i,j,k,l,m,n. The xth counter variable, n would iterate from the value
of m+1 to 9 for the innermost loop.).
6. Output the combinations in the innermost loop by using the variable values
as array (AR) indexes:
AR(1st counter), AR(second counter),…..AR(xth counter).
The total nested iterations will generate y!/((y-x)!x!) combinations.
A pseudo-code for generating the combinations when 6 items of integer values
are chosen from 9 such items could look like this:
I. Define array AR of integer, and store the 9 integers
array AR[1..9] (initialize with the 9 items. e.g., AR(1)= 5,AR(2)=10,..etc.
II. Define 6 loop variables and a counter variable .
int i,j,k,l,m,n, c
III. Iterate through the 6 nested loops :
begin
c = 0 {initialize c to 0}
for i = 1 to 4 {remember 9-6 + 1 = 4} do
for j = i + 1 to 5 {9-6 + 2} do
for k = j + 1 to 6 {9-6 +3} do
for l = k + 1 to 7 {9-6 +4} do
for m = l + 1 to 8 {9-6 +5} do
for n = m + 1 to 9 {9-6 +6} do
begin
IV. { Print the combinations in the innermost loop: }
{ You can use a counter, c to track the number of combinations printed.}
c= c +1
Print(c, AR(i),AR(j),AR(k),AR(l),AR(m),AR(n))
end {iterations and prinout of each conbination}
end.
Conclusion
==========
I encountered this problem while trying run a lottery pool where each player’s favorite numbers were to be combined, and then gerenating all possible combinations of them. Although we have yet to hit it big, getting this problem out of the way is a step in the right direction. I have used it for PICK-6 and PICK-5 games (e.g., 5 of 7, 5 of 8, 5 of 9, 6 of 8 and 6 of 9).
I hope this year will be our lucky year. Good luck to you, if you want to use it for the same purpose.
If not, I hope it will be otherwise helpful (e.g., helping you
work out dining arrangements, etc.) I would be willing to furnish working
programs for the lottery examples given above for free, and will be happy to build others for a fee (if requested to do so).

Check out our Downloads page for an example program!

Advertisements
This entry was posted in programming and tagged . Bookmark the permalink.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s