Talk:Pascal's triangle: Difference between revisions
m (Reverted edits by 193.156.194.5 (Talk) to last revision by UnderBot) |
(→J Explanation: new section) |
||
Line 14: | Line 14: | ||
I think that maybe all example output should follow the task description format of an isosceles triangle. --[[User:Paddy3118|Paddy3118]] 08:59, 27 December 2009 (UTC) |
I think that maybe all example output should follow the task description format of an isosceles triangle. --[[User:Paddy3118|Paddy3118]] 08:59, 27 December 2009 (UTC) |
||
:That's not always easy to do. I think the important part of the task is the generation of each row. We don't need to complicate it with output formatting that isn't important to the theory involved. --[[User:Mwn3d|Mwn3d]] 18:37, 27 December 2009 (UTC) |
:That's not always easy to do. I think the important part of the task is the generation of each row. We don't need to complicate it with output formatting that isn't important to the theory involved. --[[User:Mwn3d|Mwn3d]] 18:37, 27 December 2009 (UTC) |
||
== J Explanation == |
|||
<lang j>!/~@i. N</lang> |
|||
The triangle itself is simply the table of number-of-combinations, for the first N non-negative integers. |
|||
<lang J> !/~i.5 |
|||
1 1 1 1 1 |
|||
0 1 2 3 4 |
|||
0 0 1 3 6 |
|||
0 0 0 1 4 |
|||
0 0 0 0 1</lang> |
|||
That is, [[wp:Combination|C(n,k)]] for all <tt>n,k in [0 .. n)</tt>. J's notation for <tt>C(n,k)</tt> is <code>k ! n</code> (mnemonic: combinations are closely related to factorials, which are denoted by <tt>!</tt> in math). |
|||
So, for example, the number of ways to choose a poker hand (5 cards from the deck of 52): |
|||
<lang j> 5!52 |
|||
2598960</lang> |
|||
So <code>!</code> is the mathematical choose function. As for <code>/~@i.</code>, the <code>/~</code> would be "table of" and <code>i.</code> "the first N non-negative integers (i.e. 0 .. N-1)". (And <code>@</code> is just glue.) |
|||
But, formatting the thing takes a bit more effort: |
|||
<lang j> (-@|. |."_1 [: ;:inv [: ":@-.&0&.>@|: !/~)@i. 5 |
|||
1 |
|||
1 1 |
|||
1 2 1 |
|||
1 3 3 1 |
|||
1 4 6 4 1</lang> |
|||
Here, we have refactored the operation slightly: |
|||
<lang j>(stuff)@i.5</lang> makes the sequence 0 1 2 3 4 available every odd verb (counting from the right) in stuff |
|||
The "stuff" are (from right to left) |
|||
<lang j>!/~</lang> build our table of combinations |
|||
<lang j>":@-.&0&.>@|:</lang> transpose that array, and for each number remove it if it is zero, format it as a string and put it in a box |
|||
<lang j>[:</lang> placeholder meaning "no verb here" the verb to the right does not get a left argument |
|||
<lang j>;:inv</lang> combine the strings in rows of boxes as word (with spaces between them |
|||
<lang j>[:</lang> placeholder meaning "no verb here" the verb to the right does not get a left argument |
|||
<lang j>|."_1</lang> rotate each item (each row of characters) by the indicated amount (rotation would be moving contents left except that the amounts are negative). |
|||
<lang j>-@|.</lang> reverse and negate the argument (resulting in the negative sequence _4 _3 _2 _1 0) |
Revision as of 14:55, 11 June 2010
Right Output Format?
Thw task bdescription says the tringle looks like this:
1 1 1 1 2 1 1 3 3 1
And yet, some examples are showing the easier to construct:
1 1 1 1 2 1 1 3 3 1
I think that maybe all example output should follow the task description format of an isosceles triangle. --Paddy3118 08:59, 27 December 2009 (UTC)
- That's not always easy to do. I think the important part of the task is the generation of each row. We don't need to complicate it with output formatting that isn't important to the theory involved. --Mwn3d 18:37, 27 December 2009 (UTC)
J Explanation
<lang j>!/~@i. N</lang>
The triangle itself is simply the table of number-of-combinations, for the first N non-negative integers.
<lang J> !/~i.5 1 1 1 1 1 0 1 2 3 4 0 0 1 3 6 0 0 0 1 4 0 0 0 0 1</lang>
That is, C(n,k) for all n,k in [0 .. n). J's notation for C(n,k) is k ! n
(mnemonic: combinations are closely related to factorials, which are denoted by ! in math).
So, for example, the number of ways to choose a poker hand (5 cards from the deck of 52): <lang j> 5!52 2598960</lang>
So !
is the mathematical choose function. As for /~@i.
, the /~
would be "table of" and i.
"the first N non-negative integers (i.e. 0 .. N-1)". (And @
is just glue.)
But, formatting the thing takes a bit more effort:
<lang j> (-@|. |."_1 [: ;:inv [: ":@-.&0&.>@|: !/~)@i. 5
1 1 1 1 2 1 1 3 3 1 1 4 6 4 1</lang>
Here, we have refactored the operation slightly:
<lang j>(stuff)@i.5</lang> makes the sequence 0 1 2 3 4 available every odd verb (counting from the right) in stuff
The "stuff" are (from right to left) <lang j>!/~</lang> build our table of combinations <lang j>":@-.&0&.>@|:</lang> transpose that array, and for each number remove it if it is zero, format it as a string and put it in a box <lang j>[:</lang> placeholder meaning "no verb here" the verb to the right does not get a left argument <lang j>;:inv</lang> combine the strings in rows of boxes as word (with spaces between them <lang j>[:</lang> placeholder meaning "no verb here" the verb to the right does not get a left argument <lang j>|."_1</lang> rotate each item (each row of characters) by the indicated amount (rotation would be moving contents left except that the amounts are negative). <lang j>-@|.</lang> reverse and negate the argument (resulting in the negative sequence _4 _3 _2 _1 0)