Permutations Question
I have a permutations problem, and I'm calling on all interested math-types to give it a look.
There are M distinguishable containers -- {x_1, x_2, ... x_M}. Each container x_i must contain exactly c(x_i) objects, where the sum of the c(x_i) == N.
There are N objects, each of which belongs to exactly one of D classes {y_1, y_2, ... y_D} . Objects of the same class are indistinguishable. Each class y_i contains c(y_i) objects, where the sum of c(y_i) == N. Some classes may be empty,
How many ways are there to uniquely assign the objects to the containers?
This problem has got me stumped.
__Example__
Classes:
A: 3 objects
B: 1 objects
C: 0 objects
D: 2 objects
Containers:
X: capactity of 4
Y: capactity of 1
Z: capactity of 1
Assignments:
AAAB | D | D
AABD | A | D
AABD | D | A
AADD | B | A
AADD | A | B
....
quick clarification: how do the containers relate to the classes?eg. at the moment you could remove the 3rd line of your post without effecting the solution (?)
asjf at 2007-7-7 1:07:10 >
The classes are what distinguish objects from each other. You can also think of it as object repetition. The caveat is that object A must appear c(A) times, B must appear c(B) times, etcetera.
It sounds like you can just make a simple recursive program to figure it out.
Permute through all possible unique combinations to fill x_1 given the set of items
for each combination, recursively call on x_2 with remaining items (and x_2 passes to x_3... etc.)
The hardest part will probably be finding all unique subsets to fill a container, but it is doable. Good luck!
The recursive approach is computationally expensive, unfortunately. I need to do this for large numbers of variations of the problem (hundreds of thousands, potentially). I gots to find a better way. It's a good start though -- I ought to look into a generating function technique to simplify the results.
Well, even though it's expensive, if you want to print all possible solution, just generating this output will be expensive. If it turns out this problem has an output exponential to the size of the input (which I don't know if it does, but it might), the complexity of the algorithm will be intractable, meaning that there isn't any way to make a neat algorithm to simplify it.
However, if all you want is how many solutions are there (not a listing of all solutions), then there may still be hope.
Do you mind telling us a little more about the application for which this mathematical problem is supposed to be the solution. It is useful to know the context in which this problem is framed.
For example is there some reason that you need to know exact counts rather than close approximations?
When you state the problem as a theoretical math problem it seems to imply that only an exact answer will do. Then you reject a recursive computation (which is a perfectly good function to a theoretical mathematician) as too slow and point at the need to do this possibly hundreds of thousands of times.
It might be possible to give more help if the problem was exposed in its original frame work rather than boiled down into one tough little hard to crack mathematical nut.
I will tell you in advance that I do not expect there to be any simple formula for your problem.
Allow me to recast it into a form where the problem may be easier to visualize.
If you have M different classes and N different containers, any single solution to the problem can be viewed as an array with N rows and M columns. The array has integer values and A[i,j] is simply the number of elements of class i that sit in container j.
You give us two vectors of numbers, one is the list of the N capacities of the N containers and the other is the count of the amount of each of the M different object types.
If you write the N capacities at the ends of the rows, you can see that each row must sum to the capacity at the end of that row. Similarly, if you write the M different object counts along the bottom of the matrix you will see that those numbers repersent the column sums.
the range of any given cell in the matrix can be any integer from 0 to the minimum of either the row sum or the column sum that that particular cell belongs to.
So your problem is really one of counting matricies that have positive integer components that satisfy the constraints of haveing fixed row and column sums.
The reason that I am not particularly hopeful that you will find a nice simple closed form formula for the count is that if you look at just the subcase where the matrix is square and where all the row and column sums are all identical, you will see that what you are talking about is an enumeration of simple magic squares.
As I am sure that you know, people have been playing with magic squares for some time and I would have thought that if there were a simple form to calculate the number of magic squares that exist of any given order (which is just a sub case of your more general problem) that there would have been some mention of that formula in the recreational math literature.
I am not aware of any such result and that argues against there being a simple formula for your particular problem. Well, technically it only really argues that I am not very well read on the literature of recreational math.
Hopefully this characterization which is a slightly more symmetric restatment of your problem will be of some assistance.
None the less, I once again request that you fill us in on some of the details of why exactly we are working on this particular problem.
A Yahtzee AI -- I'd like to be able to calculate the probability of a given roll once it's happened, the probability of getting each winning combination ahead of time, etc. Particularly, I'd like to be able to calculate the probability of a getting a particular roll from an existing roll, knowing that there will be a certain number of rerolls. The technique I've arrived at involves enumerate through all the possible rolls (with indistinguishable dice), and calculating the probability of rolls of interest.
There's also another project I'm working on for a Dungeons and Dragons MUD, with a roll-checker to watch for player cheating.
> Allow me to recast it into a form where the problem> may be easier to visualize.> ...That's an excellent characterisation of the problem -- thanks. It may help me quite a bit.
unglaublich!
I started a novel once way back in 1975, when I was a grad student in math (it is unfinished of course) whose central theme involved developing an accurate computer model for playing Yahtzee perfectly. This was of course in the stone ages prior to the micro-computer revolution. I was thinking mainframes at the time. The title was the unwieldly "How Yathzee became the national passtime and destroyed the earth". Probably a good thing I never wrote it, it would be horribly dated and tedious at best.
Any way, let me dust off some of those old thoughts and get back to you on the Yahtzee player.
You might want to take a look at the analysis I did on the dice game of skunk. You can get to it through www.gottahack.com. T
That model of sloving games would work for Yahtzee as well, unfortunately it is on the limits of tractability. The count of states in the game of Yahtzee is about 24 Billion, meaning you would need an array of floats that size to do the calcualtion. Plenty of room on disk, hard to get than much memory.
However, if you are willing to back off just slightly from perfection the state table could be reduced and I'm sure a perfectly adequate player (meaning one that would do way better than any human) could be achieved.
However - ignoring all of that. If all you want to do is create the table that starting from any given roll and any given any target, like going for you full house, - it will tell you which dice to pick up and what your probability of achieving that target are - that is a perfectly tractable computation.
To be honest though, I think you would do just fine to calculate most of that on the fly. i.e. when the computer has a given hand, it just quickly picks up dice at random, and rolls in its head a million or so times (do this while the other player is deciding on his move) and compute not exact probabilities but likely probabilities. All it is looking for is to select among the 32 possible patterns of picking up dice and it wants to select the one that has the best expected payoff.
Yes, this is very inefficient compared with precomputing all that, but if it is fast enough, it saves all that memory. And basically the machinery that you must build to do this, all the code to score hands, etc, must be built regardless of whether you drive it systematically through the pre-computation or whether you use it on the fly.
Anyway, I'll be happy to kibitz on the design of a yahtzee AI
