title: Java - Rule-based sorting using bellman-held-karp algorithm
body: <p>I asked the following question on CS SE, and have no idea as to how to implement the answer in java (let alone make out what it is actually saying):</p>
  <p>I am trying to plant a row in a garden. Certain plants are good for some plants and bad for others, and I am trying to find the best order of plants: most adjacent friends and no adjacent foes, as defined in this table (I have one of each):</p>
  <pre><code>Num Vegetable     Friends      Foes
  1   Watermelon    7,4,3        8,6
  2   Tomatoes      9,8,6,5,1    7
  3   Sunflowers    7,6,11  
  4   Zucchini      9,7,3   
  5   Eggplant      9,6,2        7,10
  6   Cucumbers     9,7,3        8,1
  7   Corn          8,6,4,3,1    5,2
  8   Cantaloup     7,4,3        6,1
  9   Bell peppers  6,5,11,10,2 
  10  Swiss chard   2            5
  11  Rhubarb       9,3 
  </code></pre>
  <p>How do I find the arrangement?</p>
  <p>&quot;Jakube&quot; answered:</p>
  <blockquote>
  <p>You can solve such a problem by simply iterating over all n! different
  permutations, and checking each if any of the arrangements is allowed
  and how good it is. This has complexity O(n⋅n!).</p>
  <p>Much faster (but still exponential complexity) will be a variation to
  the Bellman–Held–Karp algorithm. Compute for each pair (V,v) with V
  being a subset of all vegetables and and v∈V, if it is possible to
  arrange the vegetables V in a way such that v is the last one and what
  it's best value is. You can define a recursive formula for this
  function, and apply dynamic programming, like in the BHK algorithm.
  That should run in O(n<sup>2</sup>⋅2n).&quot;</p>
  </blockquote>
  <p>I originally asked the question for a case where I had one of each, but now realize that I need an answer which can take more an occasional duplicate. I am not sure if the answer he gave is applicable to a case where I have more than one of a given plant.</p>