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
C E D
C A B
becomes (as one solution)
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.