Reverse cartesian product matching all given rows

Question

I´m looking for an efficient algorithm that will find reverse cartesian products.

Mathematically, given $S \subseteq T^n$, I want to express $S$ as a union of sets $A_{i,1} \times A_{i,2} \times \dots \times A_{i,n}$, for $i=1,2,\dots,k$; and I want to minimize the number $k$. Is there an efficient algorithm to solve this problem?

This may be easier to explain by example. Calculating the cartesian product (cross product) is trivial, e.g. {1,2,3,4,5} x {1,2,3,4,5} x {1,2,3,4,5} results in:

    1 1 1
    1 1 2
    1 1 3
    .
    .
    .
    5 5 3
    5 5 4
    5 5 5

All 125 (5 x 5 x 5) rows are created.

Now let's say you remove some rows from this result, i.e. you are left with these 14 rows as a starting point:

    1 2 3
    1 2 4
    1 2 5
    5 2 3
    5 2 4
    2 2 5
    3 2 5
    1 3 3
    1 3 4
    1 3 5
    5 3 3
    5 3 4
    2 3 5
    3 3 5

Now, how do I find a cartesian product that if calculated can generate only those 14 rows back? (order of rows is irrelevant). It can no longer be represented by only one cartesian product {1,2,3,4,5} x {1,2,3,4,5} x {1,2,3,4,5} since e.g. 5 5 5 is not in the list.

One way to now represent the rows as cartesian products is this answer:

    {1} x {2,3} x {3,4,5}
    union
    {5} x {2,3} x {3,4}
    union
    {2,3} x {2,3} x {5}

But the above merge of rows is not optimal although it is a valid solution, we can do better and write it in only two cartesian products:

    {1,5} x {2,3} x {3,4}
    union
    {1,2,3} x {2,3} x {5}

This result is better since 2 < 3 and I want to find the smallest possible number of cartesian products that still represents all the rows. There is no way to reduce (merge) this any further given the 14 rows so this is the best answer in this case.

Now if the starting point would have been all the 125 rows (as in example above) the optimal answer would have been one: {1,2,3,4,5} x {1,2,3,4,5} x {1,2,3,4,5}.

Some known facts about the input:

• All rows are unique, no duplicates exists in the list.
• Row are of same length, fixed with either 3,4,5,6,7,8 in length.
• Numbers in a row range from 1 to 20
• There could be millions of rows as a starting point but typically around 100k, hence speed is of importance rather than low memory consumption.

One possible idea is that rows can be merged if n-1 numbers (or group of numbers in the slot) are equal, e.g.,

    1 2 4
    1 2 5
    1 2 6
    1 3 4
    1 3 5
    1 3 6

can merge into

    1 2 456
    and
    1 3 456

which further can be merged to:

    1 23 456

and written as:

    {1} x {2,3} x {4,5,6}

My question is similar to https://stackoverflow.com/q/20890802/781723, but that one is limited to triples ($n=3$); I am interested in generalizing, where rows can be longer than 3. I also found https://stackoverflow.com/q/46084505/781723, but that has no answer.

Answer 1

Unfortunately the problem is NP-hard when the number of columns ($n$) is unlimited. In particular, consider the case with $n$ columns and where every number in every row is either 0 or 1. Then your problem is equivalent to: given a truth table for a boolean function, find a minimal DNF formula (with the minimum number of clauses) for that function. This is NP-hard.

I know you said you'll have at most 8 columns, so this theoretical result doesn't necessarily imply there is no hope for your specific situation, but it does suggest that you shouldn't expect an efficient algorithm that will generalize to a large number of columns.

One approach you could use that might work well enough in your situation is to use a SAT solver. Encode each of the sets $A_{i,j}$ with a one-hot encoding; i.e., you have variables $x_{i,j,t}$, which is true if $t \in A_{i,j}$ or false otherwise. Then it is easy to write down a bunch of constraints (clauses) that enforce that these $A_{i,j}$ form a solution to your problem. For instance, for each row $r$ that isn't in the input (each $r \notin S$), you get a constraint that $r_1 \notin A_{i,1} \lor r_2 \notin A_{i,2} \lor \dots$ for each $i$, i.e., $(\neg x_{i,1,r_1}\lor \neg x_{i,2,r_2} \lor \dots)$. And so on. In this way, for any $k$, you can set up a SAT instance that will be satisfiable iff it is possible to express your input using $k$ reverse cartesian products. Then you can use binary search on $k$ to find the minimal $k$ such that this is possible.

Because SAT is NP-hard, this won't scale to very large inputs, but it's possible it might work well enough on the problem sizes you mention. The only way to know for sure is to try it and see.