Combinations and permutations: Difference between revisions

{{trans|C++}}

 

BigInt r = 1

V k = n - p

print(‘P(12,’i‘) = ’perm(12, i))

L(i) (10.<60).step(10)

 

{{out}}

{{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:

=={{header|Bracmat}}==

Bracmat cannot handle floating point numbers. Instead, this solution shows the first 50 digits and a count of the digits that are not shown.

= n k coef

. !arg:(?n,?k)

& out$(str$(!i " C " !k " = " displayBig$(C$(!i,!k))))

)

Output:

<pre>1 P 0 = 1

=={{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|C++}}==

{{libheader|Boost}}

Compiled with <code>g++-10 -Wall -std=c++03</code>, linked with <code>-lgmp</code>

#include <iostream>

 

 

return 0;

{{out}}

<pre>P(12,1) = 12

=={{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

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

 

=={{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|FreeBASIC}}==

{{trans|Visual Basic .NET}}

Dim As Long i

Dim As Longint z = 1

Print ""

Next i

 

 

=={{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;

 

}

 

{{out}}

=={{header|jq}}==

Currently, jq approximates large integers by IEEE 754 64-bit floats, and only supports tgamma (true gamma). Thus beyond about 1e308 all accuracy is lost.

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

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

 

'''Examples''':

12 | permutation(9) #=> 79833600

 

'''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}}

 

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

Module PermComb {

Form 80, 50

}

PermComb

{{out}}

-- Permutations - from 1 to 12

 

=={{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);

As with the Raku code, some special handling was done for those values which would have overflowed the native floating point type.

 

use warnings;

 

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

}

{{out}}

<pre style="height:50ex">A sample of Permutations from 1 to 12

Translation of Raku/Sidef, same results<br>

Update: there are now builtin routines k_perm(n,k) and choose(n,k), slightly more efficient equivalents of P() and C() respectively.

<span style="color: #008080;">with</span> <span style="color: #008080;">javascript_semantics</span>

<span style="color: #008080;">function</span> <span style="color: #000000;">P</span><span style="color: #0000FF;">(</span><span style="color: #004080;">integer</span> <span style="color: #000000;">n</span><span style="color: #0000FF;">,</span><span style="color: #000000;">k</span><span style="color: #0000FF;">)</span>

<span style="color: #7060A8;">printf</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"C(%d,%d) = %s\n"</span><span style="color: #0000FF;">,{</span><span style="color: #000000;">n</span><span style="color: #0000FF;">,</span><span style="color: #000000;">p</span><span style="color: #0000FF;">,</span><span style="color: #000000;">to_s</span><span style="color: #0000FF;">(</span><span style="color: #000000;">C_approx</span><span style="color: #0000FF;">(</span><span style="color: #000000;">n</span><span style="color: #0000FF;">,</span><span style="color: #000000;">p</span><span style="color: #0000FF;">))})</span>

<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>

{{out}}

<pre>

=={{header|Python}}==

==={{libheader|SciPy}}===

 

from scipy.misc import factorial as fact

k = N-2

print('%iC%i =' % (N, k), comb(N, k, exact))

 

{{out}}

=={{header|R}}==

R has most of this built in. The documentation for choose warns that it only calculates its result directly if k is small. Skimming [https://github.com/wch/r-source/blob/trunk/src/nmath/choose.c what appears to be the source code] suggests that 29 is the highest "small" k. This means that we can solve both tasks with little more than R's choose.

print(perm(seq(from = 3, to = 12, by = 3), seq(from = 2, to = 8, by = 2)))

print(choose(seq(from = 10, to = 60, by = 10), seq(from = 3, to = 18, by = 3)))

print(perm(seq(from = 1500, to = 15000, by = 1500), seq(from = 55, to = 100, by = 5)))

{{out}}

<pre>> print(perm(seq(from = 3, to = 12, by = 3), seq(from = 2, to = 8, by = 2)))

there is no need for a floating point estimate:

 

#lang racket

(require math)

(C 1000 10) ; -> 263409560461970212832400

(P 1000 10) ; -> 955860613004397508326213120000

 

(I'll spare this page from yet another big listing of samples...)

Notice that Raku can process arbitrary long integers, though. So it's not clear whether using floating points is useful in this case.

 

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:

=={{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>

=={{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}}==

{{trans|Raku}}

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">

{{libheader|Wren-fmt}}

{{libheader|Wren-trait}}

import "/fmt" for Fmt

import "/trait" for Stepped

var e = (l <= 40) ? "" : "... (%(l - 40) more digits)"

Fmt.print("$4d C $-3d = $s$s", n, k, s.take(40).join(), e)

 

{{out}}