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 }
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
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.
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, }