xtina: (Default)
I run into wacky math things while I play my pointless games.

The setup:

I have a set of monsters I can use. They each cost a certain, different, amount of creds to play. I have a maximum amount of creds I can spend. The order of monsters I play is relevant.

What is the formula for determining all the possible permutations?

Don't tell me there isn't one, there must be one.

Date: 2017-05-28 02:10 (UTC)From: [personal profile] rosefox
rosefox: Green books on library shelves. (Default)
So something like

Monster A costs 1 credit
Monster B costs 2 credits
Monster C costs 3 credits
Monster D costs 3 credits

and you have seven credits and want to know all the possible ways to spend them?

Date: 2017-05-28 14:00 (UTC)From: [personal profile] vatine
vatine: Generated with some CL code and a hand-designed blackletter font (Default)
If we ignore the different costs for now, the number of permutations of N distinct items from M is M! / (M - N)!. If you can choose the same monster multiple times, it would probably end up being something like M to the power of N. Here N is approximated as "your available funds" divided by "the average cost of monsters you're going to play".

Generating all of them should boil down to looping through the set of monsters, stick it in the "list of monsters used so far" list, then pass that list and the set with the monster removed recursively done until either "all onsters used" or "funds used up".

Date: 2017-05-28 16:09 (UTC)From: [personal profile] metahacker
metahacker: And then a miracle occurs... (You need to be more explicit in step 2, here!)  (miracle)
There's an algorithm for generating them, but not a fast one. This is the knapsack problem, which is NP complete...so the "obvious" solution is also the fastest one. (Basically, generate each possible combination in order.)

September 2017


Most Popular Tags

Style Credit

Page generated 2017-09-19 11:49
Powered by Dreamwidth Studios