0
$\begingroup$

I know the number of solutions to the equation $$x_1+x_2+x_3+...+x_k=n$$ is given by $\binom{n+k-1}{k-1}$.

Is there an algorithm to actually find all the solutions to this equation, without having to brute force?

$\endgroup$
3
  • 1
    $\begingroup$ The coefficient matrix for a linear program using that equality constraint and $x \geq 0$ looks totally unimodular, so the polyhedron defined by the non-negativity constraint and your equality constraint might have the property that all vertices are integral. If that is the case, then you could enumerate all of the vertices. I'm not sure that such an algorithm generalizes, and I'm skeptical that such an approach is really worth doing. $\endgroup$ – Geoff Oxberry Jan 21 '14 at 20:20
  • $\begingroup$ mathoverflow.net/questions/9477 $\endgroup$ – S Huntsman Jan 22 '14 at 2:49
  • $\begingroup$ The solutions (partitions of $n$) exhibit symmetries of permutation, so one optimization over "brute force" might be enumerating the solutions with descending (or ascending) values. Beyond that it's unclear what "not brute force" answers are conceivable. $\endgroup$ – hardmath Jan 22 '14 at 4:31
3
$\begingroup$

Algorithms for listing all solutions are given in the textbook "Constructive Combinatorics" by Dennis Stanton and Dennis White.

$\endgroup$
1
$\begingroup$

Perhaps there's some misunderstanding about the nature of a "brute force" enumeration of the solutions. Guesswork, at any rate, can be essentially eliminated in navigating a search tree consisting of the solutions.

An efficient production of the solutions is implemented easily enough by nesting $k$ loops, with indexes $i_1,\ldots,i_k$ each going from zero to a "running count" of $n$ minus the sum of the indexes assigned outer to any given level of nesting. This can be parameterized as to the levels of nesting by making $k$ a formal argument in a recursively called routine.

The solutions are called ordered partitions (or (weak) compositions) of $n$, and the count of these as given in the Question is easily established by the Stars and Bars argument.

If the order of the summands is not important, or may otherwise be accounted for in a calling algorithm, some efficiency may be gained by generating the solutions with summands restricted to an ascending (equiv. descending) arrangement, which are known as the (unordered) partitions of $n$ into at most $k$ summands. [Strictly speaking a partition is required to be a sum of positive integers, but the restriction to at most $k$ summands allows an easy bookkeeping convention by taking any "missing" summands to be zero.]

The nested loops or recursive function implementation for weak compositions (ordered partitions) is easily adapted to generate (unordered) partitions by simply restricting the indexes to an upper bound limited by the next-higher level index (as well as by the remaining portion of $n$ to be allocated) and a lower bound that permits that remaining portion of $n$ to be attained by the number of summands left to fill.

$\endgroup$
6
  • $\begingroup$ I found an algorithm similar to the recursive function but using loops. I thought there might be algorithms where you wouldn't need to check all the solutions to be generated, but it seems as though for generating $n$ solutions in this case you can't get better complexity than $O(n)$ $\endgroup$ – udiboy1209 Jan 24 '14 at 11:50
  • $\begingroup$ Perhaps you have in mind a function of $O(1)$ complexity that maps an integer between 1 and $\binom{n+k-1}{k-1}$ to a unique solution, without any dependence on providing other solutions. $\endgroup$ – hardmath Jan 24 '14 at 13:42
  • $\begingroup$ yeah exactly! Not what I had in mind, but that's exactly what I want. $\endgroup$ – udiboy1209 Jan 24 '14 at 17:41
  • $\begingroup$ It seems doubtful that one can realize an $O(1)$ complexity, in view of the fact we are outputting something of size $k$ (the solution), but something along these lines might be useful in generating "random" solutions. $\endgroup$ – hardmath Jan 24 '14 at 17:45
  • $\begingroup$ You could make a dictionary out of the list of solutions and find the n'th solution by counting up to n, similar to the algorithm used for finding the n'th permutation of a set. $\endgroup$ – udiboy1209 Jan 24 '14 at 17:47

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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