Math

[nonethefewer]

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.

Comments

[rosefox]

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?

[vatine]

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".

[metahacker]

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.)