How to decompose a list of n-tuples into a union of Cartesian products

Question

I have a list with all elements at the same level
{
    {a, d}, {a, e}, {a, f},
    {b, d}, {b, e}, {b, f},
    {c, d}, {c, e}, {c, f},
    {x, t}, {x, q}
}

How can I transform this to a list of Cartesian products, so that the number of products is minimal? For the list above I would like to get the result
{ Outer[List,{a, b, c}, {d, e, f}], Outer[List, {x}, {t, q} }

Can someone tell me, what the algorithm is that I need here? The above list is just an example, in fact I need to transform a list with 3 or 4 elements, e.g. I would like to get
{ Outer[List, {a, b, c}, {c, d, e}, {e, f, g}],
  Outer[List, {x}, {y, z, t}, {n}],
  Outer[List, {t, u}, {v}, {h, o, i} }

for the list below
{{a, c, e}, {a, c, f}, {a, c, g}, {a, d, e}, {a, d, f}, {a, d, g}, 
 {a, e, e}, {a, e, f}, {a, e, g}, {b, c, e}, {b, c, f}, {b, c, g}, 
 {b, d, e}, {b, d, f}, {b, d, g}, {b, e, e}, {b, e, f}, {b, e, g}, 
 {c, c, e}, {c, c, f}, {c, c, g}, {c, d, e}, {c, d, f}, {c, d, g}, 
 {c, e, e}, {c, e, f}, {c, e, g}, {x, y, n}, {x, z, n}, {x, t, n}, 
 {t, v, h}, {t, v, o}, {t, v, i}, {u, v, h}, {u, v, o}, {u, v, i}}

yarchik · Accepted Answer

One can try to exploit the functionality of FullSimplify. For this, we transform lists into polynomial expressions.

First example

list1={
    {a, d}, {a, e}, {a, f},
    {b, d}, {b, e}, {b, f},
    {c, d}, {c, e}, {c, f},
    {x, t}, {x, q}
}

poly1=Apply[Times,list1,{1}]//Total

FullSimplify[poly1]

Consider for the second example

list2={{a, c, e}, {a, c, f}, {a, c, g}, {a, d, e}, {a, d, f}, {a, d, g}, 
 {a, e, e}, {a, e, f}, {a, e, g}, {b, c, e}, {b, c, f}, {b, c, g}, 
 {b, d, e}, {b, d, f}, {b, d, g}, {b, e, e}, {b, e, f}, {b, e, g}, 
 {c, c, e}, {c, c, f}, {c, c, g}, {c, d, e}, {c, d, f}, {c, d, g}, 
 {c, e, e}, {c, e, f}, {c, e, g}, {x, y, n}, {x, z, n}, {x, t, n}, 
 {t, v, h}, {t, v, o}, {t, v, i}, {u, v, h}, {u, v, o}, {u, v, i}};

(Apply[Times,list2,{1}]//Total)//FullSimplify
(*(a + b + c) (c + d + e) (e + f + g) + o t v + o u v + h (t + u) v + i (t + u) v + n t x + n x y + n x z*)

Upon closer inspection, I realized that this is not so easy, and the "factorization" is, in fact, incomplete...

Now you may wonder if this can be improved. Yes! It seems MA's FullSimplify does not treat all variables equivalently. Replacing x with j solves the problem and gives exactly what is expected.

(Apply[Times,list2/.{x->j},{1}]//Total)//FullSimplify
(* (a + b + c) (c + d + e) (e + f + g) + (h + i + o) (t + u) v + j n (t + y + z) *)

Ulrich Neumann · Answer

Perhaps Outer is what you are looking for.
Try
Outer[cp, {a, b, c}, {d, e, f}]
(*{{cp[a, d], cp[a, e], cp[a, f]}, {cp[b, d], cp[b, e], cp[b, f]}, {cp[c, d], cp[c, e], cp[c, f]}}*)

where cp is the unknown cartesian product function ( "x-product" in your definition).

How to decompose a list of n-tuples into a union of Cartesian products

2 Answers

Add your own answers!

Ask a Question