# Generating lists of integer numbers with two constraints

I am looking for an effective way to generate all lists of non-negative integer numbers $\{k_0,k_1,k_2\dots\}$ such that $$\sum_{i\ge0} k_i=K, \quad\sum_{i\ge0} i k_i=N$$ for given $K$ and $N$. The lists should have equal length $N+1$, corresponding to that of the longest set or end with the last non-zero element.

I would appreciate any hint.

Here is a variation of @kglr's answer that does what I think your looking for:

g[k_, n_] := With[
{
p = Catenate @ Map[Permutations] @ PadRight[IntegerPartitions[k, n+1], {Automatic, n+1}]
},

Pick[p, p . Range[0, n], n]
]


For example:

g[2,3]
g[3,5]


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

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

Using Permutations makes it rather brute force, so this may be too slow for you. Also, I used a max length of n+1 instead of k+1, changing this is straightforward.

• Thanks. This is indeed what I was looking for. For some unclear reasons I am unable at the moment to upvote or accept answers. As soon as the problem is solved I will be back. If you find out how to avoid Permutations please let me know.
– drer
Feb 25, 2018 at 19:40
• Upon checking the code I have found that it fails for $n=1$. It seems that replacement IntegerPartitions[k]$\rightarrow$IntegerPartitions[k,n+1] helps.
– drer
Feb 26, 2018 at 8:47
• I could not find a description for the option Automatic for PadRight. Certainly the code does not work without the option. Could you explain how does it work?
– drer
Feb 26, 2018 at 8:54
• @drer Yes, I think your suggested change is good. As for PadRight, Automatic means use the existing dimension. Feb 26, 2018 at 15:56
• I have found a way to get rid of Permutations. I have posted an answer with the corresponding code. Please take a look at it. I would be very thankful for any suggestions on improving the code, as it looks ugly comparing with those given by experienced Mathematica users.
– drer
Feb 28, 2018 at 17:28
ClearAll[f]
f[k_, n_] := Module[{p = PadLeft[Sort /@ IntegerPartitions@k, {Automatic, k + 1}]},
Pick[p, Range[0, k].# & /@ p, n]]


Examples:

 Join @@ Table[{i, #, f[i, #]} & /@ Range[i^2] /. {_, _, {}} -> Sequence[], {i, 2, 6}] //
Grid[Prepend[#, {"k", "n", "f[k,n]"}],
Dividers -> {All, Thread[{1, 2, 4, 7, 12, 19, 29, -1} -> True]},
Background -> {None, None, {{{2, 3}, {1, -1}} -> LightYellow,
{{4, 6}, {1, -1}} -> LightRed, {{7, 11}, {1, -1}} -> LightGreen,
{{12, 18}, {1, -1}} -> LightPurple, {{19, -1}, {1, -1}} -> LightBlue}}] &


{10, #, f[10, #]} & /@ Range[10^2] /. {_, _, {}} -> Sequence[] //
Grid[Prepend[#, {"k", "n", "f[k,n]"}], Dividers -> All] & // TeXForm


$$\begin{array}{|c|c|c|} \hline \text{k} & \text{n} & \text{f[k,n]} \\ \hline 10 & 55 & \left( \begin{array}{ccccccccccc} 0 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 \\ \end{array} \right) \\ \hline 10 & 64 & \left( \begin{array}{ccccccccccc} 0 & 0 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 2 \\ \end{array} \right) \\ \hline 10 & 71 & \left( \begin{array}{ccccccccccc} 0 & 0 & 0 & 1 & 1 & 1 & 1 & 1 & 1 & 2 & 2 \\ \end{array} \right) \\ \hline 10 & 72 & \left( \begin{array}{ccccccccccc} 0 & 0 & 0 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 3 \\ \end{array} \right) \\ \hline 10 & 76 & \left( \begin{array}{ccccccccccc} 0 & 0 & 0 & 0 & 1 & 1 & 1 & 1 & 2 & 2 & 2 \\ \end{array} \right) \\ \hline 10 & 78 & \left( \begin{array}{ccccccccccc} 0 & 0 & 0 & 0 & 1 & 1 & 1 & 1 & 1 & 2 & 3 \\ \end{array} \right) \\ \hline 10 & 79 & \left( \begin{array}{ccccccccccc} 0 & 0 & 0 & 0 & 1 & 1 & 1 & 1 & 1 & 1 & 4 \\ 0 & 0 & 0 & 0 & 0 & 1 & 1 & 2 & 2 & 2 & 2 \\ \end{array} \right) \\ \hline 10 & 80 & \left( \begin{array}{ccccccccccc} 0 & 0 & 0 & 0 & 0 & 0 & 2 & 2 & 2 & 2 & 2 \\ \end{array} \right) \\ \hline 10 & 82 & \left( \begin{array}{ccccccccccc} 0 & 0 & 0 & 0 & 0 & 1 & 1 & 1 & 2 & 2 & 3 \\ \end{array} \right) \\ \hline 10 & 83 & \left( \begin{array}{ccccccccccc} 0 & 0 & 0 & 0 & 0 & 1 & 1 & 1 & 1 & 3 & 3 \\ \end{array} \right) \\ \hline 10 & 84 & \left( \begin{array}{ccccccccccc} 0 & 0 & 0 & 0 & 0 & 1 & 1 & 1 & 1 & 2 & 4 \\ 0 & 0 & 0 & 0 & 0 & 0 & 1 & 2 & 2 & 2 & 3 \\ \end{array} \right) \\ \hline 10 & 85 & \left( \begin{array}{ccccccccccc} 0 & 0 & 0 & 0 & 0 & 1 & 1 & 1 & 1 & 1 & 5 \\ \end{array} \right) \\ \hline 10 & 86 & \left( \begin{array}{ccccccccccc} 0 & 0 & 0 & 0 & 0 & 0 & 1 & 1 & 2 & 3 & 3 \\ \end{array} \right) \\ \hline 10 & 87 & \left( \begin{array}{ccccccccccc} 0 & 0 & 0 & 0 & 0 & 0 & 1 & 1 & 2 & 2 & 4 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 2 & 2 & 3 & 3 \\ \end{array} \right) \\ \hline 10 & 88 & \left( \begin{array}{ccccccccccc} 0 & 0 & 0 & 0 & 0 & 0 & 1 & 1 & 1 & 3 & 4 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 2 & 2 & 2 & 4 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 3 & 3 & 3 \\ \end{array} \right) \\ \hline 10 & 89 & \left( \begin{array}{ccccccccccc} 0 & 0 & 0 & 0 & 0 & 0 & 1 & 1 & 1 & 2 & 5 \\ \end{array} \right) \\ \hline 10 & 90 & \left( \begin{array}{ccccccccccc} 0 & 0 & 0 & 0 & 0 & 0 & 1 & 1 & 1 & 1 & 6 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 2 & 3 & 4 \\ \end{array} \right) \\ \hline 10 & 91 & \left( \begin{array}{ccccccccccc} 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 2 & 2 & 5 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 1 & 4 & 4 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 3 & 3 & 4 \\ \end{array} \right) \\ \hline 10 & 92 & \left( \begin{array}{ccccccccccc} 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 1 & 3 & 5 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 2 & 4 & 4 \\ \end{array} \right) \\ \hline 10 & 93 & \left( \begin{array}{ccccccccccc} 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 1 & 2 & 6 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 2 & 3 & 5 \\ \end{array} \right) \\ \hline 10 & 94 & \left( \begin{array}{ccccccccccc} 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 1 & 1 & 7 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 2 & 2 & 6 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 4 & 5 \\ \end{array} \right) \\ \hline 10 & 95 & \left( \begin{array}{ccccccccccc} 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 3 & 6 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 5 & 5 \\ \end{array} \right) \\ \hline 10 & 96 & \left( \begin{array}{ccccccccccc} 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 2 & 7 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 4 & 6 \\ \end{array} \right) \\ \hline 10 & 97 & \left( \begin{array}{ccccccccccc} 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 1 & 8 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 3 & 7 \\ \end{array} \right) \\ \hline 10 & 98 & \left( \begin{array}{ccccccccccc} 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 2 & 8 \\ \end{array} \right) \\ \hline 10 & 99 & \left( \begin{array}{ccccccccccc} 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 9 \\ \end{array} \right) \\ \hline 10 & 100 & \left( \begin{array}{ccccccccccc} 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 10 \\ \end{array} \right) \\ \hline \end{array}$$

• Probably I was not precise enough. I need not a single reresentative, but the complete list of the requred sets (lists). Besides I have an impresssion that the first element of your lists corresponds to $i=1$, rather than $i=0$.
– drer
Feb 25, 2018 at 12:21
• @drer, changed the index to start from 0. f gives all lists that satisfy the two conditions.
– kglr
Feb 25, 2018 at 12:27
• Thank you! It seems to work. The only thing to correct is to allow the value $k_i=0$ as well.
– drer
Feb 25, 2018 at 12:53
• Besides it seems that your solutions are subject to condition $k_i\le k_{i+1}$.
– drer
Feb 25, 2018 at 13:48
• @drer, i thought "ordered non-negative integer numbers" meant $k_i \leq k_{i+1}$.
– kglr
Feb 25, 2018 at 18:00

This answer is intended not to present programming skills (rather opposite) or to give a general recipe for generating lists with several constraints, but instead aims on solving the particular problem. The solution should be much more effective than the brute force approach and uses a bijection between integer partitions and the sets (lists) in question.

I have checked two versions:

g1[n_,k_]:=Module[
{u=Map[Tally] @ IntegerPartitions[n,k],s},
Table[s=SparseArray[Rule @@ Transpose[u[[i]]],n]//Normal;
Join[{k-Total[s]},s],{i,Length[u]}]
]

g2[n_,k_]:=Module[
Table[{pos,val}=Transpose[u[[i]]];SparseArray[pos+1->val,n+1]//Normal,
{i,Length[u]}]
]


They both appear to give correct result

g1[5,3]

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

and seem to be equally efficient. I would be very thankful for any suggestions on improving the code.

• This looks very good. I think you should make this the accepted answer. Feb 28, 2018 at 20:46