Combinations and permutations: Difference between revisions
Content added Content deleted
Thundergnat (talk | contribs) (Rename Perl 6 -> Raku, alphabetize, minor clean-up) |
|||
Line 1,373: | Line 1,373: | ||
1000 C 333 = 5776134553147651669777486323549601722339... (235 more digits) |
1000 C 333 = 5776134553147651669777486323549601722339... (235 more digits) |
||
</pre> |
</pre> |
||
=={{header|M2000 Interpreter}}== |
=={{header|M2000 Interpreter}}== |
||
<lang M2000 Interpreter> |
<lang M2000 Interpreter> |
||
Line 1,479: | Line 1,480: | ||
C(600,20)=2801445153584 C(600,40)=266319106596345 C(600,60)=14409368913 C(600,80)=271441 C(600,100)=52868467287780595308 |
C(600,20)=2801445153584 C(600,40)=266319106596345 C(600,60)=14409368913 C(600,80)=271441 C(600,100)=52868467287780595308 |
||
C(800,20)=1925279023672620 C(800,40)=23121069591511231041 C(800,60)=18702067923763447158 C(800,80)=1193559552292625 C(800,100)=172727802 |
C(800,20)=1925279023672620 C(800,40)=23121069591511231041 C(800,60)=18702067923763447158 C(800,80)=1193559552292625 C(800,100)=172727802 |
||
C(1000,20)=1239329180287869852 C(1000,40)=1937726921514640866484017 C(1000,60)=149470629867337347460963500 C(1000,80)=1269150275532146867313740 C(1000,100)=10088410532027029794548 |
C(1000,20)=1239329180287869852 C(1000,40)=1937726921514640866484017 C(1000,60)=149470629867337347460963500 C(1000,80)=1269150275532146867313740 C(1000,100)=10088410532027029794548 |
||
=={{header|Maple}}== |
=={{header|Maple}}== |
||
Line 1,678: | Line 1,679: | ||
Since the output is almost the same as perl6's, and this is only a Draft RosettaCode task, I'm not going to bother including the output of the program. |
Since the output is almost the same as perl6's, and this is only a Draft RosettaCode task, I'm not going to bother including the output of the program. |
||
=={{header|Perl 6}}== |
|||
Perl 6 can't compute arbitrary large floating point values, thus we will use logarithms, as is often needed when dealing with combinations. We'll also use a Stirling method to approximate <math>\ln(n!)</math>: |
|||
<math>\ln n! \approx |
|||
\frac{1}{2}\ln(2\pi n) + n\ln\left(\frac{n}{e} + \frac{1}{12 e n}\right)</math> |
|||
Notice that Perl6 can process arbitrary long integers, though. So it's not clear whether using floating points is useful in this case. |
|||
<lang perl6>multi P($n, $k) { [*] $n - $k + 1 .. $n } |
|||
multi C($n, $k) { P($n, $k) / [*] 1 .. $k } |
|||
sub lstirling(\n) { |
|||
n < 10 ?? lstirling(n+1) - log(n+1) !! |
|||
.5*log(2*pi*n)+ n*log(n/e+1/(12*e*n)) |
|||
} |
|||
role Logarithm { |
|||
method gist { |
|||
my $e = (self/10.log).Int; |
|||
sprintf "%.8fE%+d", exp(self - $e*10.log), $e; |
|||
} |
|||
} |
|||
multi P($n, $k, :$float!) { |
|||
(lstirling($n) - lstirling($n -$k)) |
|||
but Logarithm |
|||
} |
|||
multi C($n, $k, :$float!) { |
|||
(lstirling($n) - lstirling($n -$k) - lstirling($k)) |
|||
but Logarithm |
|||
} |
|||
say "Exact results:"; |
|||
for 1..12 -> $n { |
|||
my $p = $n div 3; |
|||
say "P($n, $p) = ", P($n, $p); |
|||
} |
|||
for 10, 20 ... 60 -> $n { |
|||
my $p = $n div 3; |
|||
say "C($n, $p) = ", C($n, $p); |
|||
} |
|||
say ''; |
|||
say "Floating point approximations:"; |
|||
for 5, 50, 500, 1000, 5000, 15000 -> $n { |
|||
my $p = $n div 3; |
|||
say "P($n, $p) = ", P($n, $p, :float); |
|||
} |
|||
for 100, 200 ... 1000 -> $n { |
|||
my $p = $n div 3; |
|||
say "C($n, $p) = ", C($n, $p, :float); |
|||
}</lang> |
|||
{{out}} |
|||
<pre>Exact results: |
|||
P(1, 0) = 1 |
|||
P(2, 0) = 1 |
|||
P(3, 1) = 3 |
|||
P(4, 1) = 4 |
|||
P(5, 1) = 5 |
|||
P(6, 2) = 30 |
|||
P(7, 2) = 42 |
|||
P(8, 2) = 56 |
|||
P(9, 3) = 504 |
|||
P(10, 3) = 720 |
|||
P(11, 3) = 990 |
|||
P(12, 4) = 11880 |
|||
C(10, 3) = 120 |
|||
C(20, 6) = 38760 |
|||
C(30, 10) = 30045015 |
|||
C(40, 13) = 12033222880 |
|||
C(50, 16) = 4923689695575 |
|||
C(60, 20) = 4191844505805495 |
|||
Floating point approximations: |
|||
P(5, 1) = 5.00000000E+0 |
|||
P(50, 16) = 1.03017326E+26 |
|||
P(500, 166) = 3.53487492E+434 |
|||
P(1000, 333) = 5.96932629E+971 |
|||
P(5000, 1666) = 6.85674576E+6025 |
|||
P(15000, 5000) = 9.64985399E+20469 |
|||
C(100, 33) = 2.94692433E+26 |
|||
C(200, 66) = 7.26975256E+53 |
|||
C(300, 100) = 4.15825147E+81 |
|||
C(400, 133) = 1.25794868E+109 |
|||
C(500, 166) = 3.92602839E+136 |
|||
C(600, 200) = 2.50601778E+164 |
|||
C(700, 233) = 8.10320356E+191 |
|||
C(800, 266) = 2.64562336E+219 |
|||
C(900, 300) = 1.74335637E+247 |
|||
C(1000, 333) = 5.77613455E+274</pre> |
|||
=={{header|Phix}}== |
=={{header|Phix}}== |
||
Line 1,904: | Line 1,813: | ||
(I'll spare this page from yet another big listing of samples...) |
(I'll spare this page from yet another big listing of samples...) |
||
=={{header|Raku}}== |
|||
(formerly Perl 6) |
|||
Perl 6 can't compute arbitrary large floating point values, thus we will use logarithms, as is often needed when dealing with combinations. We'll also use a Stirling method to approximate <math>\ln(n!)</math>: |
|||
<math>\ln n! \approx |
|||
\frac{1}{2}\ln(2\pi n) + n\ln\left(\frac{n}{e} + \frac{1}{12 e n}\right)</math> |
|||
Notice that Perl6 can process arbitrary long integers, though. So it's not clear whether using floating points is useful in this case. |
|||
<lang perl6>multi P($n, $k) { [*] $n - $k + 1 .. $n } |
|||
multi C($n, $k) { P($n, $k) / [*] 1 .. $k } |
|||
sub lstirling(\n) { |
|||
n < 10 ?? lstirling(n+1) - log(n+1) !! |
|||
.5*log(2*pi*n)+ n*log(n/e+1/(12*e*n)) |
|||
} |
|||
role Logarithm { |
|||
method gist { |
|||
my $e = (self/10.log).Int; |
|||
sprintf "%.8fE%+d", exp(self - $e*10.log), $e; |
|||
} |
|||
} |
|||
multi P($n, $k, :$float!) { |
|||
(lstirling($n) - lstirling($n -$k)) |
|||
but Logarithm |
|||
} |
|||
multi C($n, $k, :$float!) { |
|||
(lstirling($n) - lstirling($n -$k) - lstirling($k)) |
|||
but Logarithm |
|||
} |
|||
say "Exact results:"; |
|||
for 1..12 -> $n { |
|||
my $p = $n div 3; |
|||
say "P($n, $p) = ", P($n, $p); |
|||
} |
|||
for 10, 20 ... 60 -> $n { |
|||
my $p = $n div 3; |
|||
say "C($n, $p) = ", C($n, $p); |
|||
} |
|||
say ''; |
|||
say "Floating point approximations:"; |
|||
for 5, 50, 500, 1000, 5000, 15000 -> $n { |
|||
my $p = $n div 3; |
|||
say "P($n, $p) = ", P($n, $p, :float); |
|||
} |
|||
for 100, 200 ... 1000 -> $n { |
|||
my $p = $n div 3; |
|||
say "C($n, $p) = ", C($n, $p, :float); |
|||
}</lang> |
|||
{{out}} |
|||
<pre>Exact results: |
|||
P(1, 0) = 1 |
|||
P(2, 0) = 1 |
|||
P(3, 1) = 3 |
|||
P(4, 1) = 4 |
|||
P(5, 1) = 5 |
|||
P(6, 2) = 30 |
|||
P(7, 2) = 42 |
|||
P(8, 2) = 56 |
|||
P(9, 3) = 504 |
|||
P(10, 3) = 720 |
|||
P(11, 3) = 990 |
|||
P(12, 4) = 11880 |
|||
C(10, 3) = 120 |
|||
C(20, 6) = 38760 |
|||
C(30, 10) = 30045015 |
|||
C(40, 13) = 12033222880 |
|||
C(50, 16) = 4923689695575 |
|||
C(60, 20) = 4191844505805495 |
|||
Floating point approximations: |
|||
P(5, 1) = 5.00000000E+0 |
|||
P(50, 16) = 1.03017326E+26 |
|||
P(500, 166) = 3.53487492E+434 |
|||
P(1000, 333) = 5.96932629E+971 |
|||
P(5000, 1666) = 6.85674576E+6025 |
|||
P(15000, 5000) = 9.64985399E+20469 |
|||
C(100, 33) = 2.94692433E+26 |
|||
C(200, 66) = 7.26975256E+53 |
|||
C(300, 100) = 4.15825147E+81 |
|||
C(400, 133) = 1.25794868E+109 |
|||
C(500, 166) = 3.92602839E+136 |
|||
C(600, 200) = 2.50601778E+164 |
|||
C(700, 233) = 8.10320356E+191 |
|||
C(800, 266) = 2.64562336E+219 |
|||
C(900, 300) = 1.74335637E+247 |
|||
C(1000, 333) = 5.77613455E+274</pre> |
|||
=={{header|REXX}}== |
=={{header|REXX}}== |