Combinations and permutations: Difference between revisions

{{wikipedia|Permutation}}

 

;Task:

{{Template:Combinations and permutations}}

<br><br>

 

=={{header|ALGOL 68}}==

{{works with|ALGOL 68G|Any - tested with release [http://sourceforge.net/projects/algol68/files/algol68g/algol68g-2.6 algol68g-2.6].}}

{{wont work with|ELLA ALGOL 68|Any (with appropriate job cards) - tested with release [http://sourceforge.net/projects/algol68/files/algol68toc/algol68toc-1.8.8d/algol68toc-1.8-8d.fc9.i386.rpm/download 1.8-8d] - due to extensive use of '''format'''[ted] ''transput''.}}

 

COMMENT REQUIRED by "prelude_combinations_and_permutations.a68" CO

END COMMENT

 

# -*- coding: utf-8 -*- #

 

printf(($"("g(0)" C "g(0)") = "g(0,1)$, r, first, r C first, $", "$));

printf(($"("g(0)" C "g(0)") = "g(0,1)$, r, second, r C second, $l$))

<pre>

A sample of Permutations from 1 to 12:

(1000 C 998) = 499500.0, (1000 C 969) = 76023224077705100000000000000000000000000000000000000000000.0

</pre>

 

=={{header|Bracmat}}==

= n k coef

. !arg:(?n,?k)

& !coef

)

& ( P

= n k result

& !result

)

& 0:?i

& whl

' ( 10+!i:~>60:?i

& div$(!i.3):?k

)

& ( displayBig

' ( !is:%?i ?is

& div$(!i.3):?k

)

& 0:?i

' ( 100+!i:~>1000:?i

& div$(!i.3):?k

)

Output:

<pre>1 P 0 = 1

11 P 3 = 990

12 P 4 = 11880

 

=={{header|C}}==

Using big integers. GMP in fact has a factorial function which is quite possibly more efficient, though using it would make code longer.

 

void perm(mpz_t out, int n, int k)

gmp_printf("C(1000,969) = %Zd\n", x);

return 0;

 

=={{header|Common Lisp}}==

 

(cond ((or (< n k) (< k 0) (< n 0)) 0)

((= k 0) 1)

(a m (* a m)))

((= i k) a)))))

 

=={{header|Crystal}}==

{{trans|Ruby}}

include Math

def combination(k)

end

p 15000.permutation(74) #=> 896237613852967826239917238565433149353074416025197784301593335243699358040738127950872384197159884905490054194835376498534786047382445592358843238688903318467070575184552953997615178973027752714539513893159815472948987921587671399790410958903188816684444202526779550201576117111844818124800000000000000000000

 

{{out}}

<pre>

=={{header|D}}==

{{trans|Ruby}}

std.bigint, std.conv;

 

15_000.bigPermutation(1185).writeln;

writefln("%(%s\\\n%)", 15_000.permutation(74).text.chunks(50));

{{out}}

<pre>79833600

84444202526779550201576117111844818124800000000000\

000000000</pre>

 

=={{header|EchoLisp}}==

;; rename native functions according to task

(define-syntax-rule (Cnk n k) (Cnp n k))

→ 1029024198692120734765388598788124551227594950478035495578451793852872815678512303375588360

1398831219998720000000000000

 

=={{header|Elixir}}==

{{trans|Erlang}}

def perm(n, k), do: product(n - k + 1 .. n)

end

 

 

{{out}}

{{trans|Haskell}}

 

-module(combinations_permutations).

 

io_lib:format("~s... (~p more digits)", [Shown, length(Hidden)])

end.

 

Output:

=={{header|Factor}}==

As with Racket, these operations are built in and Factor has unlimited integers.

 

1000 10 nCk . ! 263409560461970212832400

 

=={{header|Go}}==

Go has arbitrary-length maths in the standard math/big library; no need for floating-point approximations at this level.

package main

 

return c

}

Output:

<pre>A sample of permutations from 1 to 12:

=={{header|Haskell}}==

The Haskell Integer type supports arbitrary precision so floating point approximation is not needed.

perm n k = product [n-k+1..n]

 

mapM_ showComb [(n, n `div` 3) | n <- [100,200..1000] ]

 

{{out}}

<pre style="font-size:80%">A sample of permutations from 1 to 12:

The sample here gives a few representative values to shorten the output.

 

write("P(4,2) = ",P(4,2))

write("P(8,2) = ",P(8,2))

every (p:=1) *:= (n-k+1) to n

return p

 

Output:

Implementation:

 

 

! is a primitive, but we will give it a name (<code>C</code>) for this task.

Example use (P is permutations, C is combinations):

 

┌──┬─────────────────────────────────────────────────────────────┐

│P │1 2 3 4 5 6 7 8 9 10 11 12│

2.24185e96

700 C 800

 

=={{header|Java}}==

The second part of this task implies that the computations are performed in floating point arithmetic. However, the maximum value of a double in Java is 1.7976931348623157E308. Hence, larger computations would overflow. As a result, this task was interpreted so that “using” means “displayed”.

import java.math.BigInteger;

 

System.out.println();

System.out.println("A sample of permutations from 5 to 15000 displayed in floating point arithmetic:");

for ( int n = 1000 ; n <= 15000 ; n += 1000 ) {

int k = n / 2;

}

 

{{out}}

 

A sample of permutations from 5 to 15000 displayed in floating point arithmetic:

1000 P 500 = 3.2978863640988537122024252070116261706996485697981 * 10^1433

2000 P 1000 = 8.2415012140674255266380217928953202425839550211348 * 10^3167

 

=={{header|jq}}==

| reduce range($n-k+1; 1+$n) as $i (1; . * $i);

def big_permutation(k): log_permutation(k) | exp;

 

 

 

 

 

 

 

=={{header|Julia}}==

 

'''Functions'''

function Base.binomial{T<:FloatingPoint}(n::T, k::T)

exp(lfact(n) - lfact(n - k) - lfact(k))

⊞{T<:Real}(n::T, k::T) = binomial(n, k)

⊠{T<:Real}(n::T, k::T) = factorial(n, n-k)

 

'''Main'''

function picknk{T<:Integer}(lo::T, hi::T)

n = rand(lo:hi)

println(@sprintf " %7.1f ⊞ %7.1f = %10.6e" n k n ⊞ k)

end

 

{{out}}

=={{header|Kotlin}}==

As Kotlin/JVM can use the java.math.BigInteger class, there is no need to use floating point approximations and so we use exact integer arithmetic for all parts of the task.

 

import java.math.BigInteger

System.out.printf("%4d C %-3d = %s%s\n", n, k, s.take(40), e)

}

 

{{out}}

1000 C 333 = 5776134553147651669777486323549601722339... (235 more digits)

</pre>

=={{header|M2000 Interpreter}}==

Module PermComb {

Form 80, 50

}

PermComb

{{out}}

-- Permutations - from 1 to 12

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

 

=={{header|Maple}}==

comb := proc (n::integer, k::integer)

return factorial(n)/(factorial(k)*factorial(n-k));

return factorial(n)/factorial(n-k);

end proc;

 

=={{header|Mathematica}} / {{header|Wolfram Language}}==

Combination[n_,k_]:=Binomial[n,k]

Permutation[n_,k_]:=Binomial[n,k]k!

TableForm[Array[Combination,{6,6},{{10,60},{10,60}}],TableHeadings->{Range[10,60,10],Range[10,60,10]}]

{Row[{#,"P",#-2}," "],N@Permutation[#,#-2]}&/@{5,1000,5000,10000,15000}//Grid

 

{{out}}

</pre>

Note that Mathematica can easily handle very big numbers with exact integer arithmetic:

Permutation[200000, 100000]

{{out}}

The output is 516777 digits longs:

 

=={{header|МК-61/52}}==

ИП1 ИП2 - ПП 53 П3 ИП1 ПП 53 ИП3 / В/О

1 ИП1 * L2 21 В/О

ИП1 ИП2 - ПП 53 П3 ИП2 ПП 53 ИП3 * П3 ИП1 ПП 53 ИП3 / В/О

ИП1 ИП2 + 1 - П1 ПП 26 В/О

 

''Input'': ''x ^ n ^ k В/О С/П'', where ''x'' = 8 for permutations; 20 for permutations with repetitions; 26 for combinations; 44 for combinations with repetitions.

 

=={{header|Nim}}==

 

proc perm(n, k: int32): BigInt =

 

echo "P(1000, 969) = ", perm(1000, 969)

 

=={{header|PARI/GP}}==

permExact(m,n)=factorback([m-n+1..m]);

combExact=binomial;

sample(combExact, 10, 60);

sample(permApprox, 5, 15000);

{{out}}

<pre>?sample(permExact, 1, 12);

 

=={{header|Perl}}==

native integers and floats are limited to what the computer's native types can handle.

 

 

use warnings;

 

sprintf "%.8Fe%+d", exp($x - $e * log(10)), $e;

}

 

 

 

<math>\ln n! \approx

\frac{1}{2}\ln(2\pi n) + n\ln\left(\frac{n}{e} + \frac{1}{12 e n}\right)</math>

 

 

multi C($n, $k) { P($n, $k) / [*] 1 .. $k }

my $p = $n div 3;

say "C($n, $p) = ", C($n, $p, :float);

{{out}}

<pre>Exact results:

C(900, 300) = 1.74335637E+247

C(1000, 333) = 5.77613455E+274</pre>

 

=={{header|REXX}}==

The hard part of this REXX program was coding the &nbsp; '''DO''' &nbsp; loops for the various ranges.

numeric digits 100 /*use 100 decimal digits of precision. */

 

if x-y <y then y=x - y /*switch things around for speed. */

call .combPerm /*call subroutine to do heavy lifting. */

'''output'''

<pre>

C(900,1)=900 C(900,181)=5.1402207737939392620E+194 C(900,361)=4.6256239559539226532E+261 C(900,541)=2.0577328996911473555E+261 C(900,721)=3.2260054093505652100E+193

C(1000,1)=1000 C(1000,201)=2.6336937554862900107E+216 C(1000,401)=7.4293352412781479131E+290 C(1000,601)=3.3046738011675400053E+290 C(1000,801)=1.6522236106515115238E+215

</pre>

 

=={{header|Ruby}}==

Float calculation as Tcl.

 

class Integer

#Fixnum has no maximum:

p 15000.permutation(74) #=> 896237613852967826239917238565433149353074416025197784301593335243699358040738127950872384197159884905490054194835376498534786047382445592358843238688903318467070575184552953997615178973027752714539513893159815472948987921587671399790410958903188816684444202526779550201576117111844818124800000000000000000000

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)

 

=={{header|Scheme}}==

 

(define (combinations n k)

(do ((i 0 (+ 1 i))

(display "C(1000,1000) = ") (display (combinations 1000 1000)) (newline)

(display "C(15000,14998) = ") (display (combinations 15000 14998)) (newline)

 

{{out}}

 

=={{header|Sidef}}==

func C(n, k) { binomial(n, k) }

 

var p = n//3

say "C(#{n}, #{p}) = #{C_approx(n, p)}"

{{out}}

<pre>

The '''[https://www.stata.com/help.cgi?mf_comb comb]''' function is builtin. Here is an implementation, together with perm:

 

return(exp(lnfactorial(n)-lnfactorial(k)-lnfactorial(n-k)))

}

real scalar perm(n, k) {

return(exp(lnfactorial(n)-lnfactorial(n-k)))

 

=={{header|Swift}}==

Using AttaSwift's BigInt

 

 

func permutations(n: Int, k: Int) -> BigInt {

 

print("\(i) C \(k) = \(res.prefix(40))\(extra)")

 

{{out}}

Tcl doesn't allow the definition of new infix operators, so we define <math>P</math> and <math>C</math> as ordinary functions. There are no problems with loss of significance though: Tcl has supported arbitrary precision integer arithmetic since 8.5.

{{tcllib|math}}

proc tcl::mathfunc::P {n k} {

set t 1

proc tcl::mathfunc::fC {n k} {

expr {exp(lnGamma($n+1) - lnGamma($n-$k+1) - lnGamma($k+1))}

Demonstrating:

puts "A sample of Permutations from 1 to 12:"

for {set i 4} {$i <= 12} {incr i} {

set iii [expr {$i - int(sqrt($i))}]

puts "$i C $ii = [expr {fC($i,$ii)}], $i C $iii = [expr {fC($i,$iii)}]"

{{out}}

<pre>

 

=={{header|VBScript}}==

dim i,j

Wscript.StdOut.WriteLine "-- Long Integer - Permutations - from 1 to 12"

comb=perm(x,y)/fact(y)

end if

{{out}}

<pre style="height:40ex">

=={{header|Visual Basic .NET}}==

{{works with|Visual Basic .NET|2013}}

Imports System.Numerics 'BigInteger

Module CombPermRc

End Function 'CombBig

 

{{out}}

<pre style="height:40ex">

--

C(5000,4000)=57462357505803375604893834658665168251899919793850512934468881710397678593302188064618445132583370701755893065787216750992391223467601994741594656878559929037277303674963658032197224327768110236651567704673226756781828332650887849150208195780031161286578505113618731045004523840401144118298192191997565735245181433457469532981432785237769191864102953974244072964471109551273603780184330987071947790993108191904370472373403157802158903129815170101708451875442019845175637901995588390614304812103202403626211504997668649346891167495657556154392183988627948442807346603688457854135114491955258804187129028256547543888109987151649038111791932035229202856007767332717845596528598314477979861265222941138323298702349967224867703420888363395662988291273283611081068577160905840445308086112429900453394212790633910614322699210850302387512579976209123523546689147207974269396548873838155355768985614160932799226261509866933143702889005270480654844312094564956178277998090168826124850606847021667494019587077659107276117413835912767949017954979839258481340540145909025953956582025656306426226560

</pre>