Click here to Skip to main content
13,830,143 members
Click here to Skip to main content
Add your own
alternative version

Stats

25.8K views
684 downloads
16 bookmarked
Posted 15 Apr 2014
Licenced CPOL

C# Class to generate Math. Combinations

, 7 May 2014
Rate this:
Please Sign up or sign in to vote.
Fast algorithm

Introduction

This article introduce simple class able to generate all possible combination sets of non-repetitive (k) elements of a predefined set consist of number of non-repetitive (n) elements, the combination is a way of selecting members from a grouping,, I wrote this code while I'm currently developing an algorithm to find best group of employees are selected from a working group of engineers based on some predefined rules, after excluding the unwanted combinations, some of all possible combinations of these engineers can be extracted.. the included class can be used for fast combinations generations when the total number of combinations becomes in millions.

Background

As known in Mathematics the total number of these generated subsets can be calculated by the formula :

\begin{equation} ^{^{{\Large n}}}{\Large C}_{k} = {n \choose k} = \frac{n!}{k!(n-k)!} \end{equation}

where n! , k! & (n-k)! are the factorials calculated as

n! = n x ((n-1)) x ((n-2)) x ((n-3)) x ….. 3 x 2 x 1

Example :

consider the following example To select different combinations of 5 elements from a group of 7 elements :

  1. Original set of 7 elements
    OrgSet[7] = { S1 S2 S3 S4 S5 S6 S7 }
  2. A subset combination of 5 elements named as
    CombSet[5] = {E1 E2 E3 E4 E5 }
    which are selected from OrgSet elements.
  3. Counter pointer CP which point to an element of the SubSet array that to be stepped up to generate the next combination, The CP pointer initially points to the last element of CombSet which is
    { E5 }
  4. Max Limit array always has the same CombSet size which holds max values allowed for each CombSet element
    Max[] = { mx1 mx2 mx3 mx4 mx5 }
    OrgSet is Initialized with series of integers from 1 to 7 So
    OrgSet[] = { 1 2 3 4 5 6 7 }
    
    Max, which has the same size of CombSet (5 elements), is initialized with the last elements of OrgSet to be
    Max[] ={ 3 4 5 6 7 }

CombSet is initialized with a series of integers from 1 to 5 to be CombSet = { 1 2 3 4 5 }.

Now check the following table carefully which shows the logic sequence to generate all possible combination Sets of 5 elements selected from a original Set of 7 elements, note that E(CP) is not a function of CP but it means E5 when CP=5 or E4 when CP=4 and so on :

Another way to describe what is happening to generate these combinations :

Beginning:

check if counting pointer refer to first element which has reached its Max value,

  • if (Yes) so no more available new results & return back,
  • if (No) continue to below.

Check 1 :

check if the element value reffered to by counting pointer to its Max value by reading Max[CP] .

  • if (Yes) Move the counting pointer to previous location E(n-1) and step it up one step then loop to chck1
  • if (No) continue to below.

Check 2 :

check if the (element value pointed to by CP) +1 = (its Max value)

  • if (Yes) adjust all next elements to equal its previous elements + 1 so that En = E(n-1) + 1.
    Do this up to the last element which is the most right element E5.
  • if (No) Step up that element referred to by counter pointer E(cp) ++.

reset the counter pointer to last element E5,
start over from the Begining to find the next combination.

Here is the flow char of the NextComb() method which clarify its details :

Using the code

After downloading the code you will find the followings :

one constructor and Four methods, they are :

public TCombinator (int elementSize,int CombinationSize) 

constructor take two initial parameters (elementSize, CombinationSize) .

Public void Initializ_Element() 

used to initialize OrgSet [x] Elements with series of +ve integers from 1 up to its length .

public void Initializ_Combin() 

used to initialize Max Ary against each identical element of combAry[] .

public void NextCombin() 

with each call generates new combination updated in CombSet[].

UInt64 CalcCombNum(UInt64 n,UInt64 r) 

to calculate the number of total combinations .

UInt64 Factorial(UInt64 n)  

to calculate the factorial of n .

Two properties are :

n_Element used to Set/get n# of Element of OrgSet, Resize OrgSet[]

k_Combin used to Set/get n# of Combined SubSet Elements, Resize SubSet[]

this class is used through the user interface as shown below :

The main Method that generates the combinations is shown here :

public void NextCombin() 
{ 
    //End of process no new combinations available
    if (Finished) return;

    //last location (which is first element) 
    if (CombSet[1] >= Max[1]) { Finished = true; return; } 
    
    //---------------------------------------------------------------------------- 
    if (CombSet[CP] == Max[CP]) 
    { 
        //------------------------------------------------------------------------ 
        //Loop & step down TC till find CombAry[] != Max[] 
        //------------------------------------------------------------------------ 
        while (CombSet[CP] == Max[CP]) 
        { 
            CP--; 
         } 
         //------------------------------------------------------------------------- 
         //in case the element < its Max value Advance element at 
         //[TC] one step then re-adjust all next elements from location (TC) upto 
         //last location (CombArySZ),, Or Advance element at [TC] one Step directly 
         //------------------------------------------------------------------------- 
         int Loc = CombSet[CP]; 
         if (CombSet[CP]+1 == Max[CP]) 
             CombSet[CP] = ++Loc; 
         else 
             for (int t = CP; t <= var_Combin; t++) 
             { 
                 CombSet[t] = ++Loc; 
             } 
         //------------------------------------------------------------------------- 
         //after this element readjustment, alwayes TC must be reset to 
         //the last element in CombAry[] 
         //------------------------------------------------------------------------- 
         CP = var_Combin; 
         return; 
     } 
     else 
         CombSet[CP]++; 
     // the new combination result has been generated, that you can display or store. 
 } 

Points of Interest

While I’m writing this code I discovered better way to make it faster algorithm !

License

This article, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)

Share

About the Author

ehab_nour
Engineer
Egypt Egypt
This member doesn't quite have enough reputation to be able to display their biography and homepage.

You may also be interested in...

Pro

Comments and Discussions

 
Questionvery nice Pin
BillW3323-Apr-14 7:31
professionalBillW3323-Apr-14 7:31 
AnswerRe: very nice Pin
ehab_nour23-Apr-14 7:58
memberehab_nour23-Apr-14 7:58 
GeneralRe: very nice Pin
BillW3323-Apr-14 8:29
professionalBillW3323-Apr-14 8:29 
BugThe first two images in the article don't display! Pin
Matt T Heffron21-Apr-14 9:41
professionalMatt T Heffron21-Apr-14 9:41 
GeneralRe: The first two images in the article don't display! Pin
Chris Maunder21-Apr-14 17:15
adminChris Maunder21-Apr-14 17:15 
GeneralRe: The first two images in the article don't display! Pin
Matt T Heffron22-Apr-14 6:54
professionalMatt T Heffron22-Apr-14 6:54 
GeneralRe: The first two images in the article don't display! Pin
ehab_nour22-Apr-14 7:42
memberehab_nour22-Apr-14 7:42 
SuggestionText on images in unreadable Pin
_Noctis_15-Apr-14 21:09
professional_Noctis_15-Apr-14 21:09 
GeneralRe: Text on images in unreadable Pin
thatraja16-Apr-14 2:02
protectorthatraja16-Apr-14 2:02 
GeneralRe: Text on images in unreadable Pin
_Noctis_16-Apr-14 12:34
professional_Noctis_16-Apr-14 12:34 
SuggestionUpload Source Code Pin
firmwaredsp15-Apr-14 18:28
memberfirmwaredsp15-Apr-14 18:28 
GeneralRe: Upload Source Code Pin
Oshtri Deka16-Apr-14 1:08
professionalOshtri Deka16-Apr-14 1:08 
GeneralRe: Upload Source Code Pin
fredatcodeproject16-Apr-14 12:56
professionalfredatcodeproject16-Apr-14 12:56 
GeneralRe: Upload Source Code Pin
ehab_nour22-Apr-14 12:54
memberehab_nour22-Apr-14 12:54 

General General    News News    Suggestion Suggestion    Question Question    Bug Bug    Answer Answer    Joke Joke    Praise Praise    Rant Rant    Admin Admin   

Use Ctrl+Left/Right to switch messages, Ctrl+Up/Down to switch threads, Ctrl+Shift+Left/Right to switch pages.

Permalink | Advertise | Privacy | Cookies | Terms of Use | Mobile
Web01 | 2.8.190114.1 | Last Updated 7 May 2014
Article Copyright 2014 by ehab_nour
Everything else Copyright © CodeProject, 1999-2019
Layout: fixed | fluid