Stirling numbers of the second kind: Difference between revisions
Content added Content deleted
m (Updated description and link for Fōrmulæ solution) |
|||
Line 840: | Line 840: | ||
12 0 1 2047 86526 611501 1379400 1323652 627396 159027 22275 1705 66 1 |
12 0 1 2047 86526 611501 1379400 1323652 627396 159027 22275 1705 66 1 |
||
The maximum value of S2(100, k) = |
The maximum value of S2(100, k) = |
||
7769730053598745155212806612787584787397878128370115840974992570102386086289805848025074822404843545178960761551674 |
|||
(115 digits, k = 28) |
|||
</pre> |
|||
=={{header|jq}}== |
|||
'''Adapted from [[#Wren|Wren]]''' |
|||
'''Works with gojq, the Go implementation of jq''' |
|||
The following program is more complex than it otherwise would be because |
|||
it ensures that the cache of values computed in the first part |
|||
is available in the second part. |
|||
<lang jq>def lpad($len): tostring | ($len - length) as $l | (" " * $l)[:$l] + .; |
|||
# Input: {computed} (the cache) |
|||
# Output: {computed, result} |
|||
def stirling2($n; $k): |
|||
"\($n),\($k)" as $key |
|||
| if .computed[$key] then .result = .computed[$key] |
|||
elif ($n == 0 and $k == 0) then .result = 1 |
|||
elif (($n > 0 and $k == 0) or ($n == 0 and $k > 0)) then .result = 0 |
|||
elif ($k == $n) then .result = 1 |
|||
elif ($k > $n) then .result = 0 |
|||
else stirling2($n-1; $k-1) as $s1 |
|||
| ($s1 | stirling2($n-1; $k)) as $s2 |
|||
| ($s1.result + ($k * $s2.result)) as $result |
|||
| $s2 |
|||
| .computed[$key] = $result |
|||
| .result = $result |
|||
end ; |
|||
# Set .emit to a table of values and .computed to a cache of stirling2 values |
|||
# Output: {emit, computed} |
|||
def part1(max): |
|||
{emit: "Unsigned Stirling numbers of the second kind:"} |
|||
| .emit += "\n" + "n/k" + |
|||
([range(0; max+1) | lpad(10)] | join("")) |
|||
| reduce range(0; max+1) as $n ( .computed = {}; |
|||
.emit += "\n" + ($n | lpad(3)) |
|||
| reduce range(0; $n+1) as $k (.; |
|||
stirling2($n; $k) |
|||
| .emit += (.result | lpad(10) ) )) ; |
|||
# "The maximum value of S2($m, k) ..." |
|||
# Input: {computed} |
|||
def part2($m): |
|||
"The maximum value of S2(\($m), k) =", |
|||
first( |
|||
foreach range(1;$m+1) as $k ({computed:{}, previous: 0}; |
|||
stirling2($m; $k) as $current |
|||
| if ($current.result > .previous) |
|||
then .previous = $current.result |
|||
else |
|||
.emit = "\(.previous)\n(\(.previous|tostring|length) digits, k = \($k - 1))" |
|||
end; |
|||
select(.emit).emit) ); |
|||
part1(12) |
|||
| .emit, |
|||
part2(100) |
|||
</lang> |
|||
{{out}} |
|||
<pre> |
|||
Unsigned Stirling numbers of the second kind: |
|||
n/k 0 1 2 3 4 5 6 7 8 9 10 11 12 |
|||
0 1 |
|||
1 0 1 |
|||
2 0 1 1 |
|||
3 0 1 3 1 |
|||
4 0 1 7 6 1 |
|||
5 0 1 15 25 10 1 |
|||
6 0 1 31 90 65 15 1 |
|||
7 0 1 63 301 350 140 21 1 |
|||
8 0 1 127 966 1701 1050 266 28 1 |
|||
9 0 1 255 3025 7770 6951 2646 462 36 1 |
|||
10 0 1 511 9330 34105 42525 22827 5880 750 45 1 |
|||
11 0 1 1023 28501 145750 246730 179487 63987 11880 1155 55 1 |
|||
12 0 1 2047 86526 611501 1379400 1323652 627396 159027 22275 1705 66 1 |
|||
The maximum value of S2(100, k) = |
|||
7769730053598745155212806612787584787397878128370115840974992570102386086289805848025074822404843545178960761551674 |
7769730053598745155212806612787584787397878128370115840974992570102386086289805848025074822404843545178960761551674 |
||
(115 digits, k = 28) |
(115 digits, k = 28) |