TransWikia.com

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

Mathematica Asked on October 22, 2021

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

2 Answers

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

Answered by yarchik on October 22, 2021

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

Answered by Ulrich Neumann on October 22, 2021

Add your own answers!

Ask a Question

Get help from others!

© 2024 TransWikia.com. All rights reserved. Sites we Love: PCI Database, UKBizDB, Menu Kuliner, Sharing RPP