Complex permutations without repetition

Question

I am trying to create a tool for a game called Monster Hunter (for personal-use)). I have worked with permutations before, but nothing this complex so i am totally stuck.

In the game you wear 5 pieces of armor. Each piece has skill points for one of many different skills. If you have 10+ skill points in a particular skill after calculating the whole set, you earn that skill.

Example:

Foo Head: Attack +2, Guard + 2
Foo Chest: Defense + 5    
Foo Body: Guard + 2, Attack + 5, Defense +2
Foo Arm: Attack + 3, Speed + 4
Foo Legs: Attack + 5, Guard + 6, Defense + 3

The above set would result in 10+ in Attack, Defense, and Guard (not speed).

I would like to figure out how to find all combinations of armor pieces given 2-3 user-specified skills. So if you selected "Attack" and "Speed", it would give you all possible combinations of 5 pieces of armor that will result in +10 in both "Attack" and "Speed". There are about 60 different items for each of the 5 categories.

I know I can use LINQ to filter each of the 5 categories of armor parts so that I only get back a list of all the items that include one of the 2 specified skills, but I am lost on how to do the permutations since I am juggling 2-3 user-specified skills...

I wish I had working code to show, but I am so lost at this point I don't know where to start. I am not looking for the answer, per se, but advice on how to get there. Thanks.

Answer 1

1) I would try to find just for 1 skill, then filter that item set for the second / third

2) to avoid taking too much time/memory/recursion : i would sort the 5 * 60 items based on that only skill. Then i would create combinations by seeking the ones that add up to more than 10, starting from the upper skills, and stopping either when 10 is reached, or when it won't be reached.
The function that builds all combinations would look like : 1 : if we have total item skill >10 : all combination with other items are ok . stop. 2 : if current item skill is count <10 seek in the array for next biggest item for a not weared piece.
if in the array we reached 0 OR we reached a value such that (current count + value*number of piece type left ) <10 then its time to stop :-)
Otherwise add its skill count, note piece of armor type as used, then call your function for all items that might match.

well i may not be precise enough but you see the idea : use condition for the call to avoid exploding recursivity. Because 60*60*60*60*60 is a lot. and (quick)sorting 5*60=300 items is nothing.

To store your combinations, you might want to add the 'anything goes' case, to avoid storing / computing too many combination for nothing. (ex : if you have Carmak's Magical Hat, you have +100 in Coding, and you can dress any way you want, the bugs will dye ! :-) )