7
$\begingroup$

I need a function that creates a table of all possible lists of length $n$ which contain integer entries that sum up to the same given number $m$. For example, if we consider lists of size $n=3$ and want to distribute the number $m=2$ in them the result should be:

n=3;
m=2;
numberDistribute[n,m]

{{2,0,0},{0,2,0},{0,0,2},{1,1,0},{1,0,1},{0,1,1}}

Is there such a function in Mathematica? Or maybe there is a convenient way to write it? Thanks for any suggestion.

Improve this question
$\endgroup$
2

4 Answers 4

Reset to default
2
$\begingroup$

How about

numberDistribute[n_?IntegerQ, m_?IntegerQ] :=
   Select[Tuples[Range[0, m], n], Total[#] == m &]
Improve this answer
$\endgroup$
8
$\begingroup$

Proposition

The built-in function IntegerPartitions can be useful here.

numberDistribute[n_, m_] := 
   Join @@ (Permutations /@ (PadLeft[#, n] & /@ IntegerPartitions[m, n]))

Update

To avoid mapping twice through the list generated by IntegerPartitions:

numberDistribute2[n_, m_] := 
   Join @@ ((Permutations@PadLeft[#, n]) & /@ IntegerPartitions[m, n])
Improve this answer
$\endgroup$
4
  • $\begingroup$ Much faster than the other solutions, +1 $\endgroup$
    – eldo
    Commented Dec 3, 2015 at 2:50
  • $\begingroup$ This also avoids the memory problems introduced by creating large tuples. This is a great solution - I had no idea that IntegerPartitions existed! $\endgroup$
    – djphd
    Commented Dec 3, 2015 at 3:36
  • 2
    $\begingroup$ To avoid having to Pad, do Join @@ Permutations /@ IntegerPartitions[m, {n}, Range[0, m]]. $\endgroup$
    – march
    Commented Dec 3, 2015 at 4:20
  • $\begingroup$ @march Thanks for mentioning, this is indeed nicer. $\endgroup$
    – user31159
    Commented Dec 3, 2015 at 4:32
3
$\begingroup$

Of the solutions so far, those based on IntegerPartitions by @Xavier and @march are orders of magnitude faster than those based on Tuples (@djphd and @eldo). Just for interest, the following method based on FrobeniusSolve is about 10 times faster than Tuples, but still much slower than IntegerPartitions.

AnotherNumberDistribute[n_,m_]:=FrobeniusSolve[ConstantArray[1, n], m]
Improve this answer
$\endgroup$
1
$\begingroup$ 
numberDistribute[n_, m_] :=
 Cases[Tuples[Range[0, n - 1], n], a_List /; Total@a == m]

numberDistribute[3, 2]

{{0, 0, 2}, {0, 1, 1}, {0, 2, 0}, {1, 0, 1}, {1, 1, 0}, {2, 0, 0}}

Or

m = 2;
n = 3;

Pick[#, Plus @@@ # - m, 0] &[Tuples[Range[0, m], n]]

{{0, 0, 2}, {0, 1, 1}, {0, 2, 0}, {1, 0, 1}, {1, 1, 0}, {2, 0, 0}}

Improve this answer
$\endgroup$
3
  • $\begingroup$ For some reason the produced entries are never bigger than n-1, so this implementation misses some combinations for larger examples. $\endgroup$
    – Kagaratsch
    Commented Dec 3, 2015 at 2:21
  • $\begingroup$ Except the ordering my result seems to be the result of your question $\endgroup$
    – eldo
    Commented Dec 3, 2015 at 2:26
  • $\begingroup$ Oh, the ordering does not really matter. But I found how to fix your code: Cases[Tuples[Range[0, m], n], a_List /; Total@a == m] seems to work great! $\endgroup$
    – Kagaratsch
    Commented Dec 3, 2015 at 2:27

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