Combinatorial explosion magnitude?

A place to discuss the implementation and style of computer programs.

Moderators: phlip, Moderators General, Prelates

Posts: 1
Joined: Sat Dec 21, 2013 7:05 am UTC

Combinatorial explosion magnitude?

Postby Kaliedo » Sat Dec 21, 2013 7:27 am UTC

So, one idea I've been tossing around is making a simple game about combining things.
You start off with ten items, and combining any two will produce a single new item that can, in turn, be combined with other items, either items you've made by combining other objects, or the starting objects.

I've tried searching around, but I can't figure out the math to predict the number of possible items, does anyone have an idea?

Posts: 477
Joined: Sun Jul 05, 2009 6:56 pm UTC

Re: Combinatorial explosion magnitude?

Postby mr-mitch » Sat Dec 21, 2013 11:25 am UTC

Essentially each new object is a product of the starting objects that have been used?

If the order doesn't matter, then it's just the number of subsets, 2n for n basic items.

If the order does matter and there's only ever one result, then it's the number of permutations of each choice, sum_{k=0}^{n} k! (n choose k) which according to wolfram alpha is [e Gamma(1+n,1)] and is bounded above by n! 2^n... but that's a silly bound.

If there can be multiple results for the same ordering, then I've no idea lol. You could probably "make" multiple results dependent on a special other independent set of items and then get at the result that way (and would be bounded above by (n+m)! 2^(n+m)... but that bound is probably even more silly).

Posts: 3
Joined: Mon Dec 09, 2013 11:45 pm UTC

Re: Combinatorial explosion magnitude?

Postby drowdemon » Sat Dec 21, 2013 9:39 pm UTC

I think that if you can combine items that are not just the original ones, then it should be unlimited. For example, if you have 3 items A,B,C, and a combination is simply concatenation, then you can put A and B together to get AB. Then you do A and C to get AC, then you do AB and AC to get ABAC. Then you add ABAC and B and get ABACB, and so on. If you can add 'n-k' level items to 'n' level items (number of letters being n) then it should go on forever. You could get item ABAAAAAAAAAAA...

Or am I misunderstanding something?

Posts: 194
Joined: Tue Sep 25, 2007 9:10 pm UTC
Location: Belgrade, Serbia

Re: Combinatorial explosion magnitude?

Postby bittyx » Sun Dec 22, 2013 8:26 am UTC

This sounds like one of the many Alchemy games available for Android (and no doubt, other platforms, it's just that I've played these, so I know about them). Don't know if this helps, but perhaps you can see how/what they implemented, and maybe get some ideas?

User avatar
Poster with most posts but no title.
Posts: 11128
Joined: Sat Jan 27, 2007 7:27 pm UTC
Location: E pur si muove

Re: Combinatorial explosion magnitude?

Postby Yakk » Tue Jan 07, 2014 1:00 am UTC

There are 45 'tier 2' items possible, assuming order does not matter, and duplicates are not valid.

Pairs of these and the original 10 come to 55*27-45=1485-45=1440 new tier 3 items.

Pairs of those and previous items comes to 1485C2-1440=big.

It continues to explode.
One of the painful things about our time is that those who feel certainty are stupid, and those with any imagination and understanding are filled with doubt and indecision - BR

Last edited by JHVH on Fri Oct 23, 4004 BCE 6:17 pm, edited 6 times in total.

Return to “Coding”

Who is online

Users browsing this forum: No registered users and 3 guests