Essays/Compositions
The verb comp generates all size x compositions of y in ascending order: all lists v of non-negative integers such that (x=#v)*.(y=+/v) . For example, x comp y are the exponents in the expansion of an x-nomial a0+a1+a2+ ... raised to the y-th power.
comp=: 4 : 0
if. 1 >: x do. ((x>:&*y),x)$y
else.
c=. (x-2)!(x-2)+|.k=. i.1+y
(c#k) ,. ((x-1){."0 c#-k) + (-1+;i.&.>-c) { (x-1) comp y
end.
)
0 1 2 3 4 comp&.> 4
┌┬─┬───┬─────┬───────┐
││4│0 4│0 0 4│0 0 0 4│
││ │1 3│0 1 3│0 0 1 3│
││ │2 2│0 2 2│0 0 2 2│
││ │3 1│0 3 1│0 0 3 1│
││ │4 0│0 4 0│0 0 4 0│
││ │ │1 0 3│0 1 0 3│
││ │ │1 1 2│0 1 1 2│
││ │ │1 2 1│0 1 2 1│
││ │ │1 3 0│0 1 3 0│
││ │ │2 0 2│0 2 0 2│
││ │ │2 1 1│0 2 1 1│
││ │ │2 2 0│0 2 2 0│
││ │ │3 0 1│0 3 0 1│
││ │ │3 1 0│0 3 1 0│
││ │ │4 0 0│0 4 0 0│
││ │ │ │1 0 0 3│
││ │ │ │1 0 1 2│
││ │ │ │1 0 2 1│
││ │ │ │1 0 3 0│
││ │ │ │1 1 0 2│
││ │ │ │1 1 1 1│
││ │ │ │1 1 2 0│
││ │ │ │1 2 0 1│
││ │ │ │1 2 1 0│
││ │ │ │1 3 0 0│
││ │ │ │2 0 0 2│
││ │ │ │2 0 1 1│
││ │ │ │2 0 2 0│
││ │ │ │2 1 0 1│
││ │ │ │2 1 1 0│
││ │ │ │2 2 0 0│
││ │ │ │3 0 0 1│
││ │ │ │3 0 1 0│
││ │ │ │3 1 0 0│
││ │ │ │4 0 0 0│
└┴─┴───┴─────┴───────┘
In words, the rows of x comp y whose first element is k , are formed by prefixing k to (x-1)comp(y-k) . But the latter is just the last (x-2)!(x-2)+1+y-k rows of (x-1) comp y , with the first column decremented by k .
The phrase y ((=+/"1) # ]) (#: i.@(*/)) x$1+y is equivalent to x comp y , but requires space (and time) exponential in the size of the desired result.
comp1 is a non-recursive version of comp ; compcheck incorporates checks.
comp1=: 4 : 0
k=. i.#c=. (-1+y){.1
z=. i.0 0
for_j. i.x do.
z=. (c#k) ,. (j{."0 c#-k) + (-1+;i.&.>-c) { z
c=. +/\.c
end.
z
)
compcheck=: 4 : 0
assert. (0<:x)*.x<:y
if. 1>:x do. z=. ((x>:&*y),x)$y
else.
c=. (x-2)!(x-2)+|.k=. i.1+y
z=. (c#k) ,. ((x-1){."0 c#-k) + (-1+;i.&.>-c) { (x-1) compcheck y
end.
assert. 2=#$z
assert. (-: /:~) z
assert. x={:$z
assert. y=+/"1 z
)
See also
Contributed by Roger Hui. An earlier version of the text appeared as section 4.2 of Some Uses of { and } by Roger Hui, APL 87 Conference Proceedings, May 10-14, 1987.