Permutation Coefficient

Question

What is Permutation Coefficient

Permutation refers to the process of arranging all the members of a given set to form a sequence. The number of permutations on a set of n elements is given by n! , where “!” represents factorial. The Permutation Coefficient represented by P(n, k) is used to represent the number of ways to obtain an ordered subset having k elements from a set of n elements.

Mathematically,

Examples:

P(10, 2) = 90
P(10, 3) = 720
P(10, 0) = 1
P(10, 1) = 10

To Calculate the Permutation Coefficient, you can use the following recursive approach:

P(n, k) = P(n-1, k) + k * P(n-1, k-1)

Though, this approach can be slow at times. So Dynamic approach is preferred mostly.

Example of Dynamic Approach (Python)

Input Format

{n} {k}

Output Format

{PermutationCoefficient}

Test Cases

INPUT - 100 2
OUTPUT - 9900

INPUT - 69 5
OUTPUT - 1348621560

INPUT - 20 19
OUTPUT - 2432902008176640000

INPUT - 15 11
OUTPUT - 54486432000

Constraints in input

N will always be greater than or equal to K.

(Not to be confused with Binomial Coefficient)

Answer 1

APL (Dyalog Extended), 5 bytes

⊣÷⍥!-

⊣      left argument
 ÷⍥!   divide over factorial, apply factorial to both arguments and then divide
    -  subtract

Try it online!

Answer 2

Python 3.8 (pre-release), 51 23 21 bytes

import math
math.perm

Try it online!

---

No builtins:

Python 3.8 (pre-release), 31 bytes

f=lambda n,k:k<1or n*f(n-1,k-1)

Try it online!

Answer 3

JavaScript ES6, 25 bytes

c=(n,k)=>k?n*c(n-1,k-1):1

Answer 4

C (gcc), ^{34 32} 27 bytes

Saved 2 bytes thanks to Davide who credits Irratix's JavaScript answer!!!

f(n,k){n=k?n*f(n-1,k-1):1;}

Try it online!

Answer 5

Husk, 4 bytes

Π↑↔ḣ

Try it online!

Π     # product of
 ↑    # the first k elements (k is 2nd argment) of
  ↔   # the reverse of
   ḣ  # 1...n (n is 1st argument)

Answer 6

Whispers v2, 34 bytes

> Input
> Input
>> 1P2
>> Output 3

Try it online!

Builtins for the win

Answer 7

x86 Machine Language, 14 bytes

86 31 C0 40 29 F7 4E 78 05 47 F7 E7 EB F8 C3   

Try it online!

The above bytes of code define a function that calculates and returns the Permutation Coefficient, according to the formula given in the challenge. The function accepts two arguments, n and k, in the EDI and ESI registers, respectively.^* The result is returned in the EAX register, as is conventional.

^{* Note that the selection of these two registers is quite flexible. EDI and ESI were chosen to match some standard C calling conventions, but since this is machine code, they can be changed to any other registers of your choice, except for EAX (which is used for the return value) and EDX (which is clobbered by the MUL instruction).}

Ungolfed assembly mnemonics:

               PermutationCoefficient:
31 C0             xor    eax, eax               # \ assume
40                inc    eax                    # /  result = 1
29 F7             sub    edi, esi               # n -= k
               Top:                             # <======================\
4E                dec    esi                    # --k                    |
78 05             js     End                    # terminate if k < 0     |
47                inc    edi                    # ++n                    |
F7 E7             mul    edi                    # result *= n            |
EB F8             jmp    Top                    # =======================/
               End:
C3                ret

There's nothing especially fancy here. Just machine code at its finest, performing iterative arithmetic with a minimal number of bytes required to encode the instructions. The key innovation is basically just effective use of registers to track the appropriate changes in values of n and k across iterations, which allows the use of extremely small INCrement and DECrement instructions (which can be encoded in only 1 byte). This reduces the number of 2-byte and 3-byte arithmetic operations that must be done inside of the loop, which in turn reduces overall code size. It is probably also a pretty efficient implementation, as far as iterative loops go.

Answer 8

Jelly, 3 bytes

ḶạP

A dyadic Link accepting, the non-negative integers, n on the right and k on the left which yields P(n,k).

Try it online!

How?

ḶạP - Link: k, n          e.g. 3, 10
Ḷ   - lowered range (k)        [0, 1, 2]
 ạ  - absolute difference (n)  [10,9, 8]
  P - product                  720

Answer 9

R, 26 25 bytes

Edit: -1 byte by using scan() to take input

prod(diff(x<-scan())+1:x)

Try it online!

Input in reverse order ( k first, then n).

Answer 10

05AB1E, 1 byte

e

Builtins ftw ¯\_(ツ)_/¯

First input is \$k\$, second input is \$n\$.
e is a builtin for the number of permutations, so \$P(n,k) = \frac{n!}{(n-k)!}\$.

Try it online or verify all test cases.

Answer 11

MathGolf, 5 bytes

‼!-!/

Input in the order \$k\text{ }n\$.

Try it online.

Explanation:

‼      # Apply the following two commands on the stack separately:
 !     #  Take the factorial of the second (implicit) input-integer
  -    #  Subtract the second from the first (implicit) input-integers
   !   # Take the factorial of (n-k) as well
    /  # Integer-divide n! by (n-k)!
       # (after which the entire stack is output implicitly as result)

Answer 12

PowerShell, 28 bytes

param($a,$b)'$a--*'*$b+1|iex

Try it online!

PowerShell 7, 43 bytes

$f={param($a,$b)$b ?$a*(&$f($a-1)($b-1)):1}

no TIO link because TIO still runs on PS 6, which does not support the ternary operator.

Answer 13

Pyth, 4

.P.*

Try it online!

Explanation

    Q      Implicit input of 2-tuple
  .*       splat
.P         nPr
           Explicit output

Answer 14

R, 36 35 bytes

Several attempts hitting the same number:

function(n,r)choose(n,r)*gamma(r)*r

or

function(n,r)gamma(r)/beta(n-r+1,r)

or yet

 function(n,r)"if"(r,n*f(n-1,r-1),1)

with

 function(n,r)dpois(n-r,1)/dpois(n,1)
  

doing even worse (by 1).

Try it online!

Answer 15

Julia, 20 bytes

nothing fancy here, just applying the basic definition

P(n,k)=prod(n-k+1:n)

Try it online!

Answer 16

Retina, 37 bytes

\d+
*
~[".+¶$.("|""L$v`(_*)_ \1
$.'$*

Try it online! Link includes test cases. Takes input in the order k n. Explanation:

\d+
*

Convert the inputs to unary.

L$v`(_*)_ \1
$.'$*

List the numbers from n-k+1 to n, with a * suffixed to each.

|""

Don't separate the results with the default newline.

[".+¶$.("

Prefix the results with the given string.

~

Evaluate that as a Retina 1 expression.

Example: For the input 2 100, there are two matches, where $.' takes the values 99 and 100. The result of the L command is therefore

.+
$.(99*100*

When executed as a Retina program, this then replaces the input with the desired result.

Answer 17

Jelly, 4 bytes

_Ɱ‘P

Try it online!

 Ɱ      For each x in 1 .. k,
_       subtract it from n
  ‘     and increment.
   P    Take the product.

Alternatively,

Jelly, 4 bytes

c×!}

Try it online!

c       nCk
 ×      times
  !}    k!

Bonus solution, 5 bytes, all ASCII: ,_!:/

Answer 18

Charcoal, 7 bytes

ＩΠ⁻Ｎ…⁰Ｎ

Try it online! Link is to verbose version of code. Explanation:

      Ｎ Input `k`
    …⁰  Range from `0` to `k-1`
   Ｎ    Input `n`
  ⁻     Subtract i.e. range from `n-k+1` to `n` (inclusive)
 Π      Product
Ｉ       Cast to string
        Implicitly print

Answer 19

Wolfram Language (Mathematica), 11 bytes

#!/(#-#2)!&

Try it online!

Answer 20

Japt, 6 bytes

o áV l

Try it here

Answer 21

Factor, 27 bytes

USE: math.combinatorics
nPk

Try it online!

There's a built-in for this ... except that the import is horribly long. Even more embarrassing is that I couldn't find a non-built-in solution that beats it:

Factor, 28 bytes

[ [1,b] swap tail* product ]

Try it online!

Takes two numbers k n from the stack, extracts the last k numbers from the inclusive range 1..n, and computes the product. The product of an empty sequence is 1.

Answer 22

Perl 5 -MList::Util=reduce, 36 bytes

sub f{reduce{$a*$b}$_[0]+1-pop..pop}

Try it online!

Answer 23

MATL, 7 bytes

Xn0G:p*

Because snog :p*

Xn        % compute nchoosek
  0G:p    % compute k!
      *   % multiply

Try it online!

Answer 24

Java (JDK), 45 bytes

(n,k)->{var r=1;for(;k-->0;)r*=n--;return r;}

Try it online!

Works only for results <= Integer.MAX_VALUE.

If f(_,0) wasn't a requirement, it could go down one byte:

(n,k)->{for(var x=n;k-->1;)n*=x--;return n;}