How to generate bigger number of list

Hi, i am using python component to generate all combination of number which sum up to particular given number.(this works for small number with lesser variables)

INPUT x=1500
scrpit:

import rhinoscriptsyntax as rs
a=[]
b=[]
c=[]
d=[]
e=[]
f=[]
g=[]
h=[]
i=[]
for i15 in range(1,x,1):
for i14 in range(1,x,1):
for i13 in range(1,x,1):
for i12 in range(1,x,1):
for i11 in range(1,x,1):
for i10 in range(1,x,1):
for i9 in range(1,x,1):
for i8 in range(1,x,1):
for i7 in range(1,x,1):
if(i15+i14+i13+i12+i11+i10+i9+i8+i7==x):
a.append(i15)
b.append(i14)
c.append(i13)
d.append(i12)
e.append(i11)
f.append(i10)
g.append(i9)
h.append(i8)
i.append(i7)

This scrip getting stuck..what should i do get all combination?

Replies to This Discussion

Permalink Reply by David Rutten on September 6, 2014 at 3:43pm

So you're trying to generate 9 integers (between 1 and X) that sum together to X?

Right now you're trying all possible combinations, meaning that for x=1500, you have to run this loop 1500^9 times, which is 38 octillion times. If every iteration takes 1 microsecond, you'll be done in 10^15 years, or 89000 times the age of the universe. I think 'stuck' is an apt analogy. You might enjoy this sculpture by Arthur Ganson.

I do not know how many possible combinations there are, but it sounds like an awful lot. I don't think you can generate all of them in a reasonable amount of time.

A different approach would be to generate the sum as a sequential process. Then at least you can code up some trivial abort logic in case the amount of remaining positions is larger than the distance to X, or if the amount of remaining positions * X is smaller than the distance to X. But I wouldn't expect it to suddenly finish in a few seconds though.

Permalink Reply by David Rutten on September 6, 2014 at 5:30pm

Attachments:

SummationSequences.gh, 8 KB

Permalink Reply by David Rutten on September 6, 2014 at 5:31pm

Well, my text got axed for some reason.

I was saying that if you only want to generate those summation sequences which have no increasing values from left to right then the problem becomes tractable I think. I have no mathematical proof of the above algorithm, but it seems to work.

Permalink Reply by David Rutten on September 6, 2014 at 5:34pm

Well, scratch that, it doesn't generate all possible sequences. My logic is clearly off.

It's 1:34 in the morning though and I'm tired...

Permalink Reply by s s solomon on September 6, 2014 at 10:53pm

hahahaha!! thanks for your effort.. i am trying to add more logic's to reduce the possibilities...

Permalink Reply by David Rutten on September 7, 2014 at 5:01am

Minor change to the code, it at least generates more sequences, I'm still not sure whether it generates all of them.

Attachments:

SummationSequences.gh, 9 KB

Permalink Reply by David Rutten on September 7, 2014 at 6:20am

Incidentally here's my logic for those who'd rather not parse dense C#.

The basic premise of my algorithm is that each sequence is logically followed by the next sequence, until we've reached the last sequence at which point we're done. I have no proof this is in fact true. But if it is true, it means that we can write down the first sequence and then keep in generating additional ones until we have the entire collection.

As mentioned before, the numbers in a sequence are always in descending order. In other words, the neighbour to the right of a number is not allowed to be bigger (but it is allowed to be identical) than the number itself. Thus, {5,4,2,1,1,1} is a valid sequence, but {5,4,1,2,1,1} is not as 2 is bigger than 1.

We only allow a single type of operation on a sequence in order to generate the next one. One of the numbers is incremented by 1, another number is decremented by 1. Again, I have no proof this methodology is capable of generating all possible sequences.

We always start of with the following sequence:

{X-(N-1),1,1,...,1}

Or, in English, all the values are 1, except for the first one which is necessarily set to whatever it needs to be in order to give the correct sum.

In order to generate the next sequence from any given sequence, the following algorithm is applied:

Iterate from left to right over all numbers except the rightmost one.
If the number at i is larger than its immediate neighbour plus one, decrement the number at i and increment the number at i+1. This results in the next sequence (see figure 1).
If none of the numbers is larger than its immediate neighbour plus one, then iterate again from left to right (skipping the rightmost number) and find a number which is larger than its immediate neighbour (not the neighbour plus one in this case).
Then keep on looking towards the right until you find a number which is less than the previous number. Once found, decrement the origin number and increment the newly found number (see figure 2).
When either rule fails to generate a new sequence, we're done.

(figure 1, rule 1)

(figure 2, rule 2)

Permalink Reply by Thomas on September 7, 2014 at 6:26am

Is there a reason to exclude e.g. 1493+2+2+1+1+1?

Permalink Reply by David Rutten on September 7, 2014 at 7:46am

No it should be in the list. If it isn't then you've just found proof that my approach still doesn't work.

Permalink Reply by Thomas on September 7, 2014 at 8:03am

Actually I don't think that it's possible to calculate and handle the combinations for 9 elements with reasonable expense.

The number of unique valid combinations grows very fast:

1 Element : 1 combination
2 Elements : 750 combinations
3 Elements : 187500 combinations
4 Elements : 23484375 combinations
5 Elements : 1769539000 combinations
...

Even if you get all combinations with a magic zero-time-algorithm it's nearly impossible to store them or apply functions on them.

Permalink Reply by David Rutten on September 7, 2014 at 8:14am

Do those numbers still hold if you enforce the 'numbers-to-the-right-can't-get-bigger' constraint'?

Permalink Reply by Thomas on September 7, 2014 at 8:27am

I used the algorithm in my example below. It also avoids duplicate sequences by allowing only descending lists. I proofed the algorithm only with a smaller example (Sum(3 Elements) == 100) but it seems to work.

Anyway I only managed to calculate the number of combinations with 5 elements by dropping the results immediately.

1769539000 * 9 * 32 bit = 63.7GB