CODEWITHSUNDEEP
pythonalgorithmpermutation
Jeremy Parks
Jeremy Parks

Reputation: 111

How to generate permutations while culling bad sequences?

Problem Statement: I have 150 objects with weights and values attached to them. The weights of the objects might change based on the order they are selected, typically about 70-80 items are selected. I can only select up to a maximum weight, so all permutations that start with the same sequence need to be skipped once I've found a sub-solution with that sequence. The goal is to maximize value.

I can trivially create all permutations with:

from itertools import permutations
for i in permutations(list(range(150))):
    # do something with i

However this will create many sequences that I don't need to check. I can also restrict permutation length with r such that

from itertools import permutations
for i in permutations(list(range(150)), r=80):
    # do something with i

However for really bad sequences there will still be a lot of redundant checks. Additionally this could stop before a 'best' solution.

I could do something like

from itertools import permutations
v = []
for i in permutations(list(range(150)), r=80):
    if v and v == i[:len(v)]:
        continue
    # do something with i
    v = i # would be some optimal subset of i

However this still takes a very long time to run as Python is still generating and checking the sequences. Any thoughts on how I should approach this? Ideally I would be able to run the checks in parallel.

More Background: I am attempting to create optimized resource graphs for a game called Black Desert Online( graph example at somethinglovely.net/bdo/ ). The graph has ~150 resource nodes that can each connect to a subset of 14 root nodes. Intermediate nodes on the graph have weights associated with them. Each city has a maximum amount of nodes it can be connected to and there is an additional weight cost for connecting a resource node to a city. I was not having success with random graph generation coupled with a genetic algorithm for 'finding' an optimal solution. Additionally just making greedy choices leads to a sub-optimal solution. I am currently stumped on how to generate a brute force + comprehensive solution that will run in a reasonable period of time(reasonable being within a day on a reasonable desktop computer.

Upvotes: 0

Views: 293

Answers (1)

Prune
Prune

Reputation: 77837

Go through the inventory list, one item at a time, and try packing both with and without that item (two recursions). Report a solution when we reach one of two points:

  1. No more items left to consider
  2. The remaining list fits within our weight budget.

This takes care of the culling, by proactive construction.

Code:

items = [
    # Description, weight
    ("petrol", 10),
    ("clothes", 8),
    ("tents", 7),
    ("beer", 16),
    ("food", 20),
    ("teddy bear", 3),
    ("tank", 25),
    ("skin lotion", 2),
    ("library", 17),
    ("mortar", 9),
    ("cut lumber", 12),
    ("sports gear", 14),
]

limit = 20

def load(inventory, max_weight, current):

    still_okay = [item for item in inventory if item[1] <= max_weight]
    if len(still_okay) == 0:
        # Can't add any more; emit solution and back up
        print "RESULT", current
    else:
        # If the rest of the list fits in our weight budget,
        #   take everything.
        if sum([item[1] for item in still_okay]) <= max_weight:
            print "RESULT", current + still_okay
        else:
            item = still_okay.pop()
            # recur on two branches: one each with and without this item
            load(still_okay, max_weight - item[1], current + [item])
            load(still_okay, max_weight, current)

load(items, limit, [])

Output:

RESULT [('sports gear', 14), ('teddy bear', 3), ('skin lotion', 2)]
RESULT [('cut lumber', 12), ('skin lotion', 2), ('teddy bear', 3)]
RESULT [('cut lumber', 12), ('teddy bear', 3)]
RESULT [('cut lumber', 12), ('tents', 7)]
RESULT [('cut lumber', 12), ('clothes', 8)]
RESULT [('mortar', 9), ('skin lotion', 2), ('teddy bear', 3)]
RESULT [('mortar', 9), ('skin lotion', 2), ('tents', 7)]
RESULT [('mortar', 9), ('skin lotion', 2), ('clothes', 8)]
RESULT [('mortar', 9), ('teddy bear', 3), ('tents', 7)]
RESULT [('mortar', 9), ('teddy bear', 3), ('clothes', 8)]
RESULT [('mortar', 9), ('tents', 7)]
RESULT [('mortar', 9), ('clothes', 8)]
RESULT [('mortar', 9), ('petrol', 10)]
RESULT [('library', 17), ('skin lotion', 2)]
RESULT [('library', 17), ('teddy bear', 3)]
RESULT [('skin lotion', 2), ('teddy bear', 3), ('tents', 7), ('clothes', 8)]
RESULT [('skin lotion', 2), ('teddy bear', 3), ('clothes', 8)]
RESULT [('skin lotion', 2), ('teddy bear', 3), ('petrol', 10)]
RESULT [('skin lotion', 2), ('beer', 16)]
RESULT [('skin lotion', 2), ('tents', 7), ('clothes', 8)]
RESULT [('skin lotion', 2), ('tents', 7), ('petrol', 10)]
RESULT [('skin lotion', 2), ('petrol', 10), ('clothes', 8)]
RESULT [('teddy bear', 3), ('beer', 16)]
RESULT [('teddy bear', 3), ('tents', 7), ('clothes', 8)]
RESULT [('teddy bear', 3), ('tents', 7), ('petrol', 10)]
RESULT [('teddy bear', 3), ('clothes', 8)]
RESULT [('teddy bear', 3), ('petrol', 10)]
RESULT [('food', 20)]
RESULT [('beer', 16)]
RESULT [('tents', 7), ('clothes', 8)]
RESULT [('tents', 7), ('petrol', 10)]
RESULT [('petrol', 10), ('clothes', 8)]

Upvotes: 1

Related Questions