algorithmic modeling for Rhino
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?
Views: 1027
Replies to This Discussion
-
Permalink Reply by David Rutten on
-
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.
-
-
-
- Attachments:
-
-
SummationSequences.gh, 8 KB
-
-
-
-
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.
-
-
-
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
-
hahahaha!! thanks for your effort.. i am trying to add more logic's to reduce the possibilities...
-
-
-
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
-
-
-
-
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)
-
-
-
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
-
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.
-
-
-
Do those numbers still hold if you enforce the 'numbers-to-the-right-can't-get-bigger' constraint'?
-
-
-
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
-
About
Welcome to
Grasshopper
Translate
Search
Photos
Videos
-
Scaling Tower
Added by Parametric House 0 Comments 0 Likes
-
Field Trap
Added by Parametric House 0 Comments 0 Likes
© 2024 Created by Scott Davidson.
Powered by
