Skip to Content
 

Combinatorial Mathematics

7 replies [Last post]
Wed, 03/02/2011 - 14:57
Yamahako
Offline
Joined: 12/01/2010

I hope this is the right place to put this.

Certain parts of probability and combinatorial mathematics makes a lot of sense to me. But some I think there should be a short cuts I can do (aside from brute forcing) - but I'm not sure what they are. And in certain cases, I think there should be a way for some software to automate the manual process I go through in order to figure out - for example - all the potential cards/tiles I could make that are a combination of the various configurations of elements I have designed.

So I have a two part question - one specific, one generic.

First: How would you go about figuring out all of the possible 6-sided dice that can have any non-negative value on the faces (including 0), but that the sum of all the faces is 12? For purposes of this exercise the elements are non-exclusive and the order of the elements is irrelevant (ie 12,0,0,0,0,0 and 0,12,0,0,0,0 are identical for this)

Since as numbers become decided, the options become fewer (but not a simple removal from a list like the formula #insetA*(#insetA-1)...for each slot [as it were] would be) I don't think the formulas I know can account for that.

For this problem the first side has a potential 13 values, if it is 12 though, each other side as only 1 possible value. If its 11, also there is only 1 possible set of remaining sides. If its 10 though, there are 2 sets of remaining sides. 9 has 3 sets of remaining sides, and 8 has 5 and so on.

Is there a formula to discover this and problems like it (I could likely generate a formula for this problem specifically, but that wouldn't be helpful for future problems.)

Second: Has anyone come across a tool that allows you to generate the full set of outcomes for such a problem? Knowing how many are available is interesting for balance reasons - expansion possibilities and stuff like that - but actually generating them (to avoid the tedious process of hand building a full set of every potential) would be incredibly useful.

Top
Wed, 03/02/2011 - 16:27
#1
truekid games
truekid games's picture
Offline
Joined: 10/29/2008
well, for your initial stated

well, for your initial stated problem, i would actually just brute-force it on paper- because the time spent doing that is probably distinctly less than the time it takes finding a relevant formula. and it's a pretty specific issue for there to be a tool that would handle it, but that doesn't mean there isn't one somewhere.

that said, http://www.anydice.com is pretty helpful for a lot of similar game-design uses, though not that specific one.

Top
Wed, 03/02/2011 - 17:58
#2
Yamahako
Offline
Joined: 12/01/2010
anydice.com looks awesome -

anydice.com looks awesome - and is great when I'm taking the crazy dice I made and am seeing what the results are when they are rolled against each other!

I did the brute force thing, on that problem already - but the whole time I was doing it - i was SURE there had to be a way to solve it instead of just working it out. It's sometimes complicated to make sure that you are getting every combination when you do it by hand. If I did it correctly - there were only 49 solutions to that problem.

Here's another one that that maybe is solvable that I HAVEN'T done by hand due to the sheer size of the solution.

Imagine a Hex Tile. Each side of a hex tile can either have a road, or no road. Each road can form a path from its side to any other side or dead end (not connect to another side), but the roads cannot cross each other - though multiple roads can go to a particular other side.

So for example, if the sides are numbered clockwise 1,2,3,4,5,6 A path from 1 to 4 would prevent a path going from 2 to 5, but not one from 2 to 4, or from 5 to 4.

Even if I ignore the exclusionary element of the problem - but keep that each individual path is unique - I run into issues with the solution - is it a simple 3^6? Or is it 3^6 + 3^5 + 3^4 + 3^3 + 3^2 + 3^1? Or am I off the mark entirely.

One Solution I think I know is if the options are a road that goes to the center (thus touching all other center roads), or a road that dead ends, or no road, it should be a simple 6^3 possible tiles right?

Top
Thu, 03/03/2011 - 02:57
#3
kos
Offline
Joined: 01/17/2011
Combinations

On the question of dice faces adding to 12:
I had a go at this but I don't think the answer is 49 (unless I've misunderstood the question). I spent some time on the problem, and while I haven't arrived at a solution it looks like the number would be in the order of a few hundred combinations. For example, using only 3 faces (while all the other faces stay at zero), I calculated more than 100 combinations.

On the question of a tool to calculate these things:
Any spreadsheet application.

On the question of the roads on tiles:
The first phrasing of the question would lead to an enormous number of potential tiles (not to mention that many of them would be impractical to draw on a normal-sized hex tile). Without doing the maths, I think the solution would number into many thousands of unique tiles.
The second phrasing of the question is simpler, and also more practical to draw. The number of combinations would be near to but less than 3^6. The reason it would be less is that a hex can be rotated without becoming unique. (For example, the 6 combinations of "1 dead end" are actually the same tile.)

As an aside:
I originally misinterpreted your description of the tiles and calculated a solution for something you didn't ask. But I'll describe my assumptions anyway and then the solution. (I've seen a game that used hex tiles almost exactly as per your second solution, and while the mechanics worked fine I didn't like the visual appeal because it created jagged corners rather than curves.)
- A tile can have at most one dead-end. (I pictured this as terminating in the middle of the tile, so if there were two "dead-ends" they would meet in the middle and thus become a road.)
- A side can have at most one road. (I pictured this as curving between the two sides, without passing through the middle.)
- The roads cannot cross.
Under these assumptions, there are only 25 possible tiles.
- 1x one dead-end
- 3x one road
- 8x two roads
- 2x three roads
- 8x one dead-end and one road
- 3x one dead-end and two roads
I may have missed a couple, but you can see the final number is still quite small.
If multiple roads can connect to the same side, the combinations increase substantially.

Regards,
kos

Top
Thu, 03/03/2011 - 04:54
#4
Zomulgustar
Offline
Joined: 07/31/2008
The magic phrase you want to

The magic phrase you want to google is 'numerical partitions'. In particular, for your first case you're essentially trying to find all the numerical partitions of 12 into 6 or less parts. Google or Wikipedia should turn up a better definition than I can spout off the top of my head at 2:30 in the morning, but I'll try and follow up when awake. ^_^ Last I checked, the Combinatorial Object Server is still up and running, and should be able to generate these for you in a more general case, and I think I saw a nice open-source implementation in Python a while back...I'll try and dig it up later. Despite some recent theoretical discoveries regarding recurring patterns, IIRC the usual trick for generating all of them is to define a lexicographic order of all possible partitions, and then a method which, given a partition, generates the next one in that order. In short, let the computer do it. ^_^

I found 58 for your initial problem, but again, should double-check when awake.

2 2 2 2 2 2
3 2 2 2 2 1
3 3 2 2 1 1
3 3 2 2 2 0
3 3 3 1 1 1
3 3 3 2 1 0
3 3 3 3 0 0
4 2 2 2 1 1
4 2 2 2 2 0
4 3 2 1 1 1
4 3 2 2 1 0
4 3 3 1 1 0
4 3 3 2 0 0
4 4 1 1 1 1
4 4 2 1 1 0
4 4 2 2 0 0
4 4 3 1 0 0
4 4 4 0 0 0
5 2 2 1 1 1
5 2 2 2 1 0
5 3 1 1 1 1
5 3 2 1 1 0
5 3 2 2 0 0
5 3 3 1 0 0
5 4 1 1 1 0
5 4 2 1 0 0
5 4 3 0 0 0
5 5 1 1 0 0
5 5 2 0 0 0
6 2 1 1 1 1
6 2 2 1 1 0
6 2 2 2 0 0
6 3 1 1 1 0
6 3 2 1 0 0
6 3 3 0 0 0
6 4 1 1 0 0
6 4 2 0 0 0
6 5 1 0 0 0
6 6 0 0 0 0
7 1 1 1 1 1
7 2 1 1 1 0
7 2 2 1 0 0
7 3 1 1 0 0
7 3 2 0 0 0
7 4 1 0 0 0
7 5 0 0 0 0
8 1 1 1 1 0
8 2 1 1 0 0
8 2 2 0 0 0
8 3 1 0 0 0
8 4 0 0 0 0
9 1 1 1 0 0
9 2 1 0 0 0
9 3 0 0 0 0
10 1 1 0 0 0
10 2 0 0 0 0
11 1 0 0 0 0
12 0 0 0 0 0

Top
Thu, 03/03/2011 - 10:28
#5
Yamahako
Offline
Joined: 12/01/2010
I personally came up with 49

I personally came up with 49 possible dice - I need to go through Zomulgustar's list to see which ones of those I was missing - but that's why I wish I knew how to get a mathematical answer rather than basing it on my flawed ability to brute for it. For what its worth, the dice I found are here:
https://spreadsheets0.google.com/ccc?hl=en&key=t185ct-48krN7FtLwCi4d5w&h...
I'm going to add the ones I was missing and highlight them when I get some time.

For the tiles - a programmer friend of mine I posed this question to had the last (last) solution as you - but I did indeed intend that it would be possible for each side to be able to have multiple roads going out from it.

I made a (terrible) drawing that shows some examples of both possible tiles.

I think you're right about the tile rotations - so it would have been 6^3/6 (or just 6^2) I often forget about rotations.

I agree that in tile version 1 - it would be in the order of thousands of solutions.

https://docs1.google.com/drawings/edit?id=1Y3zap_rsYKTb34RbBZsmqsCOT5o2n...

Top
Thu, 03/03/2011 - 11:16
#6
Yamahako
Offline
Joined: 12/01/2010
"The magic phrase you want to

"The magic phrase you want to google is 'numerical partitions'"

YES! Thank you this is perfect - and while doesn't cover every kind of problem I'm trying to solve - this will be extremely helpful! I can't wait to engross myself in this.

And this "http://www.theory.csc.uvic.ca/~cos/" Looks like it's going to be invaluable for some of this kind of work!!

I wonder how useful a suite of tools that do these kinds of things would be to game designers. I've already got some software I designed that a friend of mine coded to take spreadsheets and build PNG files with text and pictures to create me print sheets of cards... and its collaborative capable and web-based (and easy to use) if I could incorporate some of this other stuff into a single package I wonder if it would be useful to anyone but me :-)

Top
Thu, 03/03/2011 - 20:27
#7
kos
Offline
Joined: 01/17/2011
Dice and tiles

Yamahako wrote:
I personally came up with 49 possible dice - I need to go through Zomulgustar's list to see which ones of those I was missing - but that's why I wish I knew how to get a mathematical answer rather than basing it on my flawed ability to brute for it. For what its worth, the dice I found are here:
https://spreadsheets0.google.com/ccc?hl=en&key=t185ct-48krN7FtLwCi4d5w&h...
I'm going to add the ones I was missing and highlight them when I get some time.

I stand corrected. I was trying to come up with a generalised formula to solve the problem for any size dice with any target number, but obviously there was an error in my calculations somewhere.

Yamahako wrote:
I think you're right about the tile rotations - so it would have been 6^3/6 (or just 6^2) I often forget about rotations.

Note that maximum for "option 2" would be 3^6 (729) not 6^3 (216).
So the solution would be somewhere between 121 and 729 depending on how many of the tiles are rotations of each other. If an approximation is sufficient for your needs, you could just take the mid-point of 425.

*But* ... I just realised this number doesn't take into account multiple roads connecting to each side. With multiple roads, this number would go up again. Actually calculating the number would get very difficult and further complicated by rotations.

For example, a tile with 3 roads terminating on sides 1, 3, and 5 would have 2 unique combinations (all 3 sides connected; any 2 sides connected (the others are rotations of this)). However, a tile with 3 roads terminating on sides 1, 2, and 4 would have 4 unique combinations (all 3 sides connected; 1-2 and 1-4; 1-2 and 2-4; 1-4 and 2-4).

At a rough guess I'd put the total number between 1000 and 2000, after applying fudge factors for the rotations and the multiple roads connecting to the same side.

Regards,
kos

Top
Syndicate content


forum | by Dr. Radut