Algorithm for finding all sets that fulfill a condition?

Question

Lets say I have a set of none-negative integers of given length $n$ where $n>0$. $$m=\left(m_1,...,m_n\right)$$ A number can appear more than once in the same set. The same set or numbers can also be arranged in a different order. What is the most efficient way of finding all such sets which fulfill the condition: $$\sum^{n}_{k=1}k \cdot m_k=n$$ I am looking for a algorithm I can use for a computer program.

Answer 1

In fact you are looking for partitions. Each time a solution to the question is found it in fact determines a partition, only it is represented in a different way. Your algorithm should start with generating the partitions of $n$ and then collecting similar results. Example (in GAP) with $n=10$:

gap> p10 := Partitions(10);
[ [ 1, 1, 1, 1, 1, 1, 1, 1, 1, 1 ], [ 2, 1, 1, 1, 1, 1, 1, 1, 1 ],    
  [ 2, 2, 1, 1, 1, 1, 1, 1 ], [ 2, 2, 2, 1, 1, 1, 1 ], [ 2, 2, 2, 2, 1, 1],
  [ 2, 2, 2, 2, 2 ], [ 3, 1, 1, 1, 1, 1, 1, 1 ], [ 3, 2, 1, 1, 1, 1, 1 ],
  [ 3, 2, 2, 1, 1, 1 ], [ 3, 2, 2, 2, 1 ], [ 3, 3, 1, 1, 1, 1 ],
  [ 3, 3, 2, 1, 1 ], [ 3, 3, 2, 2 ], [ 3, 3, 3, 1 ], [ 4, 1, 1, 1, 1, 1, 1 ],
  [ 4, 2, 1, 1, 1, 1 ], [ 4, 2, 2, 1, 1 ], [ 4, 2, 2, 2 ], [ 4, 3, 1, 1, 1 ],
  [ 4, 3, 2, 1 ], [ 4, 3, 3 ], [ 4, 4, 1, 1 ], [ 4, 4, 2 ], [ 5, 1, 1, 1, 1, 1 ],
  [ 5, 2, 1, 1, 1 ], [ 5, 2, 2, 1 ], [ 5, 3, 1, 1 ], [ 5, 3, 2 ], [ 5, 4, 1 ],
  [ 5, 5 ], [ 6, 1, 1, 1, 1 ], [ 6, 2, 1, 1 ], [ 6, 2, 2 ], [ 6, 3, 1 ],
  [ 6, 4 ], [ 7, 1, 1, 1 ], [ 7, 2, 1 ], [ 7, 3 ], [ 8, 1, 1 ], [ 8, 2 ],
  [ 9, 1 ], [ 10 ] ]
gap> List(p10, Collected);
[ [ [ 1, 10 ] ], [ [ 1, 8 ], [ 2, 1 ] ], [ [ 1, 6 ], [ 2, 2 ] ],
  [ [ 1, 4 ], [ 2, 3 ] ], [ [ 1, 2 ], [ 2, 4 ] ], [ [ 2, 5 ] ],
  [ [ 1, 7 ], [ 3, 1 ] ], [ [ 1, 5 ], [ 2, 1 ], [ 3, 1 ] ],
  [ [ 1, 3 ], [ 2, 2 ], [ 3, 1 ] ], [ [ 1, 1 ], [ 2, 3 ], [ 3, 1 ] ],
  [ [ 1, 4 ], [ 3, 2 ] ], [ [ 1, 2 ], [ 2, 1 ], [ 3, 2 ] ],
  [ [ 2, 2 ], [ 3, 2 ] ], [ [ 1, 1 ], [ 3, 3 ] ], [ [ 1, 6 ], [ 4, 1 ] ],
  [ [ 1, 4 ], [ 2, 1 ], [ 4, 1 ] ], [ [ 1, 2 ], [ 2, 2 ], [ 4, 1 ] ],
  [ [ 2, 3 ], [ 4, 1 ] ], [ [ 1, 3 ], [ 3, 1 ], [ 4, 1 ] ],
  [ [ 1, 1 ], [ 2, 1 ], [ 3, 1 ], [ 4, 1 ] ], [ [ 3, 2 ], [ 4, 1 ] ],
  [ [ 1, 2 ], [ 4, 2 ] ], [ [ 2, 1 ], [ 4, 2 ] ], [ [ 1, 5 ], [ 5, 1 ] ],
  [ [ 1, 3 ], [ 2, 1 ], [ 5, 1 ] ], [ [ 1, 1 ], [ 2, 2 ], [ 5, 1 ] ],
  [ [ 1, 2 ], [ 3, 1 ], [ 5, 1 ] ], [ [ 2, 1 ], [ 3, 1 ], [ 5, 1 ] ],
  [ [ 1, 1 ], [ 4, 1 ], [ 5, 1 ] ], [ [ 5, 2 ] ], [ [ 1, 4 ], [ 6, 1 ] ],
  [ [ 1, 2 ], [ 2, 1 ], [ 6, 1 ] ], [ [ 2, 2 ], [ 6, 1 ] ],
  [ [ 1, 1 ], [ 3, 1 ], [ 6, 1 ] ], [ [ 4, 1 ], [ 6, 1 ] ],
  [ [ 1, 3 ], [ 7, 1 ] ], [ [ 1, 1 ], [ 2, 1 ], [ 7, 1 ] ],
  [ [ 3, 1 ], [ 7, 1 ] ], [ [ 1, 2 ], [ 8, 1 ] ], [ [ 2, 1 ], [ 8, 1 ] ],
  [ [ 1, 1 ], [ 9, 1 ] ], [ [ 10, 1 ] ] ]

from which the solutions $\{10,0,\ldots\}$, $\{8,1,0,\ldots\}$, $\{6,2,\ldots\}$, $\{4,3,\ldots\}$, $\{2,4,\ldots\}$,$\{0,5,\ldots\}$,$\{7,0,1,\ldots\}$, $\{5,1,1\ldots\}$, etc.