Ordering a list of lists subject to constraints 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.
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.