Permutations in Rows; Garden Optimization Problem

Question

Imagine a small garden, divided into 8 equal parts, each a square foot. The garden is 4 ft x 2 ft, so the "bins" are in two rows. Let's number them as:

0 1 2 3
4 5 6 7

Now, each of these plants has other plants that they like, that's good for them to be next to. I can score a particular arrangement by how many of these good relationships I end up with. I've done this in a python script, described here.

Without repeating all those details here, my problem is that there are too many permutations. If I just run it through python's handy permutation generator, there's 8! cases. (I'm stating this problem here as 8 spaces, but my real garden is 16 bins. The problem is too large to solve with 16! possible arrangements.)

My math question is, how can I iterate through a list of unique permutations that also consider how these two rows are arranged? If they were all in one row, the answer is easy, 8!. With 2 rows, there are rotations and mirrors that are really the same answer.

0 1 2 3 is same when mirrored 3 2 1 0
4 5 6 7                       7 6 5 4

0 1 2 3 is same when mirrored 4 5 6 7
4 5 6 7                       0 1 2 3

0 1 2 3 is same when rotated  7 6 5 4
4 5 6 7                       3 2 1 0

I'd like to score all the possible arrangements, but skip those that are mirrors or rotations of things I've already considered. My usual hack-job attempts at iterating through such things include a lookup table, where I'd simply look through a list of ones completed. In this case, that lookup through potentially 8! (16! in my real problem) would take much longer than simply scoring each permutation.

How can I iterate through this and potentially reduce my problem set from 16! (~20 trillion) to perhaps 5 trillion? Or, failing a direct answer, what would you call this kind of problem? I'm not sure what to look up and read about. If I knew enough to know what to tag this problem as, I'd be farther along!

Answer 1

You can solve this problem via integer linear programming, as follows. Let binary variable $x_{i,j}$ indicate whether item $i$ is placed in slot $j$. Maximizing the number of good pairs is equivalent to minimizing the number of bad pairs. For each pair $(j_1,j_2)$ (with $j_1<j_2$) of neighboring slots, let binary variable $y_{j_1,j_2}$ indicate whether the item pair assigned to those slots is bad. The problem is to minimize $\sum_{j_1,j_2} y_{j_1,j_2}$ subject to: \begin{align} \sum_j x_{i,j} &= 1 &&\text{for all $i$}\\ \sum_i x_{i,j} &= 1 &&\text{for all $j$}\\ x_{i_1,j_1} + x_{i_2,j_2} - 1 &\le y_{j_1,j_2} &&\text{for all bad item pairs $(i_1,i_2)$ (with $i_1 \not= i_2$) and slot pairs $(j_1,j_2)$} \end{align} The first constraint places each item in exactly one slot. The second constraint places exactly one item in each slot. The third constraint enforces the implication $(x_{i_1,j_1} = 1 \land x_{i_2,j_2} = 1) \implies y_{j_1,j_2} = 1$, so placing a bad item pair in neighboring slots contributes a penalty of $1$ to the objective.

Using an integer linear programming solver will find an optimal solution without explicitly enumerating all feasible solutions.

Answer 2

You can do this using canonicalization.

As long as the garden is rectangular, exactly one of the equivalent permutations has the $0$ in the top left quarter (for $2\times4$, that’s the first two spots), so you can quickly check whether that’s the case and only process such permutations.

If the garden is square, things are only slightly more complicated. Now there are two equivalent permutations where $0$ is in the top left quarter. If $0$ is off the diagonal, take the one where it’s above the diagonal; if it’s on the diagonal, take the one where the off-diagonal elements in the top-left quarter are in ascending order.

Or you could always take the lexically smallest of the permutations. That’s the one where the least value in the four corners is in the top left corner, and in case of a square, additionally the value to the right of the top-left corner is smaller than the value below the top-left corner.

For $2\times4$ the first approach is more efficient (you just have to compare $2$ values against $0$), but for larger gardens the second approach is more efficient (you always only have to compare $4$ values for rectangles, $6$ for squares, independent of the size of the garden).