Algorithm for optimal rule-based arrangements?

Question

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):

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 

How do I find the arrangement? Sort them using an algorithm? The title was my best guess at the answer. I am trying to understand the thought process and the implementation.

Answer 1

As @Steven wrote, this problem is NP-hard. However that doesn't mean that you can't solve the problem for small instances.

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 \cdot n!)$.

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 \in 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^2 \cdot 2^n)$.

Answer 2

Even just determining if your problem admits a feasible solution is NP-hard.

Let $G = (V,E)$ be a graph. For each vertex $u$ create a vegetable that has no friends and has all vegetables corresponding to vertices in $\{v : (u,v) \not\in E\}$ as foes.

There is a way to plant all vegetables in a row with no adjacent foes if and only if there is a simple path of length $|V|$ in $G$, that is, if and only if there is an Hamiltonian path in $G$ .