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
)

Essays/Compositions

See also