1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – D.W. Jan 25 '18 at 0:56
  • $\begingroup$ 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 $\endgroup$ – terminatur Jan 30 '18 at 19:34
  • $\begingroup$ 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. $\endgroup$ – jbilander Feb 2 '18 at 13:58
1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Thanks a lot, I had a feeling that this problem is np-hard but nice to have it confirmed by someone who knows math better than I do. I have created an algo with the merge approach (n-1 numbers, or group of numbers, being equal). It seems to produce a correct result but doesn't always find the optimal one, however better than nothing for the time being, maybe later I will try and look into using a SAT-solver that you mentioned, although I think it might be a little bit over my head to construct such an algorithm. Thanks again. $\endgroup$ – jbilander Jan 25 '18 at 22:47

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.