Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I am writing an app in javascript to try to figure out item builds for characters in a video game. There are about 25 top-tier items, and you can carry 6 at a time. They have very different effects, which leads me to believe that while one item may seem like it isn't very good by itself, it can become much stronger when combined with others.

Questions:

  1. How can I get a list of all the different distinct combinations of 6 items? How many combinations will there be? Is it just 25c6 (~134k)? Or do I need to remove duplicates? (Sorry, I've been out of math class awhile.)

  2. How would you implement something like this in Javascript? Is there already a math library that can do this?

  3. Does it seem possible to brute force calculate the damage of all the possible combinations and save the top item combinations? If not, is there a better algorithm to find strong combinations?

EDIT: Here's my code based on everyone's suggestions:

function getAllCombinations(n, k, callback)
{
    var iterate = function(remaining, args)
    {   
        var len = args.length;
        for (var i = args[len - 1]; i < n; i++)
        {
            args.splice(len);
            args[len - 1] = i;
            if (remaining)
            {
                args.push(i);
                iterate(remaining - 1, args);
            }
            else
            {
                callback.apply(null, args);         
            }
        }        
    }
    iterate(k - 1, [0]);
}

var itemsCount = 25;
var itemSlots = 6;
getAllCombinations(itemsCount, itemSlots, function(a, b, c, d, e, f)
{   
    // calculateDamage(hero, arguments);
});
share|improve this question
2  
The answer to question 3 depends a lot on the details of how the items interact and I don't think anything much can be said in full generality. (Even for apparently simple interactions the resulting problem can end up being NP-complete: see math.stackexchange.com/questions/10414/… .) Anyway, this seems like more or less a programming question. The answer to the math part of this question is: yes, it's ${25 \choose 6}$. This isn't too many combinations, so brute force should be alright anyway. –  Qiaochu Yuan Apr 26 '11 at 22:49
    
Probably belongs on SO. –  Ben Alpert Apr 26 '11 at 23:04

2 Answers 2

up vote 5 down vote accepted

The brain-dead way to enumerate all combinations would be to nest 6 for loops, one loop for each item slot. In the innermost loop, you'd calculate the total effectiveness for that gear-set and then take a max. This is pretty flexible, since you can change your measurement and re-run the program at will.

However, this might be a bit slow. There are likely less than ${25 \choose 6}$ item combos due to the fact that you wouldn't want to (say) equip two helms, but it's pretty close to that number. The actual number is $i_1 i_2 i_3 i_4 i_5 i_6$ where $i_j$ is the number of choices for slot $j$.

Javascript isn't the fastest platform (although it's getting faster... a ton of research is going into optimizing it these days). I would say try it and see if it's fast enough on a commodity PC.

To make your program faster, consider throwing out combinations that are clearly inferior before doing the inner loops. This is a bit harder, but it can be done.

This doesn't feel like a math problem. :)

Updated:

So ${25 \choose 6} = 177,100$ which is calculated the quick way using the definition, or you can do it the slow way and check how long it takes to implement the for loops from Yuval's answer, modified slightly. Copy the code below into a web page and load it with Javascript enabled...

<HEAD>
  Calculating...
</HEAD>


<BODY>
  <SCRIPT>
    x= 0;
    for (i0 = 0; i0 < 25; i0++)
      for (i1 = i0; i1 < 25; i1++)
        for (i2 = i1; i2 < 25; i2++)
          for (i3 = i2; i3 < 25; i3++)
            for (i4 = i3; i4 < 25; i4++)
              for (i5 = i4; i5 < 25; i5++)
                x++;
     document.write(x);
  </SCRIPT>
</BODY>

Not exactly HTML5 compliant, but it gets the job done. Also, I would expect your inner function will be a bit more complex than x++ but this gives you a rough idea. For me, this code runs virtually instantly.

Note that the answer output here is 593,775 which is not ${25 \choose 6}$. See the comments as to why this change was made.

share|improve this answer
    
wouldnt this create a lot of duplicate combos? a,a,a,a,a,b vs b,a,a,a,a,a –  Shawn Apr 26 '11 at 23:07
    
I was assuming that you have a set of helm, shoulder, bracer, glove, chest, and leg items and that you couldn't equip a given item other than in its proper slot. If you want to avoid repetitions, use the code above which will give you the 177,100 unique sets of 6 items taken from 25. –  Fixee Apr 26 '11 at 23:14
    
ok i tried that and it's working however it doesn't include a,a,a,a,a,a for example. it seems like it doesnt every have the same item twice. how could i fix that? –  Shawn Apr 26 '11 at 23:19
    
btw i will probably dynmically add the for loops to support any number of item slots ;p –  Shawn Apr 26 '11 at 23:21
2  
The number of possibilities is $\binom{30}{6}$. Here $30 = 25 + 6 - 1$. –  Yuval Filmus Apr 27 '11 at 0:17

The simplest way is to use nested loops, like this (in C):

for (i0 = 0; i0 < 25; i0++)
  for (i1 = i0 + 1; i1 < 25; i1++)
    for (i2 = i1 + 1; i2 < 25; i2++)

And so on. Maybe you already have an iterator for it in javascript.

You can optimize it slightly by improving the upper bounds, but it's error-prone and makes only a small difference.


If you have a built-in heap in javascript then you can use one to keep only the highest N items, then you don't need to sort anything (though sorting 134k numbers is completely feasible).


To check whether such brute forcing is feasible, calculate the time it takes you to compute one combination, and multiply it by 134k.

In order to calculate the time, use a timer (if javascript has one), and compute the combined damage for M randomly chosen combination, where M is "big" but "much smaller" than 134k.

share|improve this answer
    
this looks almost correct, i tested it, but there is no duplicate item sets, for example, a,a,a,a,a,a or a,b,a,a,a,a –  Shawn Apr 26 '11 at 23:20
    
just delete the "+1"s. –  Yuval Filmus Apr 27 '11 at 0:16

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.