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

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

enter image description here

FullSimplify[poly1]

enter image description here

  • 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) *)