Jordan Scales
Feb 11, 2018 · 5 min read

Following my previous post on the Fibonacci numbers, here’s a quick post on generating another famous mathematical sequence — Pascal’s Triangle.

    1  
1 1
1 2 1
1 3 3 1
1 4 6 4 1

Quick Background

Pascal’s triangle contains numbers formed by binomial coefficients (often referred to as “N choose K”), but there’s a simple and elegant way to generate it: each item is the sum of the two numbers above it.

 1 3 3 1 
1 4 6 4 1

We see here that the bold 6 is formed by adding the two threes above it.

 1 3 3 1  
1 4 6 4 1

Similarly, we see the 4 is formed by adding the 1 and 3, and the 1 is formed by adding 1 to nothing (0).

Summing pairs

Before we get started go ahead and grab yourself a copy of the J runtime if you haven’t already.

Let’s start by grabbing the first 5 integers using the “integers” verb i.

  i. 5 
0 1 2 3 4

We can use the “same” verb ] to echo whatever we pass into it.

  ] 10 
10
] i.5
0 1 2 3 4

Our primary tool will be J’s infix adverb \. This single backslash allows us to scan through a list of numbers in groups and apply a function to them.

Let’s scan every 3 items and pass them to the “same” verb ].

  3 ]\ i.5 
0 1 2
1 2 3
2 3 4

We can see here that J looks through 0 1 2 3 4 in overlapping groups of 3. So we'll have 0 1 2, followed by 1 2 3, etc.

By changing the number in front, we can scan in groups of 2.

  2 ]\ i.5 
0 1
1 2
2 3
3 4

Let’s swap out our boring ] for something more interesting: +/, which sums a list of numbers.

  3 +/\ i.5 
3 6 9
+/ 0 1 2
3
+/ 1 2 3
6
+/ 2 3 4
9

Similarly, we can do this pairwise.

  2 +/\ i.5 
1 3 5 7

Pretty nifty right?

Row after row

So why is this useful? Well, if we take another look at our triangle:

    1  
1 1
1 2 1
1 3 3 1
1 4 6 4 1

We can see that the next row, 1 5 10 10 5 1 can be formed by this exact strategy: summing each pair of numbers to generate the number beneath it.

  2 +/\ 1 3 3 1 
4 6 4
2 +/\ 1 4 6 4 1
5 10 10 5

Well, almost. Our issue is that we’re missing out on the 1s on either side! This is because our infix operator \ starts with +/ 1 4 to get 5 - skipping over the 1.

To fix this, let’s surround our row with 0s.

  2 ]\ 0 1 3 3 1 0 
0 1
1 3
3 3
3 1
1 0
2 +/\ 0 1 3 3 1 0
1 4 6 4 1
2 +/\ 0 1 4 6 4 1 0
1 5 10 10 5 1

Much better. So how do we surround with 0s automatically?

The append verb , is used to join items and lists.

  0 , 1 
0 1
1 2 3 , 7 8 9
1 2 3 7 8 9

The “bond” verb & allows us to partially evaluate a verb that normally expects items on both sides.

  1 + 2 
3
(1&+) 2
3
4 % 2 NB. "%" is division!
2
(%&2) 4
2

We can bind our append verb to add a 0 to either side.

  (0&,) 5 6 7 
0 5 6 7
(,&0) 5 6 7
5 6 7 0

We can also do both.

  (0&,) (,&0) 5 6 7 
0 5 6 7 0
(,&0) (0&,) 5 6 7
0 5 6 7 0

Putting it all together: we can append 0 on either side of our row:

  (0&,) (,&0) 1 4 6 4 1 
0 1 4 6 4 1 0

And sum each pair:

  2 +/\ (0&,) (,&0) 1 4 6 4 1 
1 5 10 10 5 1

All together now

Let’s wrap this in our own verb called next. "y" gives us access to the argument(s) passed in.

  next =: verb : '2 +/\ (0&,) (,&0) y' 
next 1 3 3 1
1 4 6 4 1
next 1 4 6 4 1
1 5 10 10 5 1

Fortunately, next works just fine on the first row of our triangle: a single 1.

  next 1 
1 1

We can apply next multiple times.

  next 1 
1 1
next 1 1
1 2 1
next next 1
1 2 1
next next next next 1
1 4 6 4 1

We can use the “power” verb ^: to do this for us.

  (next^:0) 1 
1
(next^:1) 1
1 1
(next^:5) 1
1 5 10 10 5 1

We can also pass a list to ^: to generate multiple powers at the same time.

  (next^:(i.7)) 1 
1 0 0 0 0 0 0
1 1 0 0 0 0 0
1 2 1 0 0 0 0
1 3 3 1 0 0 0
1 4 6 4 1 0 0
1 5 10 10 5 1 0
1 6 15 20 15 6 1

We can store this as another verb to generate Pascal’s Triangle. We’ll also simplify our definition of next using the “atop” verb @

  next =: 2 +/\ (0&,) @ (,&0)
pascal =: verb : '(next^:(i.y)) 1'
NB. We can also inline `next` entirely
pascal =: verb : '((2 +/\ (0&,) @ (,&0))^:(i.y)) 1'
pascal 10
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 1

🎉 🎉

Thanks to the powers of \ and ^:, we can intuitively generate Pascal's Triangle in a few dozen characters.

J makes operations on lists and matrices a breeze, and contains a number of interesting ideas for function composition and application. I hope you found this post interesting and give a look at what J has to offer.

I think you’ll be pleasantly surprised at how fun it is.

Thanks for reading — and feel free to give me a follow on twitter dot com for more J goodness.


Originally published at thatjdanisso.cool.

Jordan Scales

Written by

JavaScript clickbait enthusiast. Giving you superpowers @Stripe. Door-to-door accessibility salesman. http://shade.cool.

Welcome to a place where words matter. On Medium, smart voices and original ideas take center stage - with no ads in sight. Watch
Follow all the topics you care about, and we’ll deliver the best stories for you to your homepage and inbox. Explore
Get unlimited access to the best stories on Medium — and support writers while you’re at it. Just $5/month. Upgrade