Grasshopper

algorithmic modeling for Rhino

Say I have a list as follows:

{0}

1. CAT

2. DOG

3. TREE

and I want to get every possible combination that does not necessarily use all the indices.  Essentially I want a tree that would look like this:

{0}

1.CAT

2.DOG

3.TREE

{1}

1.CAT

2.DOG

{2}

1.CAT

{3}

1.DOG

2.TREE

{3}

1.DOG

{4}

1.TREE

{5}

1.CAT

2.TREE

Can cross reference be used to produce a tree like this?

Views: 4502

Replies to This Discussion

Yes it is possible, but convoluted and inefficient:

Convoluted because obvious, inefficient because on your way to the answer you end up calculating ALL possible combinations, which is a much larger set.

The general idea being:

  1. Create a collection of characters that enumerate your source collection. In this case the characters 0, 1 and 2 because you have 3 source words (cat, dog and tree).
  2. Using the CharPool component you generate all possible permutations (39 in this case). These permutations start with {0}, {1}, {2}, {0,0}, {0,1}, {0,2}, {1,0}, ... and end in ..., {2,2,0}, {2,2,1},{2,2,2}
  3. Create valid sets from these permutations, meaning any number which appears more than once will be removed. Ie. {0,1,0} becomes {0,1}, while {2,2,2} becomes {2}, while {2,0,1} remains {2,0,1}.
  4. Sort all permutation groups. This will allow us to detect that {2,0,1}, {0,1,2} and {0,2,1} are all in fact the same thing.
  5. Glue the individual characters in each set back into strings again, so {0;1} becomes "01" and {1,2} becomes "12".
  6. Create a new set from all the glued together permutation groups. This once again removes duplicates.
  7. We now have the answer we were looking for, just not in the form we can use. We need to peel apart the strings again into individual characters and then use those characters are indices into our collection of source words.

Oops, forgot to attach the file.

Attachments:

Thanks David.  This next question might shed too much light on my lacking math skills, but let's say I'm dealing with a much larger set of words and the number of permutations is less obvious.  What is the formula for calculating the number of possible pemutations.  I know the basic formala is n^r.  But in the case the formula needs to be solved with r=n... r=1.  Something tells me this is obvious and I'm not seeing it...

Never mind.  I did it like this.  Thanks again.

Yes I can see now how this can be a inefficient way to solve this problem.  It seems like when dealing with 12 source words the number of possible permutations is too high for grasshopper to handle.

Yup, it blows up pretty damn quick.

It is fun thinking about this. I came up with an algorithm which is reasonably efficient, though not particularly elegant. It sometimes generates duplicate entries so it must deal with those which costs additional processor cycles.

It generates an index map which can then be used to retrieve the actual items. Code is heavily annotated, but pretty thorny nonetheless.

Attachments:

The basic idea is that you start with a complete pattern containing all elements, then you recursively remove elements from that pattern, generating all the patterns that are one item shorter. Then you recursively remove individual elements from this new list of shorter patterns to create shorter patterns still. Repeat until the pattern length drops below 1.

The problem is that if you first remove 'B' from 'A,B,C,D' and then remove 'D', you end up with the same pattern as when you first remove 'D' and then 'B'. So these cases need to be tested. I'm sure there's some clever looping that just does the right thing, but I couldn't think of it.

Like this?

Attachments:

Thanks Peter this definitely works except for one minor thing. In my specific case order does not matter.  It seems your script has the added bonus of finding the permutations when order does matter which, in my case, results in duplicate branches.

Maybe this then?

Attachments:

http://www.grasshopper3d.com/forum/topics/permutations-vs-combinations

my 5th virsion (latest post) is the fastest as it uses anemone fast loop 

but Anders version with python is very good

but its good example because in the beginning it also show you how many possible permutations/combinations even for higher values without producing the results

RSS

About

Translate

Search

Photos

  • Add Photos
  • View All

Videos

  • Add Videos
  • View All

© 2024   Created by Scott Davidson.   Powered by

Badges  |  Report an Issue  |  Terms of Service