Combinations and permutations: Difference between revisions
Add Lua implementation
No edit summary |
(Add Lua implementation) |
||
| (13 intermediate revisions by 5 users not shown) | |||
Line 530:
return 0;
}</syntaxhighlight>
=={{header|C#}}==
{{trans|Java}}
<syntaxhighlight lang="C#">
using System;
using System.Numerics;
class CombinationsAndPermutations
{
public static void Main(string[] args)
{
Console.WriteLine(double.MaxValue);
Console.WriteLine("A sample of permutations from 1 to 12 with exact Integer arithmetic:");
for (int n = 1; n <= 12; n++)
{
int k = n / 2;
Console.WriteLine($"{n} P {k} = {Permutation(n, k)}");
}
Console.WriteLine();
Console.WriteLine("A sample of combinations from 10 to 60 with exact Integer arithmetic:");
for (int n = 10; n <= 60; n += 5)
{
int k = n / 2;
Console.WriteLine($"{n} C {k} = {Combination(n, k)}");
}
Console.WriteLine();
Console.WriteLine("A sample of permutations from 5 to 15000 displayed in floating point arithmetic:");
Console.WriteLine($"{5} P {2} = {Display(Permutation(5, 2), 50)}");
for (int n = 1000; n <= 15000; n += 1000)
{
int k = n / 2;
Console.WriteLine($"{n} P {k} = {Display(Permutation(n, k), 50)}");
}
Console.WriteLine();
Console.WriteLine("A sample of combinations from 100 to 1000 displayed in floating point arithmetic:");
for (int n = 100; n <= 1000; n += 100)
{
int k = n / 2;
Console.WriteLine($"{n} C {k} = {Display(Combination(n, k), 50)}");
}
}
private static string Display(BigInteger val, int precision)
{
string s = val.ToString();
// Ensure that we don't try to take a substring longer than what's available.
int actualPrecision = Math.Min(precision, s.Length - 1); // Adjusted to ensure it doesn't exceed string length
System.Text.StringBuilder sb = new System.Text.StringBuilder();
if (s.Length > 1) // Check if the string has more than one character
{
sb.Append(s.Substring(0, 1));
sb.Append(".");
sb.Append(s.Substring(1, actualPrecision-1));
}
else
{
// If the string is only one digit, no need to insert a decimal point.
sb.Append(s);
}
sb.Append(" * 10^");
sb.Append(s.Length - 1);
return sb.ToString();
}
public static BigInteger Combination(int n, int k)
{
// Select value with smallest intermediate results
// combination(n, k) = combination(n, n-k)
if (n - k < k)
{
k = n - k;
}
BigInteger result = Permutation(n, k);
while (k > 0)
{
result = result / k;
k--;
}
return result;
}
public static BigInteger Permutation(int n, int k)
{
BigInteger result = BigInteger.One;
for (int i = n; i >= n - k + 1; i--)
{
result = result * i;
}
return result;
}
}
</syntaxhighlight>
{{out}}
<pre>
1.79769313486232E+308
A sample of permutations from 1 to 12 with exact Integer arithmetic:
1 P 0 = 1
2 P 1 = 2
3 P 1 = 3
4 P 2 = 12
5 P 2 = 20
6 P 3 = 120
7 P 3 = 210
8 P 4 = 1680
9 P 4 = 3024
10 P 5 = 30240
11 P 5 = 55440
12 P 6 = 665280
A sample of combinations from 10 to 60 with exact Integer arithmetic:
10 C 5 = 252
15 C 7 = 6435
20 C 10 = 184756
25 C 12 = 5200300
30 C 15 = 155117520
35 C 17 = 4537567650
40 C 20 = 137846528820
45 C 22 = 4116715363800
50 C 25 = 126410606437752
55 C 27 = 3824345300380220
60 C 30 = 118264581564861424
A sample of permutations from 5 to 15000 displayed in floating point arithmetic:
5 P 2 = 2. * 10^1
1000 P 500 = 3.2978863640988537122024252070116261706996485697981 * 10^1433
2000 P 1000 = 8.2415012140674255266380217928953202425839550211348 * 10^3167
3000 P 1500 = 8.6229457673788561572282325050469704818001698192368 * 10^5015
4000 P 2000 = 5.5146268042637929575202252487087217092097210095831 * 10^6937
5000 P 2500 = 2.5959899179479570425022364594725223975158226787173 * 10^8914
6000 P 3000 = 6.4684674799045492726351265543133876130483115297807 * 10^10934
7000 P 3500 = 3.6978393541988590953223392044469547113117500019066 * 10^12991
8000 P 4000 = 2.8347416494109128583587900207169062803923698647730 * 10^15079
9000 P 4500 = 3.5613559022062915735922606191272180393638776777367 * 10^17194
10000 P 5000 = 6.7310091721588924046678115055013992269082753633190 * 10^19333
11000 P 5500 = 7.1714299723894354619599359891785521535675525394493 * 10^21494
12000 P 6000 = 4.4778633072110971517945389774618813158941392935141 * 10^23675
13000 P 6500 = 3.6571405647713639990172807053439865891697112165983 * 10^25874
14000 P 7000 = 1.5680448683572888099973548116924953997328821172933 * 10^28090
15000 P 7500 = 2.2454775022523692436484435950526532351441855443096 * 10^30321
A sample of combinations from 100 to 1000 displayed in floating point arithmetic:
100 C 50 = 1.0089134454556419333481249725 * 10^29
200 C 100 = 9.0548514656103281165404177077484163874504589675413 * 10^58
300 C 150 = 9.3759702772827452793193754439064084879232655700081 * 10^88
400 C 200 = 1.0295250013541443297297588032040198675721092538107 * 10^119
500 C 250 = 1.1674431578827768292093473476217661965923008118031 * 10^149
600 C 300 = 1.3510794199619426851447487797850453039723394544919 * 10^179
700 C 350 = 1.5857433585316795487607022764754299250587342835720 * 10^209
800 C 400 = 1.8804244186835312700958607615195351332156581822914 * 10^239
900 C 450 = 2.2474718820660159573188913903771345843514101350359 * 10^269
1000 C 500 = 2.7028824094543656951561469362597527549615200844654 * 10^299
</pre>
=={{header|C++}}==
Line 699 ⟶ 860:
84444202526779550201576117111844818124800000000000\
000000000</pre>
=={{header|EasyLang}}==
{{trans|Phix}}
<syntaxhighlight>
func perm x y .
z = 1
for i = x - y + 1 to x
z *= i
.
return z
.
func fact x .
z = 1
for i = 2 to x
z *= i
.
return z
.
func comb x y .
if x - y < y
y = x - y
.
return perm x y / fact y
.
#
e = 2.7182818284590452354
func log n .
return log10 n / log10 e
.
func lstirling n .
if n < 10
return lstirling (n + 1) - log (n + 1)
.
return 0.5 * log (2 * pi * n) + n * log (n / e + 1 / (12 * e * n))
.
func$ tolog v .
h = v div log 10
return pow e (v - h * log 10) & "e" & h
.
func$ permf n k .
return tolog (lstirling n - lstirling (n - k))
.
func$ combf n k .
return tolog (lstirling n - lstirling (n - k) - lstirling k)
.
print "=> Exact results:"
for n = 1 to 12
p = n div 3
print "P(" & n & "," & p & ")=" & perm n p
.
#
# double has 53 bits for integer
#
for n = 10 step 10 to 50
p = n div 3
print "C(" & n & "," & p & ")=" & comb n p
.
#
print ""
print "=> Floating point approximations:"
for n in [ 5 50 500 1000 5000 15000 ]
p = n div 3
print "P(" & n & "," & p & ")=" & permf n p
.
for n = 100 step 100 to 1000
p = n div 3
print "C(" & n & "," & p & ")=" & combf n p
.
</syntaxhighlight>
=={{header|EchoLisp}}==
Line 1,691 ⟶ 1,922:
900 C 300 = 1743356373296446642960730765085718347630... (208 more digits)
1000 C 333 = 5776134553147651669777486323549601722339... (235 more digits)
</pre>
=={{header|Lua}}==
{{trans|Perl}}
<syntaxhighlight lang="Lua">
-- Helper function to display results in scientific notation corrected
function eshow(x)
local e = math.floor(x / math.log(10))
local exponentiated = math.exp(x - e * math.log(10))
-- Corrected format specifier from %.8Fe%+d to %.8e, and manually constructing the scientific notation if needed
return string.format("%.8e", exponentiated) .. "e" .. tostring(e)
end
-- The rest of the functions remain the same
-- Define the factorial function for permutations
function P(n, k)
local x = 1
for i = n - k + 1, n do
x = x * i
end
return x
end
-- Define the function for big permutations using logarithms
function P_big(n, k)
local x = 0
for i = n - k + 1, n do
x = x + math.log(i)
end
return eshow(x)
end
-- Define the combinations function
function C(n, k)
local x = 1
for i = 1, k do
x = x * (n - i + 1) / i
end
return x
end
-- Define the function for big combinations using logarithms
function C_big(n, k)
local x = 0
for i = 1, k do
x = x + math.log(n - i + 1) - math.log(i)
end
return math.exp(x)
end
-- Function to showcase the calculations
function showoff(text, code, fname, ...)
local n = {...}
print("\nA sample of " .. text .. " from " .. n[1] .. " to " .. n[#n] .. "")
for _, v in ipairs(n) do
local k = math.floor(v / 3)
print(v, fname .. " " .. k .. " = ", code(v, k))
end
end
-- Examples of usage
showoff("Permutations", P, "P", 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12)
showoff("Combinations", C, "C", 10, 20, 30, 40, 50, 60)
showoff("Permutations", P_big, "P", 5, 50, 500, 1000, 5000, 15000)
showoff("Combinations", C_big, "C", 100, 200, 300, 400, 500, 600, 700, 800, 900, 1000)
</syntaxhighlight>
{{out}}
<pre>
A sample of Permutations from 1 to 12
1 P 0 = 1
2 P 0 = 1
3 P 1 = 3
4 P 1 = 4
5 P 1 = 5
6 P 2 = 30
7 P 2 = 42
8 P 2 = 56
9 P 3 = 504
10 P 3 = 720
11 P 3 = 990
12 P 4 = 11880
A sample of Combinations from 10 to 60
10 C 3 = 120.0
20 C 6 = 38760.0
30 C 10 = 30045015.0
40 C 13 = 12033222880.0
50 C 16 = 4923689695575.0
60 C 20 = 4.1918445058055e+15
A sample of Permutations from 5 to 15000
5 P 1 = 5.00000000e+00e0
50 P 16 = 1.03017325e+00e26
500 P 166 = 3.53487492e+00e434
1000 P 333 = 5.96932629e+00e971
5000 P 1666 = 6.85674576e+00e6025
15000 P 5000 = 9.64985399e+00e20469
A sample of Combinations from 100 to 1000
100 C 33 = 2.9469242702254e+26
200 C 66 = 7.2697525451696e+53
300 C 100 = 4.158251463258e+81
400 C 133 = 1.2579486841822e+109
500 C 166 = 3.9260283861944e+136
600 C 200 = 2.5060177832203e+164
700 C 233 = 8.1032035633383e+191
800 C 266 = 2.6456233626831e+219
900 C 300 = 1.7433563732974e+247
1000 C 333 = 5.776134553149e+274
</pre>
Line 2,505 ⟶ 2,848:
Ruby's Arrays have a permutation and a combination method which result in (lazy) enumerators. These Enumerators have a "size" method, which returns the size of the enumerator, or nil if it can’t be calculated lazily. (Since Ruby 2.0)
<syntaxhighlight lang="ruby">(1..60).to_a.combination(53).size #=> 386206920</syntaxhighlight>
=={{header|Rust}}==
{{trans|zig}}
Almost a verbatim port... the logic is retained but I renounce anyway to use `io::stdout()`, `println!()` is enough. I wonder why f64?!
<syntaxhighlight lang="rust">
fn perm(n: f64, k: f64) -> f64 {
let mut result: f64 = 1.0;
let mut i: f64 = 0.0;
while i < k {
result *= n - i;
i += 1.0;
}
result
}
fn comb(n: f64, k: f64) -> f64 {
perm(n, k) / perm(k, k)
}
fn main() {
const P: f64 = 12.0;
const C: f64 = 60.0;
let mut j: f64 = 1.0;
let mut k: f64 = 10.0;
while j < P {
println!("P({},{}) = {}", P, j, perm(P, j).floor());
j += 1.0;
}
while k < C {
println!("C({},{}) = {}", C, k, comb(C, k).floor());
k += 10.0;
}
}
</syntaxhighlight>
{{out}}
<pre>
P(12,1) = 12
P(12,2) = 132
P(12,3) = 1320
P(12,4) = 11880
P(12,5) = 95040
P(12,6) = 665280
P(12,7) = 3991680
P(12,8) = 19958400
P(12,9) = 79833600
P(12,10) = 239500800
P(12,11) = 479001600
C(60,10) = 75394027566
C(60,20) = 4191844505805495
C(60,30) = 118264581564861420
C(60,40) = 4191844505805495
C(60,50) = 75394027566
</pre>
=={{header|Scheme}}==
Line 3,064 ⟶ 3,471:
{{libheader|Wren-fmt}}
{{libheader|Wren-iterate}}
<syntaxhighlight lang="
import "./fmt" for Fmt
import "./iterate" for Stepped
var perm = Fn.new { |n, k|
Line 3,207 ⟶ 3,614:
C(60,50) = 75394027566
</pre>
| |||