123456789101112131415161718192021222324252627282930313233343536373839 |
- #!/usr/bin/ruby
- # Fast algorithm for computing Aitken's array.
- # See also:
- # https://oeis.org/A011971 -- Aitken's array
- # https://en.wikipedia.org/wiki/Bell_number
- func aitken_array (n) {
- var A = [1]
- [[1]] + (n-1).of {
- A = [A[-1], A...].accumulate
- }
- }
- func aitken_array_recmap (n) {
- [[1]].recmap {|A|
- A.len >= n ? break : [[A[-1], A...].accumulate]
- }
- }
- aitken_array(10).each { .say }
- assert_eq(aitken_array(10), aitken_array_recmap(10))
- __END__
- [1]
- [1, 2]
- [2, 3, 5]
- [5, 7, 10, 15]
- [15, 20, 27, 37, 52]
- [52, 67, 87, 114, 151, 203]
- [203, 255, 322, 409, 523, 674, 877]
- [877, 1080, 1335, 1657, 2066, 2589, 3263, 4140]
- [4140, 5017, 6097, 7432, 9089, 11155, 13744, 17007, 21147]
- [21147, 25287, 30304, 36401, 43833, 52922, 64077, 77821, 94828, 115975]
|