Every Possible Combination of Indices

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?

Replies to This Discussion

Permalink Reply by David Rutten on December 13, 2016 at 10:36am

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:

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).
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}
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}.
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.
Glue the individual characters in each set back into strings again, so {0;1} becomes "01" and {1,2} becomes "12".
Create a new set from all the glued together permutation groups. This once again removes duplicates.
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.

Permalink Reply by David Rutten on December 13, 2016 at 10:36am

Oops, forgot to attach the file.

Attachments:

permutations.gh, 19 KB

Permalink Reply by Ryan Whitby on December 13, 2016 at 2:34pm

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...

Permalink Reply by Ryan Whitby on December 13, 2016 at 2:38pm

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

Permalink Reply by Ryan Whitby on December 13, 2016 at 2:58pm

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.

Permalink Reply by David Rutten on December 13, 2016 at 3:18pm

Yup, it blows up pretty damn quick.

Permalink Reply by David Rutten on December 13, 2016 at 4:02pm

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:

combinations.gh, 20 KB

Permalink Reply by David Rutten on December 13, 2016 at 4:05pm

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.

Permalink Reply by peter fotiadis on December 13, 2016 at 10:36am

Like this?

Attachments:

Lists-combine_14_V1.gh, 121 KB

Permalink Reply by Ryan Whitby on December 13, 2016 at 3:00pm

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.

Permalink Reply by peter fotiadis on December 14, 2016 at 1:05am

Maybe this then?

Attachments:

Lists-combine_14_V2.gh, 122 KB

Permalink Reply by Mohamed Naeim on December 14, 2016 at 5:23am

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