*n*is a way of writing

*n*as the sum of a sequence of (strictly) positive integers" - Wikipedia.

A composition can include multiple integers of the same value and the order of the values matters, so each unique arrangement of a composition of

*n*is also a distinct composition of

*n*. Each positive integer

*n*has 2^(n-1) compositions. For example 5 has 2^4=16 compositions:

Compositions of 5: { 5 } { 4, 1 } { 1, 4 } { 3, 2 } { 2, 3 } { 3, 1, 1 } { 1, 3, 1 } { 1, 1, 3 } { 2, 2, 1 } { 2, 1, 2 } { 1, 2, 2 } { 2, 1, 1, 1 } { 1, 2, 1, 1 } { 1, 1, 2, 1 } { 1, 1, 1, 2 } { 1, 1, 1, 1, 1 }

*n*as part of my honours project, but it seems like something that could come up in all sorts of areas and it was an interesting problem to have to solve. As for how to find them, the point of this post is to share the recursive algorithm I came up with because I think it's rather elegant. This is essentially a more detailed, less formal explanation of my algorithm than what I wrote for Appendix C of my dissertation.

## Finding the compositions with only 2 elements

It's pretty simple really. To find every pair of positive integers which sum to

*n*, just start with n-1 and 1 and keep decrementing the former and incrementing the latter until you have 1 and n-1. Obviously there will be n-1 compositions of

*n*with exactly 2 elements. As an example here's some Lua code:

1 2 3 4 5 6 7 8 9 10 11 12 |
-- find compositions of n with 2 elements function comps_2(n) local comps = {} local left = n-1 local right = 1 while left > 0 do comps[#comps+1] = {left, right} left -= 1 right += 1 end return comps end |

1 2 3 4 5 6 7 8 9 10 11 12 13 14 |
function print_comps(comps) for c in all(comps) do local s = "" for e in all(c) do s = s..e..", " end print("{ "..s.."}") end end n = 5 c2 = comps_2(n) print(#c2.." compositions of "..n..":") print_comps(c2) |

4 compositions of 5: { 4, 1, } { 3, 2, } { 2, 3, } { 1, 4, }

## Finding all the compositions of *n*

*n*1s and store a copy, since it's a valid composition of

*n*. Then you remove the last 1 and add it in turn to each of the other numbers, storing the result. This process repeats recursively, backtracking up the recursion whenever the last number isn't a 1.

The diagram below illustrates this idea for finding the compositions of 4. The boxes collect all the results garnered from one function call and the arrows show the recursion. First we start with our set of 4 1s. Whenever we encounter an arrow it means 'remove the last 1 and add it to each of the remaining numbers'. The list of compositions found is on the right in the order that they were found (top to bottom). Notice that one of the solutions was found multiple times.

*n*increases. For example we would store 23 compositions of 5 even though there are only 16 unique compositions. To fix this we just need to start adding the 1 from further into the set. If we find the

*i*th composition within a single function call (box in the diagram) then when we remove the last 1 we start adding it from the

*i*th number in the set. For example:

Below is some Lua code for the complete algorithm, with some calling code at the end and the resulting output afterwards.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 |
-- adds a copy of the source table to the destination table function add_table_copy(dest, source) dest[#dest+1] = {} for i = 1, #source do dest[#dest][i] = source[i] end end -- find all compositions of n function comps_all(n) local all_comps = {} local comp = {} for i = 1, n do comp[i] = 1 end add_table_copy(all_comps, comp) find_comps(all_comps, comp, 1) return all_comps end -- recursive composition-finding algorithm function find_comps(all_comps, comp, start_index) --if (#comp <= 3) return if (comp[#comp] ~= 1) return -- remove last element (it's a 1) local new_comp = {} for i = 1, #comp-1 do new_comp[i] = comp[i] end -- add the removed 1 to each element in turn local i = start_index while i <= #new_comp do new_comp[i] += 1 add_table_copy(all_comps, new_comp) find_comps(all_comps, new_comp, i) -- recurse new_comp[i] -= 1 i += 1 end end n = 5 c = comps_all(n) print(#c.." compositions of "..n..":") print_comps(c) |

16 compositions of 5: { 1, 1, 1, 1, 1, } { 2, 1, 1, 1, } { 3, 1, 1, } { 4, 1, } { 5, } { 3, 2, } { 2, 2, 1, } { 2, 3, } { 2, 1, 2, } { 1, 2, 1, 1, } { 1, 3, 1, } { 1, 4, } { 1, 2, 2, } { 1, 1, 2, 1, } { 1, 1, 3, } { 1, 1, 1, 2, }

1 2 3 4 |
function find_comps(all_comps, comp, start_index) if (#comp <= 3) return ... end |

11 compositions of 5: { 1, 1, 1, 1, 1, } { 2, 1, 1, 1, } { 3, 1, 1, } { 2, 2, 1, } { 2, 1, 2, } { 1, 2, 1, 1, } { 1, 3, 1, } { 1, 2, 2, } { 1, 1, 2, 1, } { 1, 1, 3, } { 1, 1, 1, 2, }