Home → Show your Work →

Combinatoric Toolkit

• Edit

john

10 Jul, 2023 11:46 PM

NOTE: also see an addition combinatorial node, int_part, introduced later in this thread.

Attached are some nodes (described below) that may be useful for anyone doing projects involving combinatorics:

• factorial. Calculate exact value of n!
• n_choose_k. Calculate the binomial coefficient n choose k, the number of ways to choose k elements from a set of n elements
• combos. Generate a list of all possible ways to choose k items from a set of n elements
• stirling. Calculate the Stirling Number of the second kind S(n,k), the number of ways to partition a set with n elements into k partitions
• bell. Calculate the Bell Number B(n), the total possible partitions of a set with n elements
• partitions. Generate a list of all possible partitions of a set with n elements

How many rhyme schemes are there for a three-line poem?

• 000 = AAA = Roses are red / Violets are dead / Try tulips instead
• 001 = AAB = Roses are red / Violets are dead / Tulips are pink
• 011 = ABB = Roses are red / Violets are blue / Tulips are too
• 012 = ABC = Roses are red / Violets are blue / Tulips are pink
• 010 = ABA = Roses are red / Violets are blue / Tulips are dead

There are 2 schemes for a 2-line poem, 5 schemes for a 3-line poem, 15 schemes for a 4-line poem, and 52 schemes for a 5-line poem. 2, 5, 15, 52, 203, 877, 4140, 21147... are the Bell Numbers.

B(n) counts the total number of ways to partition a set of n elements. The partitions node lets you see the codes representing each one. You can use them, and the other nodes, for many things other than rhyme schemes.

The attached demo file contains examples showing some ways of using these nodes, with some additional nodes that may also be useful.

Notes

• factorial. n! = 1 x 2 x 3 ... x n. It's a tricky value to calculate because it grows so fast. 20! is the highest value that can be represented as an integer in Nodebox. 170! is the highest value that can be represented as a number. The factorial node outputs as a string in order to provide exact values even for 170! The add commas option shows the value with comma separators for easier reading; uncheck this if you want to use it in calculations.
• n_choose_k. The binomial coefficient has countless applications. If arranged in rows for each value of n, they form Pascal's triangle. The node accepts values of n and k from 0 to 170; if k exceeds n, the function returns 0. For more information, see https://en.wikipedia.org/wiki/Binomial_coefficient
• combos. This function returns a list of n choose k strings. Each string is a comma-separated list of element indices ranging from 0 to n-1. You can use the make_strings node to break each string into a list of indices, which you can then feed into a slice node to select a subset of objects (see the star-tips section of the attached demo). If k exceeds n the function will return an error message.
• stirling. Like n choose k, Stirling numbers can also form a triangle, but the values grow much faster. For high values of n, some numbers will exceed the maximum allowed value and return "Infinity" or "NaN" (Not a Number). If k exceeds n, the function returns 0. See https://en.wikipedia.org/wiki/Stirling_numbers_of_the_second_kind
• bell. Bell(n) is simply the sum of stirling(n,k) for k from 0 to n. Because it grows even faster than the factorial function, n is capped at a maximum value of 143. See https://en.wikipedia.org/wiki/Bell_number
• partitions. My partitions node returns partition codes for n values between 2 and 9. Each code is an n-digit number, with digits varying from 0 to n-1. The digit tells which partition each element belongs to. A 0 in the first place means that the first element belongs to partition 0; a code of 01001 indicates a set divided into two partitions with the first, third, and fourth items in partition 0 and the second and fifth items in partition 1. The partition patterns form a Gray code, which means that only one digit changes from each code to the next. The algorithm to generate this code was invented by Gideon Erlich and described by Donald Knuth in "The Art of Computer Programming Volume 4A".

The attached demo poster contains usage examples for all six functions, including star tips for the combos function and Genji-ko diagrams for the partitions function.

Some people are confused by the difference between combinations and partitions. As shown in the demo, there are 5 choose 3 = 10 ways to color three tips in a five-point star. But there are S(5,3) = 25 ways to partition a set of 5 tips into 3 different subsets (e.g. color them 3 different ways). The 5 choose 3 star patterns shown in the poster actually divide the set into 2 partitions (colored or not). But S(5,2) = 15, not 10, because there are also 5 ways to color just one tip (which also divides the set into two partitions). So combos show all the ways of choosing k elements from an n-item set, while partitions show all the ways of dividing that set into k different subsets.

S(5,3) tells us there are 25 ways to color star tips using 3 colors. If you look at the 52 codes produced by partitions(5), you will see that 25 of them include 0s, 1s, and 2s with no 3s or 4s. The first such code, 00012, indicates a star with the first 3 tips (starting from the southeast tip) assigned color 1, the next assigned color 2, and the last assigned color 3. You could use red, blue, and green for your three colors (red, red, red, blue, green). But if you changed the order of the colors (say blue, blue, blue, red, green), this would be considered the same partition. You could use any of the 3 colors for the first partition and either of the remaining 2 for the second partition, so there are 3! = 6 ways of ordering the colors for that partition. So the total number of distinct ways of coloring the tips of a 5-point star red, blue, and green with at least one instance of each color is S(5,3) * 3! = 25 * 6 = 150.

The Genji-ko patterns shown in the poster are an attractive and intuitive way to visualize partitions. In medieval Japan they were associated with an incense game involving 5 sticks of incense (see https://en.wikipedia.org/wiki/Kōdō#Monkō). The 52 possible ways of partitioning those sticks became associated with the chapters of The Tale of Genji, hence the name (there are actually 54 chapters in the novel, so 2 additional symbols were added). I was introduced to this in a charming book, which I heartily recommend: Once Upon a Prime by Sarah Hart.

Note: my genji_ko node works well for sets up to 7 elements, but will (rarely) make incorrect drawings for larger sets. There can be more than one way to draw these partitions; the choice is a matter of aesthetics. Several of the 5-element diagrams produced by my node are correct, but differ from the classic forms shown in the Wikipedia article.

I hope you find these nodes useful. If anyone sees this, PLEASE drop a quick reply and tell me which of these six nodes I should include in the next version of my Cartan Node Library.

All nodes in this demo are free to use without restriction. Happy Nodeboxing!

• combo_toolkit_screenshot.png 650 KB
• combinatoric_toolkit.ndbx.zip 392 KB

1. 1 Posted by Gabriel on 12 Jul, 2023 02:48 AM

   

   John, I never get why we have to keep releases clean. I wish the Cartan nodes were included with Nodebox releases, I would just include everything that you thought might be vaguely useful. Obviously I'm not a programmer in the sense of knowing about workflow and conventions.

   Writing this on a phone so I haven't had a chance to test it the new nodes yet. I will try them and get back to you in the most useful ones.

   • Edit

2. Support Staff 2 Posted by john on 12 Jul, 2023 06:40 AM

   

   Gabriel,

   THANK YOU for posting a reply. I can't see views on this old forum system, so if no one replies I have no way of knowing whether or not anyone has seen my post.

   There are two reasons that Cartan nodes cannot all be just added to Nodebox: a can't and a shouldn't.

   I have no control over new releases of Nodebox itself. That can only be done by its inventor, Frederik. Frederik has moved on to other things and now has little time to maintain Nodebox. New releases on both MacOS and Windows are a bit of pain, and turning my subnetworks into actual native nodes would be a ton of work, since they would have to be rewritten in Python, integrated into the rest of the system, and thoroughly tested.

   I do wish Frederik would someday add at least SOME of my well-proven nodes, but I understand why he not yet done so.

   But even if he could dump all of them into Nodebox, it would probably not be wise. Nodebox was designed to be friendly to artists (not all of whom want to spend a lot of time coding). In order to become comfortable with it and quickly solve problems, you need to learn most of the nodes - just like you need a working vocabulary to become fluent in any language.

   Nodebox already has almost 150 nodes, and I think this is already intimidating to some people. If Nodebox had, say, 500 nodes it would be harder to master, harder to even find the node you were looking for each time.

   There's an interesting idea called "Dunbar's number" that claims an individual human can maintain stable social relationships with about 150 people, not more, because of the way our brains are wired. The truth of this, and the exact value, are debatable, but I have found over the years, in both my social groups, corporate reporting structures, and computer languages, that somewhere around 150 is a sweet spot - big enough to be powerful but not too big to handle with ease.

   For that reason I am also cautious about dumping too many nodes into my Cartan Node Library (which is already north of 100 nodes). So whenever I make a new node I take some time to consider if it is "worthy" before adding it to the pile. But thanks for wishing for more more more.

   I responded separately to the thread on your website. Your work is really interesting and thinking about it has made me wonder if we need even more combinatorial nodes (like an integer partition).

   • Edit

3. Support Staff 3 Posted by john on 15 Jul, 2023 08:13 AM

   

   Attached is a NEW node to add to our Combinatoric Toolkit: int_part.

   int_part, short for "Integer Partition", generates a list of all possible ways of expressing a positive integer N as the sum of positive integers. For example, 5 can be expressed as a sum in seven different ways:

   • 5
   • 4 + 1
   • 3 + 2
   • 3 + 1 + 1
   • 2 + 2 + 1
   • 2 + 1 + 1 + 1
   • 1 + 1 + 1 + 1 + 1

   Notice that the values in each expression always decrease. This is to prevent some equivalent sums from being counted more than once. 4 + 1 is considered the same as 1 + 4, so only the first variation is included.

   int_part will take values of N from 1 to 24. 24 can be summed in 1575 different ways!

   The attached demo shows the 77 ways of finding sums for 12. Each digit d is represented by a block of d squares colored in one of 12 different hues.

   Integer partitions are primarily used in number theory, but could have a number of other interesting uses for generative artists.

   Enjoy!

   John

   • int_part_screenshot.png 307 KB
   • int_part_demo.ndbx.zip 7.41 KB
   • Edit

4. 4 Posted by edgeofinnerspac... on 27 Jul, 2023 11:55 AM

   

   well, as i've said a couple of times now: you have proven to be my most valuable source and resource out of the very few times we have even acknowledged each others' existence. i find this collection very cool but honestly, 90% of everything you post is still leagues over and above my ability to comprehend it.

   now im off to see if those nodes will tell me exactly just how far UNDER it im STANDING!

   :D ...well, atleast i entertain myself... easier than arguing with me thats for sure. that guy always wins... but i digress. i think i could work with that integer thing there. i feel like i've come across the need for such a thing recently. seems friendlier than the bit at the top.

   • Edit

5. Support Staff 5 Posted by john on 28 Jul, 2023 04:28 AM

   

   Thanks, Edgeofinnerspace! I wish this forum software had a like or laugh button.

   I encourage you to play with these nodes and try to make some art with them. I'm really not sure what kinds of things you could do, but I have a hunch you could surprise me.

   Play! Share! Have fun!

   • Edit

6. 6 Posted by goreda on 28 Jul, 2023 07:50 PM

   

   I tweaked some nodes,
   played a while even made a tiny animation and;
   et voilà! All my anxieties are gone.

   Thank you, John!

   Here are the results:
   ↓

   • 2023-07-28_22-36-23.png 5.09 MB
   • 2023-07-28_22-44-05.png 1.47 MB
   • Edit

7. Support Staff 7 Posted by john on 28 Jul, 2023 10:53 PM

   

   Goreda,

   Wow! Way cool.

   Do you want to say anything more about which nodes you used and how you made these?

   • Edit