3
$\begingroup$

I am trying to obtain all possible combinations of elements in a (long) list

factors = {A, B, C}; 
getCombinations[factors,n] 

For n = 3 factors, it should give

getCombinations[factors,3] 
{{{A^3, A^2 B, A^2 C}, {A B^2, A B C}, {A C^2}}, {{B^3, 
   B^2 C}, {B C^2}}, {{C^3}}} 

I'm stuck trying to extend it for "n" number of factors.

For n=3 I have

len = Length[fac];
Table[fac[[i]]*
  Table[fac[[j]]*
    Table[fac[[k]],
     {k, j, len}],
   {j, i, len}],
 {i, 1, len}]

SOLUTION (EDIT)

Both users cvgmt and Syed posted working solutions. Thank you so much! Based on the solution of cvgmt:

getCombinations[factors_, m_Integer] := 
 Module[{list,  n = Length[factors]},
  list = FrobeniusSolve[ConstantArray[1, n], m];
  Inner[Power, factors, #, Times] & /@ list // Sort]
$\endgroup$

4 Answers 4

6
$\begingroup$

We can use FrobeniusSolve to solve the equation $$x_1+x_2+\cdots +x_n= m $$ Here n and m may not the same.

Clear[m, n, list];
n = 4;
m = 4;
list = FrobeniusSolve[ConstantArray[1, n], m];
Inner[Power, Array[Subscript[a, ##] &, n], #, Times] & /@ list // Sort

enter image description here

$\endgroup$
4
$\begingroup$

One possible implementation could be:

getCombinations[n_Integer] := Module[{t},
  t = Select[Tuples[Range[n, 0, -1], {n}], Total@# == n &];
  Map[Times @@ Power[ToExpression /@Alphabet[][[1 ;; n]], #] &, t, {1}]
  ]

getCombinations[3]

$$\left\{a^3,a^2 b,a^2 c,a b^2,a b c,a c^2,b^3,b^2 c,b c^2,c^3\right\}$$

getCombinations[4]

$$\left\{a^4,a^3 b,a^3 c,a^3 d,a^2 b^2,a^2 b c,a^2 b d,a^2 c^2,a^2 c d,a^2 d^2,a b^3,a b^2 c,a b^2 d,a b c^2,a b c d,a b d^2,a c^3,a c^2 d,a c d^2,a d^3,b^4,b^3 c,b^3 d,b^2 c^2,b^2 c d,b^2 d^2,b c^3,b c^2 d,b c d^2,b d^3,c^4,c^3 d,c^2 d^2,c d^3,d^4\right\}$$


EDIT

To make it more general:

getCombinationsFromFactors[n_Integer, k_List] := Module[{t},
  t = Select[Tuples[Range[n, 0, -1], {Length@k}], Total@# == n &];
  Map[Times @@ Power[k, #] &, t, {1}]
  ]

getCombinationsFromFactors[3, {a, b, f}]

$$\left\{a^3,a^2 b,a^2 f,a b^2,a b f,a f^2,b^3,b^2 f,b f^2,f^3\right\}$$

getCombinationsFromFactors[5, {a, b, f}]

$${a^5, a^4 b, a^4 f, a^3 b^2, a^3 b f, a^3 f^2, a^2 b^3, a^2 b^2 f, a^2 b f^2, a^2 f^3, a b^4, a b^3 f, a b^2 f^2, a b f^3, a f^4, b^5, b^4 f, b^3 f^2, b^2 f^3, b f^4, f^5}$$

$\endgroup$
2
$\begingroup$

How about this?

factors = {"a", "b", "c", "d"};
DeleteDuplicates[Times @@@ Tuples[factors, Length[factors]]];

$ \left\{\text{a}^4,\text{a}^3 \text{b},\text{a}^3 \text{c},\text{a}^3 \text{d},\text{a}^2 \text{b}^2,\text{a}^2 \text{b} \text{c},\text{a}^2 \text{b} \text{d},\text{a}^2 \text{c}^2,\text{a}^2 \text{c} \text{d},\text{a}^2 \text{d}^2,\text{a} \text{b}^3,\text{a} \text{b}^2 \text{c},\text{a} \text{b}^2 \text{d},\text{a} \text{b} \text{c}^2,\text{a} \text{b} \text{c} \text{d},\text{a} \text{b} \text{d}^2,\text{a} \text{c}^3,\text{a} \text{c}^2 \text{d},\text{a} \text{c} \text{d}^2,\text{a} \text{d}^3,\text{b}^4,\text{b}^3 \text{c},\text{b}^3 \text{d},\text{b}^2 \text{c}^2,\text{b}^2 \text{c} \text{d},\text{b}^2 \text{d}^2,\text{b} \text{c}^3,\text{b} \text{c}^2 \text{d},\text{b} \text{c} \text{d}^2,\text{b} \text{d}^3,\text{c}^4,\text{c}^3 \text{d},\text{c}^2 \text{d}^2,\text{c} \text{d}^3,\text{d}^4\right\} $

$\endgroup$
1
  • 1
    $\begingroup$ This is a brilliant solution as well. But when the number of terms grows so much it becomes computationally more expensive to build the combinations and check for duplicates as opposed to building the terms directly without duplicates. $\endgroup$
    – Albercoc
    Nov 17, 2022 at 11:25
0
$\begingroup$

It's just a DFS

ClearAll[dfs];
max = 3;
len = 3;
dfs[curVal_, curPos_, curSum_, cur_] := Which[
        curSum > max || curPos > len,      Return[],
        curSum === max && curPos === len,  Sow[cur],
        True,
        Table[
              dfs[val, curPos + 1, curSum + val, Append[cur, val]],
              {val, 0, max - curSum}
              ]
]
Reap[dfs[0, 0, 0, {}]]//
Last//
Last//
Map[
    Inner[Power, Array[a, len], #, Times]&
]

{a[3]^3, a[2]*a[3]^2, a[2]^2*a[3], a[2]^3, a[1]*a[3]^2, a[1]*a[2]*a[3], a[1]*a[2]^2, a[1]^2*a[3], a[1]^2*a[2], a[1]^3}

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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