Best way to search/filter (potentially several billion) combinations of items from multiple lists or arrays

Question

I'm trying to write a program to optimize equipment configurations for a game. The problem is as follows:

There are six different equipment slots for a character to place an item. This is represented by 6 lists of individual items for each slot in the code containing all of the equipment owned by the player altogether.
The program will calculate the total stats of the character for each possible combination of equipment (1 from each list). These calculated stats can be filtered by specific stat min/max values and then also sorted by a specific stat to pinpoint a certain target set of stats for their character.
The program should be able to perform these queries without running out of memory or taking hours, and of course, the main problem is sifting through several billion possible combinations.

I'm not sure what the name of any supporting data structures or search algorithms to accomplish this would be called (in order to do more research towards a solution). I have come up with the following idea but I'm not sure if i'm on the right track or if someone can point me in a more effective direction.

The idea i'm pursuing is to use recursion, where each list (for each possible equipment slot) is set into a tree structure, with each progressive list acting as a child of the last. E.G.:

Weapons List
|
-----Armor List
     |
     ------Helm List... etc

Each layer of the tree would keep a dictionary of every child path it can take containing the IDs of 1 item from each list and progressively calculating the stats given to the character (simple addition of stats from weapon + armor + helm as it traverses the tree and so on...)

When any stat with a min/max filter being applied hits it's boundary for that stat (namely, if the stat goes over the maximum before it reaches the bottom layer of the tree, it eliminates that "path" from the dictionary thus removing that entire leg of possible results from being traversed).

The main goal here is to reduce the possible tree paths to be traversed by the search algorithm and remove as many invalid results before the tree needs to calculate them to make the search as fast as possible and avoid any wasteful cycles. This seems pretty straightforward when removing items based on a "maximum" filter since when adding each item's stats progressively we can quickly tell when a stat has crossed it's expected maximum -- however when it comes to stopping paths based on a minimum total stat, I can't wrap my head around how to predict and remove these paths that won't end up above the minimum by the sixth item.

To simplify the idea, think of it like this:

I have 3 arrays of numbers

[X][0][1][2]
[0] 5  3  2
[1] 1  0  8 
[2] 3  2  7
[3] 2  1  0

I want to find all combinations from the 3 arrays (sums) that are minimum of 9 and maximum of 11 total. Each array must select at least but no more than 1 item and the sum of those selected values is what is being searched. This would need to be able to scale up to search 6+ arrays of 40+ values each essentially. Is the above approach on the right track or what is the best way to go about this (mainly using c#)

Great question! Are you currently using a `multi-dimensional array [x,y]` or an `array of arrays [x][y]`? The latter is much faster in general and there's a great post on it [here](https://stackoverflow.com/questions/597720/what-are-the-differences-between-a-multidimensional-array-and-an-array-of-arrays) to get you started. — Hazel へいぜる, Sep 19 '19 at 20:56
@PerpetualJ Whereas C# jagged arrays are faster than multi-dimensional arrays, that speed difference is a single-digit factor. The OP's problem is combinatorial. Using a faster array implementation won't save enough time to make a dent in that kind of problem. — Jim Mischel, Sep 19 '19 at 22:28
So basically you want to identify all the valid combinations of items from the arrays. If you have n arrays with k items each, the worst case complexity is O(n^k) if you're using [Brute-force search](https://en.wikipedia.org/wiki/Brute-force_search). That article has some ideas on optimizations and alternatives, including the idea you're thinking about to reduce the search space. — Jim Mischel, Sep 19 '19 at 22:55

score 0 · Answer 1 · answered Sep 20 '19 at 04:06

You should be able to filter out a lot of items by using a lower and upper bound for each slot:

var minimum = slots.Sum(slot => slot.Minimum);
var maximum = slots.Sum(slot => slot.Maximum);

foreach (var slot in slots)
{
    var maxAvailable = maximum - slot.Maximum;
    var minAvailable = minimum - slot.Minimum;
    var filtered = slot.Items
         // If we choose the strongest item in all the other slots and it's still below the minimum
        .Where(item => item.Value + maxAvailable >= request.MinimumValue)
        // If we choose the weakest item in all the other slots and its still above the maximum
        .Where(item => item.Value + minAvailable <= request.MaximumValue);
}

After doing this, you can guarantee that all your combinations will be above the requested minimum, however some combinations may also be above the requested maximum, so combine this with the logic you have so far and I think you should get pretty optimal performance.

Best way to search/filter (potentially several billion) combinations of items from multiple lists or arrays

1 Answers1