Differences between revisions 7 and 8
 ⇤ ← Revision 7 as of 2008-12-08 10:45:29 → Size: 3118 Editor: anonymous Comment: converted to 1.6 markup ← Revision 8 as of 2013-05-08 16:33:48 → ⇥ Size: 3164 Editor: RogerHui Comment: Deletions are marked like this. Additions are marked like this. Line 100: Line 100: ''Some Uses of { and }'' by Roger Hui, APL 87 Conference Proceedings, May 10-14, 1987. ''[[http://www.jsoftware.com/papers/from.htm|Some Uses of { and }]]''by Roger Hui, APL 87 Conference Proceedings, May 10-14, 1987.

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
)```