APL Wiki
Pascal's Triangle: A Solution
The following solution is a one-liner which makes use of Dyalog-specific extensions to APL
Pascal←{0~¨⍨a⌽⊃⌽∊¨0,¨¨a∘!¨a←⌽⍳⍵}
Pascal 10
1
1 1
1 2 1
1 3 3 1
1 4 6 4 1
1 5 10 10 5 1
1 6 15 20 15 6 1
1 7 21 35 35 21 7 1
1 8 28 56 70 56 28 8 1
1 9 36 84 126 126 84 36 9 1
An alternative solution
Here's another solution which should work with most versions of APL. The function Pascal has been split over three lines for clarity
∇R←Pascal N;A;⎕IO
[1] ⎕IO←0
[2] R←(N+A)⌽((2×N)⍴1 ¯1)\⍉A∘.!A←⍳N
[3] ((0=,R)/,R)←⊂⍬
∇Let's investigate this solution step by step...
As the problem states, it's not too hard to generate the numbers needed. We can use APL's Binomial function ! For example 5!9 gives 126, which we find on the last row. If we use Binomial with an Outer Product ∘.! we can see the numbers we need:
(0 1 2 3 4 5 6 7 8 9) ∘.! (0 1 2 3 4 5 6 7 8 9) 1 1 1 1 1 1 1 1 1 1 0 1 2 3 4 5 6 7 8 9 0 0 1 3 6 10 15 21 28 36 0 0 0 1 4 10 20 35 56 84 0 0 0 0 1 5 15 35 70 126 0 0 0 0 0 1 6 21 56 126 0 0 0 0 0 0 1 7 28 84 0 0 0 0 0 0 0 1 8 36 0 0 0 0 0 0 0 0 1 9 0 0 0 0 0 0 0 0 0 1
This contains the triangle numbers but we need to flip it about the diagonal - i.e. exchange rows and columns - which we can do with APL's Transpose function, ⍉. So the first part of our solution is:
N←10
⎕IO←0
⍉A∘.!A←⍳N
1 0 0 0 0 0 0 0 0 0
1 1 0 0 0 0 0 0 0 0
1 2 1 0 0 0 0 0 0 0
1 3 3 1 0 0 0 0 0 0
1 4 6 4 1 0 0 0 0 0
1 5 10 10 5 1 0 0 0 0
1 6 15 20 15 6 1 0 0 0
1 7 21 35 35 21 7 1 0 0
1 8 28 56 70 56 28 8 1 0
1 9 36 84 126 126 84 36 9 1The next thing to take care of is arranging the numbers into the triangular shaped result. First of all we insert a column of zeros between each existing column. One way to do this is to use APL's Expand function, \.
((2×N)⍴1 ¯1)\⍉A∘.!A←⍳N 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 2 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 3 0 3 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 4 0 6 0 4 0 1 0 0 0 0 0 0 0 0 0 0 0 1 0 5 0 10 0 10 0 5 0 1 0 0 0 0 0 0 0 0 0 1 0 6 0 15 0 20 0 15 0 6 0 1 0 0 0 0 0 0 0 1 0 7 0 21 0 35 0 35 0 21 0 7 0 1 0 0 0 0 0 1 0 8 0 28 0 56 0 70 0 56 0 28 0 8 0 1 0 0 0 1 0 9 0 36 0 84 0 126 0 126 0 84 0 36 0 9 0 1 0
Now we need to adjust the result so that our columns line up in the required way. We can do this by rotating the first row by 10 positions to the left, the second row by 11 positions, etc. We can do this using the Rotate function, ⌽, with a left argument specifying the rotation count for each row:
R←(N+A)⌽((2×N)⍴1 ¯1)\⍉A∘.!A←⍳N
R
0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 1 0 1 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 1 0 2 0 1 0 0 0 0 0 0 0
0 0 0 0 0 0 0 1 0 3 0 3 0 1 0 0 0 0 0 0
0 0 0 0 0 0 1 0 4 0 6 0 4 0 1 0 0 0 0 0
0 0 0 0 0 1 0 5 0 10 0 10 0 5 0 1 0 0 0 0
0 0 0 0 1 0 6 0 15 0 20 0 15 0 6 0 1 0 0 0
0 0 0 1 0 7 0 21 0 35 0 35 0 21 0 7 0 1 0 0
0 0 1 0 8 0 28 0 56 0 70 0 56 0 28 0 8 0 1 0
0 1 0 9 0 36 0 84 0 126 0 126 0 84 0 36 0 9 0 1
We're nearly there! But we want to display a blank instead of a 0 in all the positions where a 0 occurs. How do we do this?
The final step comes from a realisation that APL will print a blank when displaying an empty numeric vector. Most APLs allow you to use the Zilde symbol, ⍬, which is equivalent to (0⍴0). Here's an example of APL displaying a nested array in which some items are empty vectors:
2 3⍴⍬ 1 ⍬ 1 ⍬ 1
1
1 1As you can see, it looks like the top of the Pascal's triangle we want.
So the final step is to use Selective Specification. We use a selection expression which selects only the 0 elements of R and replace them with empty numeric vectors:
((0=,R)/,R)←⊂⍬
R
1
1 1
1 2 1
1 3 3 1
1 4 6 4 1
1 5 10 10 5 1
1 6 15 20 15 6 1
1 7 21 35 35 21 7 1
1 8 28 56 70 56 28 8 1
1 9 36 84 126 126 84 36 9 1<< The task