Warehouse Picklist Algorithm

gistfile1.py

from collections import defaultdict
from copy import copy, deepcopy

WHS = {
    'ID1' : ['code1', 'code2', 'code3'],
    'ID2' : ['code2', 'code5', 'code3'],
    'ID3' : ['code6', 'code7', 'code8'],
    'ID4' : ['code3', 'code5', 'code6'],
}

class Node(object):
  def __init__(self, prod):
    self.prod = prod
    self.whs = []

  def add_whs(self, whs, nprod):
    self.whs.append((whs, nprod))

  def __str__(self, tablvl=1):
    st = self.prod + "\n"
    for name, node in self.whs:
      if node:
        st += "\t" * tablvl + name + ":"
        st += node.__str__(tablvl + 1) + "\n"

    return st

paths = []
min_cost = 99999
def find_min_paths(root, rem_prods, p_whs=defaultdict(set)):
  global paths, min_cost

  if len(p_whs) >= min_cost:
    return

  if not rem_prods:
    paths.append((len(p_whs), p_whs))
    min_cost = len(p_whs)
    return paths

  if not root:
    return paths

  rem_prods = copy(rem_prods)
  rem_prods.remove(root.prod)

  for whs, node in root.whs:
    l_whs = deepcopy(p_whs)
    l_whs[whs].add(root.prod)
    find_min_paths(node, rem_prods, l_whs)

  return paths

def find_min_path(root, prods):
  paths = find_min_paths(root, prods)

  paths.sort(key=lambda p: p[0])

  return paths[0]

prods = set()
whs = WHS

for w_id, prod_list in whs.items():
    prods |= set(prod_list)

def build_tree():
  global prods, whs

  avail = defaultdict(list)
  for prod in prods:
    for w_id, prod_list in whs.items():
      if prod in prod_list:
        avail[prod].append(w_id)

  def _add_elems(_prods):
    if not _prods:
      return

    prod = _prods[-1]
    _prods = _prods[:-1]

    node = Node(prod)
    for w_id in avail[prod]:
      node.add_whs(w_id, _add_elems(_prods))

    return node

  return _add_elems(list(prods))

root = build_tree()
print find_min_path(root, prods)