all combinations of numbers

hi, I want to write a script in MATLAB that gives me sum of all possible combinations of a few numbers.

for example I have these numbers as inputs :

120 , 250 , 450

and I want to have sum of all combinations of these numbers means that I want these outputs :

120 , 250 , 370 , 450 , 570 , 700 , 820

I can solve this problem by "ff2n" command if numbers are low (like this example 3 numbers) like this :

ff2n(3)         %due to 3 numbers (120,250,450)
>> 0 0 0
     0 0 1
     0 1 0
     1 0 0
     0 1 1
     1 0 1
     1 1 0
     1 1 1

then I can sum all combinations of numbers by "if" and "for" commands.

but if the number of numbers become more like 135 numbers what should I do ???!!!

[James Tursa]

136 numbers would be 2^136 combinations > 8.7e40 combinations. Seriously, how do you expect to process that many combinations in a reasonable amount of time? You need to rethink your problem.

[f4r3in]

I want to make COPT table in MATLAB and COPT is a table with all combinations of capacities.

my input is this :

20*120 MW (Mega Watt)
30*160
20*250
8*320
6*450
10*480
30*185
10*350
1*1020

So lenght of the input is 135 and I have to have all unique combinations of 135 inputs to make COPT table.

for example :

20*120 have 20 unique combinations likes : 120 , 240 , 360 , ...

and the combinations of 120 must combine with the combinations of other capacities.

In summary I have to have all unique combinations of 135 inputs and it is possible because I run ready COPT program with this inputs and I get 6287 outputs not 8.7e40.

[Walter Roberson]

You do not need to generate for 135 numbers.

Think about the 20*120 for example. That appears to imply 20 copies of 120 MW. But for the purposes of totals, it does not matter which of the copies you use. Using #7, 11, 19 is the same as using #2, 5, 11 for example. All that matters is how many of the 20 are used. Therefore you have at most 21*31*21*9*7*11*31*11*2 possibilities -- using 0 to 20 of the 120, together with 0 to 30 of the 160's, and so on.

But you can do better than that. Two of the 160's has the same capacity as one of the 320's, so you can change 30*160, 8*320 to 2*160, 22*320 and end up with the same generation possibilities. Or you could combine 160's and 320's to create equivalent 480's . You may have to work the logic a bit to figure out how to best take advantage of this.

[f4r3in]

Thank you for answering, but I want to write a general script for COPT table that support any inputs. And input form is something like my example in above. Also I want to have all unique sums (combinations) of capacities. For example 20*120 have 20 unique sums like: 120, 240, 360,... And 30*160 have 30 unique sums but the unique sums of each capacities are not unique and we have to unique it. For example : Sum of four 120 is 480 and also sum of three 160 is 480 too. So I dont need two 480 because one of them shows the unique capacity I want.

[Walter Roberson]

For example 20*120 have 20 unique sums like: 120, 240, 360,

21 unique sums: you forgot the possibility that none of them were selected.

As I outlined above, at the first pass all that is important is the number of 120 MW selected, which can be represented by the integers 0 to 20 instead of having to think about which of the 120 MW generators are online. John and I also pointed out ways that the calculation can be reduced further.

You should probably think about lcm(), least common multiple.

>> lcm(120,250)/120
ans =
    25

25 is > the 20 actual 120 MWs. You cannot substitute between 120 MW and 250 MW in your system.

>> lcm(120,160)/120
ans =
     4
>> lcm(120,160)/160
ans =
     3

3 160's can substitute for 4 120's.

[f4r3in]

I think your way is more complex than my way. As I comment as a answer of john's comment : we can use "nchoosek" command to get all possible subsets of inputs and then we can get the sum of each subset and by using unique command we can get all possible sums of any inputs. But I have other problem named probabilities. I describe it in the comment I put to john's answer. Would you read it?!

[SAMITA]

have you got the code for this. I am also stucked with a problem having 32 generators

Answer 1

[John D'Errico]

It is often true that people decide to do something unimaginably huge, because something small seemed easy enough. Computers are fast and big, so they can do anything, right?

The problem is you don't have enough memory to solve this using brute force. You don't have enough time to solve it in your lifetime.

All possible combinations of those numbers means you need to generate all subsets of numbers, then summing the subsets. A simple trick to generate all such combinations is just to use dec2bin.

V = [120 , 250 , 450];
n = length(V);

allsums = (dec2bin(1:2^n-1) - '0')*V(:)
allsums =
   450
   250
   700
   120
   570
   370
   820

(Think about why that works. It does.)

Of course, many of those sums will be replicated in the above, because there may be multiple ways to generate a specific sum. So, you could use unique on that result. In fact, this is a serious problem, because computing all of the possible sums is a really bad idea when n is large. As has been pointed out, when there are 136 elements in the vector, there are then 2^136-1 possible combinations where at least one of the numbers is included in the sum. That number is hugely more than you can work with, even though the possible sums are far more finite.

So you need to work more intelligently. Brute force is NEVER a good choice, if an alternative is available.

The question is if you really want to find the unique possible combinations. For example, suppose you decided to find all possible sums of the numbers 1:136?

V = 1:136;
sum(V)
ans =
        9316

There are only 9316 possible sums to consider. Once we find one way to create the sum 1136 (for example), we need not look further to see if that sum is possible. In fact, here is a trivial way to find a partition of the number 1136, in terms of the elements 1:136.

136 + 135 + 134 + 133 + 132 + 131 + 130 + 129 + 76
ans =
        1136

Surely you can see how I found that sum.

The point of all this? Work smart, and your computer won't grind to a halt on everything you do.

[f4r3in]

Thanks for good description. As you say "dec2bin" has memory problem like "ff2n" that I used. But the other way for receiving all sums of inputs is to use "nchoosek". Because when we write : nchoosek(Vector,2) We receive all 2 member subsets of inputs so by this command we can get all subsets of any vectors also huge ones. But the other problem that appears is probabilities of each capacity. I forgot to explain the COPT table completely. In COPT table each capacity has a probability and it names outage capacity. For example my full input is something like this: 20*120 0.01 30*160 0.05 . . . So if a combination of numbers used the probabilities of that numbers must multiply to each other. For example : 120 has 0.01 probability And 240 (120+120) has 0.01*0.01 (10^-4) probability.

So the problem is this how can I get the probability of each sum in front of it. (the probability of each combination is different because we use all unique combinations).

[Walter Roberson]

240 (120+120) has 0.01*0.01 (10^-4) probability.

10^-4 probability of failure? So a single 240 MW station is 100 times more reliable than a pair of 120 MW stations? I don't think so.

[f4r3in]

No, it is outage probability. It means that probability of outage of 120 MW capacity (0.01) is more than the probability of outage of 240 (120+120) MW (10^-4).

[Walter Roberson]

For example : 120 has 0.01 probability And 240 (120+120) has 0.01*0.01 (10^-4) probability.

That is bad statistics. 10^-4 might be the probability that both would fail, but it is not the probability that either would fail. The probability that either would fail is according to

>> 1-(1-0.01)*(1-0.01)
ans =
                    0.0199

If you have 69 items all of failure probability 0.01, then

 >> 1-(1-0.01)^69
ans =
         0.500162970100801
         

Over 50% probability that at least one would fail.

If you are trying to find combinations that lead to the lowest probability of failure in providing a particular output, then you could do that with some work, but I would wonder if that is what is what would be desired in an electrical generation system? Suppose I put together a combination that has a 0.01 probability of failure for a given output, but when one of the stations does fail, it takes (say) half of the capacity down with it; and suppose I put together a different combination that has a 0.0101 probability of failure for a given output, but 93% of the time when it does fail, it loses only 1/10th of the output. Would it not be the weighted "resiliance" that would be desired, rather than simply the lowest probability in absolute terms?