If you have a set of elements let's say {A,B,C,D,E} that you want to create all possible non-repeating combinations for, then here you are two simple and straight forward methods. In some cases you may need to know the all possible combinations rather than counting or calculating their count like in the Design of Experiments DOE.
Unfortunately, in this post I am not going to share a copy-and-paste code, but I will introduce two algorithms to implement them easily using any programming language in any suitable way.
As an example, there are 31 possible combinations for the previous set which is hard to calculate manually and the problem can be more serious with higher number of elements.
In both methods we will use letter-coded elements and will rely on some string processing functions. For example, if you have five billiard balls with five different colors, the following coding may be applied:
Method 1:
In this method we will create (initialize) an empty two-dimensional string matrix having number of rows (M) equals the number of elements (n) and number of columns (N) equals the maximum number of combinations for a given group size. Let's name this matrix "Combinations". This matrix will contain -when it is completely filled- all possible combinations for the given set of elements. Each row of this matrix will contain the combinations of (i) number of elements where (i) is the row number of "Combinations". The main advantage of this matrix structure is to contain data in a compact form instead of having long one-dimensional array. This structure also makes it easy to calculate the combinations manually on paper or in spreadsheet.
For the example shown above, the "Combinations" matrix will look like the following image:
The method pseudo code looks like the following sequence:
Define the elements {"A","B","C","D","E"}
First of all, add all elements to the first row of "Combinations" matrix
For each row (i) of "Combinations" matrix starting from first row to the row before the last row
Set column_counter=0
For each non-empty combination in column (j) in the current row (i) of "Combinations" matrix
For each element in elements
If the element is not contained in the current combination string then
If the element alphabetical order is higher than the alphabetical order of the last element in the combination string (ASCII code of element is larger than the ASCII code of the last element in the combination) then
Create new combination by string concatenation = current combination + element
Increment column_counter by one
Add this combination to the first empty cell in the next row of "Combinations" where row number equals i+1 and column number equals column_counter
End If
End If
Next Element
Next Combination
Next Row of "Combinations"
The evolution of "Combinations" matrix during the solution process looks like the following animated .GIF file (frame each 5 seconds)
Method 2:
This method is definitely more simple than the previous method. The core principle of this method is making a good use of binary number representation that it is made of zeros and ones 00101. Each bit in this binary format will represent the existence of the element in this combination; zero (0) means not-exist while one (1) means exist.
To apply this method, we create one-dimensional array for the elements of size (n), one-dimensional array for the binary number representation of size (n) as well, and one dimensional array of size (2^n)-1 for the generated combinations.
The method will go in the following workflow:
For each decimal number starting from 1 to (2^n)-1
Convert the decimal number to n-bit binary format
Multiply each element letter by the corresponding bit value in the binary array and join the results. Note that this is a symbolic multiplication which will return a string where A * 1 = "A" and A * 0 ="".
The resulting string is a possible combination which will be added to the combinations array.
Next decimal number
Since this method produces combinations in a non-sorted way, alphabetical sorting for combinations may be required for better display of data.
To better understand the method, the following is an animated .GIF file (frame each 5 seconds) which shows how the method works.
Key words:
Unique non-repeating combinations algorithm
Combinations using binary number representation
Combinations programming
Combinations pseudo code C++ and VBA
Efficient combinations algorithm
Compute combinations
How to compute combinations
Excel VBA combinations of cells
Combinations matrix
Unfortunately, in this post I am not going to share a copy-and-paste code, but I will introduce two algorithms to implement them easily using any programming language in any suitable way.
As an example, there are 31 possible combinations for the previous set which is hard to calculate manually and the problem can be more serious with higher number of elements.
In both methods we will use letter-coded elements and will rely on some string processing functions. For example, if you have five billiard balls with five different colors, the following coding may be applied:
Method 1:
In this method we will create (initialize) an empty two-dimensional string matrix having number of rows (M) equals the number of elements (n) and number of columns (N) equals the maximum number of combinations for a given group size. Let's name this matrix "Combinations". This matrix will contain -when it is completely filled- all possible combinations for the given set of elements. Each row of this matrix will contain the combinations of (i) number of elements where (i) is the row number of "Combinations". The main advantage of this matrix structure is to contain data in a compact form instead of having long one-dimensional array. This structure also makes it easy to calculate the combinations manually on paper or in spreadsheet.
For the example shown above, the "Combinations" matrix will look like the following image:
The method pseudo code looks like the following sequence:
Define the elements {"A","B","C","D","E"}
First of all, add all elements to the first row of "Combinations" matrix
For each row (i) of "Combinations" matrix starting from first row to the row before the last row
Set column_counter=0
For each non-empty combination in column (j) in the current row (i) of "Combinations" matrix
For each element in elements
If the element is not contained in the current combination string then
If the element alphabetical order is higher than the alphabetical order of the last element in the combination string (ASCII code of element is larger than the ASCII code of the last element in the combination) then
Create new combination by string concatenation = current combination + element
Increment column_counter by one
Add this combination to the first empty cell in the next row of "Combinations" where row number equals i+1 and column number equals column_counter
End If
End If
Next Element
Next Combination
Next Row of "Combinations"
The evolution of "Combinations" matrix during the solution process looks like the following animated .GIF file (frame each 5 seconds)
Method 2:
This method is definitely more simple than the previous method. The core principle of this method is making a good use of binary number representation that it is made of zeros and ones 00101. Each bit in this binary format will represent the existence of the element in this combination; zero (0) means not-exist while one (1) means exist.
To apply this method, we create one-dimensional array for the elements of size (n), one-dimensional array for the binary number representation of size (n) as well, and one dimensional array of size (2^n)-1 for the generated combinations.
The method will go in the following workflow:
For each decimal number starting from 1 to (2^n)-1
Convert the decimal number to n-bit binary format
Multiply each element letter by the corresponding bit value in the binary array and join the results. Note that this is a symbolic multiplication which will return a string where A * 1 = "A" and A * 0 ="".
The resulting string is a possible combination which will be added to the combinations array.
Next decimal number
Since this method produces combinations in a non-sorted way, alphabetical sorting for combinations may be required for better display of data.
To better understand the method, the following is an animated .GIF file (frame each 5 seconds) which shows how the method works.
Key words:
Unique non-repeating combinations algorithm
Combinations using binary number representation
Combinations programming
Combinations pseudo code C++ and VBA
Efficient combinations algorithm
Compute combinations
How to compute combinations
Excel VBA combinations of cells
Combinations matrix
No comments:
Post a Comment