user
|  |
| --- |
| This page uses content from **Wikipedia**. The original article was at Combination. The list of authors can be seen in the page history. As with Rosetta Code, the text of Wikipedia is available under the GNU FDL. (See links for details on variance) |

|  |
| --- |
| This page uses content from **Wikipedia**. The original article was at Permutation. The list of authors can be seen in the page history. As with Rosetta Code, the text of Wikipedia is available under the GNU FDL. (See links for details on variance) |

Task

Implement the combination    (nCk)    and permutation    (nPk)    operators in the target language:

:   :   :   * n

              C

              k
              =

              (

              n
              k

              )
              =

              n
              (
              n
              −
              1
              )
              …
              (
              n
              −
              k
              +
              1
              )

              k
              (
              k
              −
              1
              )
              …
              1
              {\displaystyle {\displaystyle ^{n}\operatorname {C} \_{k}={\binom {n}{k}}={\frac {n(n-1)\ldots (n-k+1)}{k(k-1)\dots 1}}}}

:   :   :   * n

              P

              k
              =
              n
              ⋅
              (
              n
              −
              1
              )
              ⋅
              (
              n
              −
              2
              )
              ⋯
              (
              n
              −
              k
              +
              1
              )
              {\displaystyle {\displaystyle ^{n}\operatorname {P} \_{k}=n\cdot (n-1)\cdot (n-2)\cdots (n-k+1)}}

See the Wikipedia articles for a more detailed description.

**To test**, generate and print examples of:

* A sample of permutations from 1 to 12 and Combinations from 10 to 60 using exact Integer arithmetic.
* A sample of permutations from 5 to 15000 and Combinations from 100 to 1000 using approximate Floating point arithmetic.  
   This 'floating point' code could be implemented using an approximation, e.g., by calling the Gamma function.

Related task

* Evaluate binomial coefficients

:   :   :   :   The number of samples of size k from n objects.
                  
                  
                With   combinations and permutations   generation tasks.

                |  | Order Unimportant | Order Important |
                | --- | --- | --- |
                | Without replacement | (  n k  )  =  n  C  k =    n ( n − 1 ) … ( n − k + 1 )  k ( k − 1 ) … 1 {\displaystyle {\displaystyle {\binom {n}{k}}=^{n}\operatorname {C} \_{k}={\frac {n(n-1)\ldots (n-k+1)}{k(k-1)\dots 1}}}} | n  P  k = n ⋅ ( n − 1 ) ⋅ ( n − 2 ) ⋯ ( n − k + 1 ) {\displaystyle {\displaystyle ^{n}\operatorname {P} \_{k}=n\cdot (n-1)\cdot (n-2)\cdots (n-k+1)}} |
                | Task: Combinations | Task: Permutations |
                | With replacement | (   n + k − 1 k  )  =  n + k − 1  C  k =    ( n + k − 1 ) !  ( n − 1 ) ! k ! {\displaystyle {\displaystyle {\binom {n+k-1}{k}}=^{n+k-1}\operatorname {C} \_{k}={(n+k-1)! \over (n-1)!k!}}} | n  k {\displaystyle {\displaystyle n^{k}}} |
                | Task: Combinations with repetitions | Task: Permutations with repetitions |
assistant
(formerly Perl 6)
Raku 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 

ln
⁡
(
n
!
)
{\displaystyle {\displaystyle \ln(n!)}}
:

ln
⁡
n
!
≈


1
2
ln
⁡
(
2
π
n
)
+
n
ln
⁡

(

n
e
+


1

12
e
n
)
{\displaystyle {\displaystyle \ln n!\approx {\frac {1}{2}}\ln(2\pi n)+n\ln \left({\frac {n}{e}}+{\frac {1}{12en}}\right)}}

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

```
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);
}

```

Output:

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