# Reverse cartesian product matching all given rows

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.

• What's the context where you encountered this problem? Can you credit the source for it? What did you try? Where did you get stuck? We're happy to help you understand the concepts but just solving exercise- or contest-style problems for you is unlikely to achieve that. You might find this page helpful in improving your question.
– D.W.
Jan 25, 2018 at 0:56
• I asked a similar question a while back, and managed to come up with some code to solve my issue: stackoverflow.com/questions/46084505/reverse-cartesian-product Jan 30, 2018 at 19:34
• I have now added my answer/implementation on that page. I didn't want to add it here since it doesn't always find the optimal solution, with minimum number k, which is what my question was all about. Feb 2, 2018 at 13:58

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.
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.