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.