title: How to tractably solve the assignment optimisation task
body: <p>I'm working on a script that takes the elements from <code>companies</code> and pairs them up with the elements of <code>people</code>.  The goal is to optimize the pairings such that the sum of all pair values is maximized (the value of each individual pairing is precomputed and stored in the dictionary <code>ctrPairs</code>).  </p>
  
  <p>They're all paired in a 1:1, each company has only one person and each person belongs to only one company, and the number of companies is equal to the number of people.  I used a top-down approach with a memoization table (<code>memDict</code>) to avoid recomputing areas that have already been solved.  </p>
  
  <p>I believe that I could vastly improve the speed of what's going on here but I'm not really sure how.  Areas I'm worried about are marked with <code>#slow?</code>, any advice would be appreciated (the script works for inputs of lists n&lt;15 but it gets incredibly slow for n > ~15)</p>
  
  <pre><code>def getMaxCTR(companies, people):
      if(memDict.has_key((companies,people))):
          return memDict[(companies,people)] #here's where we return the memoized version if it exists
      if(not len(companies) or not len(people)):
          return 0
  
      maxCTR = None
      remainingCompanies = companies[1:len(companies)] #slow?
  
      for p in people:
          remainingPeople = list(people) #slow?
          remainingPeople.remove(p) #slow?
          ctr = ctrPairs[(companies[0],p)] + getMaxCTR(remainingCompanies,tuple(remainingPeople)) #recurse
          if(ctr &gt; maxCTR):
              maxCTR = ctr
      memDict[(companies,people)] = maxCTR
      return maxCTR
  </code></pre>