Tuesday, June 26, 2018

Excel VBA create combinations

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

No comments:

Post a Comment