Ordering a list of lists subject to constraints

Question

I have encountered a surprisingly challenging problem arranging a matrix-like (List of Lists) of values subject to the following constraints (or deciding it is not possible):

A matrix of m randomly generated rows with up to n distinct values (no repeats within the row) arrange the matrix such that the following holds (if possible):

1) The matrix must be "lower triangular"; the rows must be ordered in ascending lengths so the only "gaps" are in the top right corner

2) If a value appears in more than one row it must be in the same column (i.e. rearranging the order of values in a row is allowed).

Example 1 - which has a solution

A B
C E D
C A B

becomes (as one solution)

A B
E D C
A B C

since A, B and C all appear in columns 1, 2 and 3, respectively.

Example 2 - which has no solution

A B C
A B D
C B D

has no solution since the constraints require the third row to have the C and D in the third column which is not possible.

In my attempts to solve this naively (e.g. by sorting shortest rows to longest and then trying to order the rows from "most in common" to least and then simple reordering within the row) there are always scenarios that it thinks aren't solvable but are. In other words backtracking/exhaustive search appears to be required, which is OK but I haven't yet struck onto a nice concise (ideally functional) algorithm for this.

Answer 1

This problem is an instance of the list coloring problem. The list coloring problem is a variant of the graph color problem, where additionally have constraints that provide for each vertex a list of allowable colors that can be used for that vertex.

Here's the relationship. Let $V$ denote the set of distinct values that appear in any row. In Example 1, $V=\{A,B,C,D,E\}$; in Example 2, $V=\{A,B,C,D\}$. Form an undirected graph $G$ where $V$ is the vertex set (so each value is a vertex). Add an edge $(u,v)$ between two values if there is some row where those two vertices appear together.

Now suppose we want to arrange these in a matrix with $c$ columns (i.e., $c$ is the length of the longest row). We'll imagine having $c$ colors, numbered from $1$ to $c$, where color $i$ corresponds to the $i$th column. If the value $v$ is colored $i$, we take this to mean that every appearance of value $v$ should appear in column $i$.

Now from each row that is less than $c$ values long, we obtain some constraints. In particular, if we have a row that is $\ell$ values long, then each value in that row needs to be colored with a color in the set $\{1,2,\dots,\ell\}$ (to ensure the lower-triangular requirement). These are the lists that make this a list coloring problem.

Now any solution to the list coloring problem yields a solution to your problem: the colors tell you what column to put each value into, which tells you how to permute each of your rows to form a valid solution. Therefore, you can use any algorithm for the list coloring problem to solve your problem.

Answer 2

To solve this problem in practice, here's the first thing I would try:

• Try using a SAT solver.

As long as your problem instance isn't too large, I suspect that a SAT solver will be very effective at solving this problem.

Here is how you use a SAT solver. Introduce boolean variables $x_{v,j}$ (where $v$ ranges over values, and $j$ ranges over columns). If your original matrix has $n$ distinct values and the longest row has $c$ columns, you'll have $cn$ boolean variables ($v$ ranges over $n$ distinct values, and $j$ ranges from $1$ to $c$). The intended meaning of $x_{v,j}$ is that value $v$ appears only in column $j$.

Now add boolean constraints as follows:

• If the value $v$ appears somewhere in the input, then it needs to appear in some row. This gives us the constraint $x_{v,1} \lor x_{v,2} \lor \dots \lor x_{v,c}$ for each value $v$.

• If the value $v$ appears in a row of length $\ell$, then the value $v$ must appear in one of the first $\ell$ columns. Consequently, for each $v$ we get the constraint $x_{v,1} \lor x_{v,2} \lor \dots \lor x_{v,\ell}$, where $\ell$ is the length of the shortest row containing the value $v$. (This actually subsumes the constraint in the previous bullet, so that one can be omitted.)

• The value $v$ appears in at most one column. This gives us the constraint $\neg x_{v,j} \lor \neg x_{v,k}$ for each value $v$ and each pair $j,k$ of columns (where $1 \le j < k \le c$).

• If there is some row that contains both the value $u$ and the value $v$, then both $u$ and $v$ cannot be placed into the same column. Consequently, we get the constraint $\neg x_{u,j} \land \neg x_{v,j}$ for each $j=1,2,\dots,c$ and each pair of values $u,v$ that appear together in the same row.

Then let the SAT solver crank away. Give it a try -- I think it might just work on the problems you have in practice.

To learn more about using SAT solvers to solve graph coloring problems, see, e.g., this nifty video.

Answer 3

I needed a solution in a functional language (XQuery) so I implemented this first in Scala due to its expressiveness and I post the code below. It uses a brute-force, breadth first style search for solutions. I'm only interested in a single solution (if one exists) so the algorithm throws away the extra solutions.

def order[T](listOfLists: List[List[T]]): List[List[T]] = {

def isConsistent(list: List[T], listOfLists: List[List[T]]) = {
  def isSafe(list1: List[T], list2: List[T]) =
    (for (i <- list1.indices; j <- list2.indices) yield
      if (list1(i) == list2(j)) i == j else true
      ).forall(_ == true)

  (for (row <- listOfLists) yield isSafe(list, row)).forall(_ == true)
}


def solve(fixed: List[List[T]], remaining: List[List[T]]): List[List[T]] =
  if (remaining.isEmpty)
    fixed        // Solution found so return it
  else
    (for {
      permutation <- remaining.head.permutations.toList
      if isConsistent(permutation, fixed)
      ordered = solve(permutation :: fixed, remaining.tail)
      if !ordered.isEmpty
    } yield ordered) match {
      case solution1 :: otherSolutions =>       // There are one or more solutions so just return one
        solution1

      case Nil =>   // There are no solutions
        Nil
    }


// Ensure each list has unique items (i.e. no dups within the list)
  require (listOfLists.forall(list => list == list.distinct))

  /* 
   * The only optimisations applied to an otherwise full walk through all solutions is to sort the list of list so that the lengths 
   * of the lists are increasing in length and then starting the ordering with the first row fixed i.e. there is one degree of freedom
   * in selecting the first row; by having the shortest row first and fixing it we both guarantee that we aren't disabling a solution from being
   * found (i.e. by violating the "lower triangular" requirement) and can also avoid searching through the permutations of the first row since
   * these would just result in additional (essentially duplicate except for ordering differences) solutions.
   */
    //solve(Nil, listOfLists).reverse           // This is the unoptimised version
    val sorted = listOfLists.sortWith((a, b) => a.length < b.length)
    solve(List(sorted.head), sorted.tail).reverse
}