For array[n], get all possible combinations of x elements

[Technetium]

This isn't really a specific VBA question, it's more of a general programming logic question that I'm having some trouble figuring out.

Suppose I have an array of an unspecified size n. Let's call it myArray(n). Each element in the array is a number. I want, through a process of iteration, to multiply numbers in myArray(n), such that I have created multiplications for every possible combination of x numbers in myArray(n) and add the multiplied results together.

Example. MyArray(5) contains 5, 6, 7, 8, 9
If x = 3, then the code should produce:
(5*6*7) + (5*6*8) + (5*6*9) + (5*7*8) + (5*7*9) + (5*8*9) + (6*7*8) + (6*7*9) + (6*8*9) + (7*8*9)
If x = 4, then the code should produce:
(5*6*7*8) + (5*6*7*9) + (5*6*8*9) + (5*7*8*9) + (6*7*8*9)

Part of the difficulty in writing the code for this is that it appears that increasing x by 1 increases the number of nested For loops needed.

[curiouscat408]

It is possible to write such an algorithm without increasing the number of nested For-loops.

But first, I suggest that you calculate WorksheetFunction.Combin(n, x) to determine if it is computationally feasible.

For example, COMBIN(1234,5) returns 23,652,162,953,496 -- not only prohibitively long execution time-wise, but also far too many for a single string as you describe.

[Technetium]

It is possible to write such an algorithm without increasing the number of nested For-loops.

But first, I suggest that you calculate WorksheetFunction.Combin(n, x) to determine if it is computationally feasible.

For example, COMBIN(1234,5) returns 23,652,162,953,496 -- not only prohibitively long execution time-wise, but also far too many for a single string as you describe.

There's no issue with the string length. The way I do this is there is a variable "total", which has each multiplied group ("temp_mult_total") added to it incrementally.

However, I am indeed running into performance issues when the array length is around 24 elements. I'm currently using MsgBox to test certain values of temp_mult_total (basically, ones greater than 0 since there are a lot of 0s in the array).

Here is the function I came up with. I'll paste the whole thing in.

Please Login or Register  to view this content.

I noticed that when I ran this using a range with 24 cells, Excel would intermittently become "not responding" but after a few seconds a MsgBox would appear with a value and the "not responding" state would go away..
Despite this issue, the function resolved correctly. However, when I included the full range of 100 elements, it became "not responding" and I had to ctrl-break out because I didn't know if it was doing anything or just stuck.
I'm okay with the process taking a long time, but it would be nice to have a way to know if it's still calculating when it says "not responding" or if the program has crashed.

[Technetium]

I realize that function is a monstrosity and here is some explanation of the strategy in it:
In addition to the array containing probabilities, it creates another array ("mult_array") of the same size where each element contains either 1 or 0, which determines whether or not a current array element is being used in a multiplied group.

For example
if the array of probabilities has 15 elements and the function is currently evaluating for exactly 7 true, then mult_array starts out containing:
1 1 1 1 1 1 1 0 0 0 0 0 0 0 0
From this, it knows to multiply p_array(0) through p_array(6) and the inverse of p_array(7) through p_array(15). What this is doing is getting the probably of exactly the first 7 elements in the array and not getting the remaining 8 elements.
This creates the first multiply group which is then added to total.
Then it goes through an algorithmic process to move mult_array to the next step, which basically looks through the array starting from the right until it finds a 0 with a 1 to the left of it, and swaps those values. Then it moves any floating 1s to the right of the swapped pair back.
So the second step for mult_array is
1 1 1 1 1 1 0 1 0 0 0 0 0 0 0
And here is an example of how it updates when there are floating 1s to the right of the swapped pair:
1 1 1 1 0 0 1 0 0 0 0 0 0 1 1 becomes 1 1 1 1 0 0 0 1 1 1 0 0 0 0 0
This guarantees that all possible combinations are evaluated. In this case, the last organization of mult_array is 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1, and that this point every possible combination of getting exactly 7 successes in 15 trials has been multiplied together and then added to the total.

[Technetium]

But first, I suggest that you calculate WorksheetFunction.Combin(n, x) to determine if it is computationally feasible.

So I just did this with COMBIN(100,50), which is only first step if I want to know the probability of "at least half" of 100. It gave a value that is 29 digits long. I don't think even the best super-computer in the world can evaluate this in a reasonable amount of time. That's disappointing. With the smaller sizes of the arrays, it appears that my function is mathematically sound, but it seems I won't be able to use this function for the data I am working with.

Do you know if there is another way to do this?

[Technetium]

I was making it much harder than I had to. The set of probabilities currently includes a lot of 100% and 0%, which there is no point evaluating. If I have a set of 100 and I need at least 50, and 44 are 100% and 43 are 0%, then I really only need to evaluate for at least 3 out of 13.

In the future I do need to be able to handle larger sets, and it looks like Normal Distribution is the way to go there. I'll need to read up more on that when it comes.

[Akuini]

Hi, Technetium
I don't quite understand the requirements, but maybe this help:
I found a code by MickG in this thread
https://www.mrexcel.com/board/thread...7/post-5267593

Note: to make the code readable you can convert it via this site: https://www.browserling.com/tools/bbcode-to-text

I've amended the code to suit your requirement, hopefully, which is:

I want, through a process of iteration, to multiply numbers in myArray(n), such that I have created multiplications for every possible combination of x numbers in myArray(n) and add the multiplied results together.

You need to put the array in col A, starting at A1 then run Sub Combinations_3()
Adjust --> k = 3 ' adjust number of element
The result is in C3.

Here's the amended code:

Please Login or Register  to view this content.

Example:
Excel 2016 (Windows) 32 bit

	A	B	C
1	5		3
2	6		3325
3	7
4	8
5	9

Sheet: Sheet2

[Technetium]

Part of the problem is that the conditions in my initial post were in error. I had tried to simplify what I was doing in the example and it led to make a critical error. I said I needed to get every combination of k elements of array[n], multiply those elements together and then add each group. This is not correct, though.

In this case, the array[n] contains a set of different probabilities. I am trying to find the probability that k out of array[n] evaluate true. So what I actually need to do is, for a value of k, get every combination of array[n] where k elements are multiplied at their value and the remaining n-k elements are multiplied at 1 minus their value. This is not feasible for arrays larger than 20 elements, and my largest array I need to evaluate has over 400 probabilities.

I think I've been going about this with the wrong approach, so instead I'm going to stop here and start a new thread asking for assistance on Normal Distribution, which, based on googling, was suggested as a way to calculate this when the array becomes too large to work with.