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]
Improve this question
$\endgroup$

4 Answers 4

Reset to default
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

Improve this answer
$\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}$$

Improve this answer
$\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\} $

Improve this answer
$\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$ Commented 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}

Improve this answer
$\endgroup$

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.