Multiplying elements of two lists in all possible orders

Question

I have two lists:

U1 = {u10, u11, u12};
U2 = {u20,u21, u22};

and I want to get a third list that will be the product of these two lists in a particular order. the third list will look like this:

UU = {u10, u20, u10 * u11, u10 * u21, u11 * u20, u20 * u21,
      u10 * u11 * u12, u10 * u11 * u22, u10 * u12 * u21,
      u10 * u21 * u22, u11 * u12 * u20, u11 * u20 * u22,
      u12 * u20 * u21, u20 * u21 * u22}

so if I take these lists in terms of actual numbers, as,

U1 = {2, 3, 4};
U2 = {1, 2, 3};

I should get,

UU = {2, 1, 6, 4, 3, 2, 24, 18, 16, 12, 12, 9, 8, 6}

Any help would be highly appreciated.

the pattern can be observed using NCExpand.

I was getting it using:

UU = MonomialList[NCExpand[(u11 + u21) ** (u20 + u10)]]

giving me

(* {u10 u11, u10 u21, u11 u20, u20 u21} *)

and when used again

UU = MonomialList[NCExpand[(u12 + u22) ** (u11 + u21) ** (u10 + u20)]]

results in

(* {u10 u11 u12, u10 u11 u22, u10 u12 u21, u10 u21 u22, u11 u12 u20, u11 u20 u22, u12 u20 u21, u20 u21 u22} *)

the problem is, I want to get the product list as one list and in general way like if I just define my U1 and U2 and generally get my UU.

Answer 1

I'm going to bundle this into a function that you can use multiple times and then get your final result by aggregation.

IndexedBinaryChoice[listA_, listB_, slotCount_Integer] :=
  Map[
    Apply[Times]@*Flatten@*MapIndexed[Part[{listA, listB}, ##] &],
    Tuples[{1, 2}, slotCount]] /;
  Length[listA] == Length[listB]

I came up with this by interpreting your question as follows. The pattern seems to take 1, 2, and 3 "columns" of the matrix {U1, U2} in turn. It appears that we have 2 terms from the 1-column case, 4 terms from the 2-column case, and 8 terms from the 3 column case. Further inspection of your example suggests that for the n-column case we have a "template" list of indexes of length n, something like {x[[1]], x[[2]], x[[3]]} in the 3-column case, where we can then replace each x with either U1 or U2. There are 2^n ways to choose the replacements, which matches our observation above.

So, at the heart we have Tuples[{1, 2}, slotCount]. The 1 and 2 represent our choices (choose from U1 or from U2), and slotCount is how many columns we want to cover. A tuple like {1, 2, 1} means "in the first slot, choose from U1, in the second from U2, and in the third from U1. Of course, we want to generalize, so U1 and U2 really mean "the first and second inputs".

Now, I want to map a "chooser" over each tuple. The chooser will index into the input lists. If I bundle my inputs like inputs = {first, second}, then the tuple {1, 2, 1} means {inputs[[1]][[1]], inputs[[2]][[2]], inputs[[1]][[3]]}, which means I need to keep track of where in the tuple I am as I map the chooser over it. That suggests using MapIndexed: MapIndexed[Part[{first, second}, ##] &][{1, 2, 1}]. We need to compose this basic chooser function with Times since that's how you wanted to transform each tuple-choice, and we need to map this whole thing over all the tuples.

Testing it on the 1-slot case:

IndexedBinaryChoice[U1, U2, 1]
(* {u10, u20} *)

2-slot case:

IndexedBinaryChoice[U1, U2, 2]
(* {u10 u11, u10 u21, u11 u20, u20 u21} *)

3-slot case:

IndexedBinaryChoice[U1, U2, 3]
(* {u10 u11 u12, u10 u11 u22, u10 u12 u21, u10 u21 u22, u11 u12 u20, u11 u20 u22, u12 u20 u21, u20 u21 u22} *)

Now, let's just refine our definition of IndexedBinaryChoice by adding this:

IndexedBinaryChoice[listA_, listB_] :=
  Flatten[IndexedBinaryChoice[listA, listB, #] & /@ Range[Length@listA]] /; 
  Length[listA] == Length[listB]

And now,

IndexedBinaryChoice[U1, U2]
(* This should be equal to UU *)

You might want to add other validity checks.

Answer 2

With

U1 = {u10, u11, u12};
U2 = {u20,u21, u22};

we do:

FoldList[Times, U1 + U2] // MonomialList // Flatten

if order doesn't matter and

Distribute /@ FoldList[NonCommutativeMultiply, U1 + U2] // MonomialList // Flatten

if order matters.

Finally, for lists of integers such as

U1 = {2, 3, 4};
U2 = {1, 2, 3};

we can do

indexedBinaryChoice2[U1_, U2_] := Module[
  {u, v, u1, u2, rules},
  u1 = Array[u, Length@U1]; u2 = Array[v, Length@U2];
  rules = Thread[Join[u1, u2] -> Join[U1, U2]];
  Flatten@MonomialList@FoldList[Times, u1 + u2] /. rules
 ]

or

Distribute[#, CirclePlus] & /@ FoldList[Times, Thread@CirclePlus[U1, U2]] /. CirclePlus -> Sequence

---

Explanation

Since these are just the monomials arising by multiplying elements of U1 + U2, we generate a list of the multiplications using

FoldList[Times, U1 + U2]
(* {u10 + u20, (u10 + u20) (u11 + u21), (u10 + u20) (u11 + u21) (u12 + u22)} *)

Then, we use MonomialList, which maps over lists, to extract the monomials in each term in each element of the list:

FoldList[Times, U1 + U2] // MonomialList
(* {{u10, u20},
    {u10 u11, u10 u21, u11 u20, u20 u21},
    {u10 u11 u12, u10 u11 u22, u10 u12 u21, u10 u21 u22, u11 u12 u20, u11 u20 u22, u12 u20 u21, u20 u21 u22}} *)

Since this is a list of lists, we just Flatten it at the end.

If order matters (which could be the case since OP is using NCExpand), do instead

Distribute /@ FoldList[NonCommutativeMultiply, U1 + U2] // MonomialList // Flatten

The only difference here is that we need to tell Mathematica that our version of NonCommutativeMultiply distributes.