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)

Our site support LaTeX if wrapped with \$. Like this: \$P(n, k)=\underbrace{n \cdot (n -1) \cdot (n-2) \cdot \ldots \cdot (n-k+1)}_{k\text{ factors}}\$ — DELETE_ME, Feb 4, 2021 at 14:23
By the way, it's recommended that you post challenges in the "sandbox for proposed challenges" first for at least 72 hours before posting it on main. — DELETE_ME, Feb 4, 2021 at 14:27
@rak1507 Well, the only difference is that the other challenge has a cumbersome input format. Maybe we can close the older challenge as a dupe of this one, but having both doesn't seem right. — Arnauld, Feb 4, 2021 at 23:04
@Arnauld and that the old challenge bans builtins. I would prefer closing the older one over this one personally — rak1507, Feb 4, 2021 at 23:11

rak1507 · Accepted Answer · 2021-02-04 13:00:07Z

10

APL (Dyalog Extended), 5 bytes

⊣÷⍥!-

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

Try it online!

answered Feb 4, 2021 at 13:00

rak1507

4,68010 silver badges16 bronze badges

Add a comment |

TFeld · Accepted Answer · 2021-02-05 08:14:48Z

6

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!

edited Feb 5, 2021 at 8:14

answered Feb 4, 2021 at 12:43

TFeld

19.8k3 gold badges19 silver badges63 bronze badges

3

\$\begingroup\$ If you're doing this, why not from math import*? \$\endgroup\$
– Digital Trauma
Feb 4, 2021 at 16:01
3

\$\begingroup\$ This sort of thing where a builtin in an import solves a problem has always been a bit of a grey area for a function submission. I don't know what the solution should be, but I disagree that from math import* should be acceptable in the same way an empty program would be unacceptable if the solution was the bin builtin function - just having the program in the namespace should not be enough. \$\endgroup\$
– Sisyphus
Feb 4, 2021 at 23:58
1

\$\begingroup\$ I think the right way is to submit the reusable name of the function (separate from the import line), just like how an anonymous lambda is submitted. So from math import perm is not valid, but from math import*\nperm or import math\nmath.perm is valid (the latter being 21 bytes). \$\endgroup\$
– Bubbler
Feb 5, 2021 at 7:17

Add a comment |

Noodle9 · Accepted Answer · 2021-02-04 15:06:30Z

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!

edited Feb 4, 2021 at 15:06

answered Feb 4, 2021 at 14:35

Noodle9

19.9k3 gold badges20 silver badges45 bronze badges

\$\begingroup\$ I can't find anything to golf. If you want you can add this recursive one giving credit to Irratix \$\endgroup\$
– anotherOne
Feb 4, 2021 at 15:01
1

\$\begingroup\$ @Davide Nice one - thanks! :D \$\endgroup\$
– Noodle9
Feb 4, 2021 at 15:06

Add a comment |

Dominic van Essen · Accepted Answer · 2021-02-05 06:57:30Z

4

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)

answered Feb 5, 2021 at 6:57

Dominic van Essen

34.6k2 gold badges18 silver badges54 bronze badges

Add a comment |

Jonathan Allan · Accepted Answer · 2021-02-06 13:45:02Z

4

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

answered Feb 6, 2021 at 13:45

Jonathan Allan

103k7 gold badges62 silver badges270 bronze badges

Add a comment |

Irratix · Accepted Answer · 2021-02-04 12:58:42Z

3

JavaScript ES6, 25 bytes

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

answered Feb 4, 2021 at 12:58

Irratix

313 bronze badges

3

\$\begingroup\$ You can save a byte by using currying syntax: 24 bytes \$\endgroup\$
– Arnauld
Feb 4, 2021 at 13:46
2

\$\begingroup\$ And you can save 2 more bytes by taking the arguments the other way around: 22 bytes \$\endgroup\$
– Arnauld
Feb 4, 2021 at 14:52

Add a comment |

Kevin Cruijssen · Accepted Answer · 2021-02-04 13:20:33Z

3

05AB1E, 1 byte

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.

edited Feb 4, 2021 at 13:20

answered Feb 4, 2021 at 13:10

Kevin Cruijssen

123k11 gold badges135 silver badges374 bronze badges

\$\begingroup\$ I was 5 hours late... \$\endgroup\$
– Makonede
Feb 4, 2021 at 19:08

Add a comment |

caird coinheringaahin g · Accepted Answer · 2021-02-04 20:25:13Z

3

Whispers v2, 34 bytes

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

Try it online!

Builtins for the win

answered Feb 4, 2021 at 20:25

caird coinheringaahin g♦

49.4k11 gold badges120 silver badges347 bronze badges

Add a comment |

Dominic van Essen · Accepted Answer · 2021-02-06 15:40:57Z

3

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).

edited Feb 6, 2021 at 15:40

answered Feb 5, 2021 at 15:58

Dominic van Essen

34.6k2 gold badges18 silver badges54 bronze badges

\$\begingroup\$ I concede defeat!!! \$\endgroup\$
– Xi'an ні війні
Feb 5, 2021 at 17:11
1

\$\begingroup\$ @Xi'an - Ha! Too soon! I just managed to sneak-away another byte! \$\endgroup\$
– Dominic van Essen
Feb 6, 2021 at 15:45

Add a comment |

Kevin Cruijssen · Accepted Answer · 2021-02-04 13:57:08Z

2

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)

edited Feb 4, 2021 at 13:57

answered Feb 4, 2021 at 13:32

Kevin Cruijssen

123k11 gold badges135 silver badges374 bronze badges

\$\begingroup\$ +1 to MathGolf for calling the first command !! in this context \$\endgroup\$
– Greg Martin
Feb 7, 2021 at 2:31

Add a comment |

Zaelin Goodman · Accepted Answer · 2021-02-04 14:33:42Z

2

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.

edited Feb 4, 2021 at 14:33

answered Feb 4, 2021 at 14:22

Zaelin Goodman

2,0793 silver badges11 bronze badges

Add a comment |

Digital Trauma · Accepted Answer · 2021-02-04 16:28:16Z

2

Pyth, 4

.P.*

Try it online!

Explanation

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

answered Feb 4, 2021 at 16:28

Digital Trauma

71.8k9 gold badges109 silver badges261 bronze badges

2

\$\begingroup\$ .PF works too. technically this would be a fold operation (so for input [1,2,3,4] it'd return P(P(P(1,2),3),4)), but if the input is a 2 element sequence, it acts identical to the splatting operator. \$\endgroup\$
– randomdude999
Feb 4, 2021 at 19:33

Add a comment |

Cody Gray - on strike · Accepted Answer · 2021-02-06 05:29:01Z

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.

Xi'an ні війні · Accepted Answer · 2021-02-06 15:16:00Z

2

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!

edited Feb 6, 2021 at 15:16

answered Feb 5, 2021 at 15:15

Xi'an ні війні

8287 silver badges21 bronze badges

2

\$\begingroup\$ The R battle is on! \$\endgroup\$
– Dominic van Essen
Feb 5, 2021 at 15:59
\$\begingroup\$ @DominicvanEssen: too bad there is no perm(n,r) R command available. I tried with various densities but they all seem to require more characters. \$\endgroup\$
– Xi'an ні війні
Feb 6, 2021 at 9:03
\$\begingroup\$ There is permutations(n,r) in gtools, but unfortunately it's long name (as well as the need to count the permutations, rather than just return them) makes it the least golfy of all... \$\endgroup\$
– Dominic van Essen
Feb 6, 2021 at 14:24

Add a comment |

Neil · Accepted Answer · 2021-02-04 13:56:20Z

1

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

answered Feb 4, 2021 at 13:56

Neil

165k12 gold badges69 silver badges273 bronze badges

Add a comment |

MarcMush · Accepted Answer · 2021-02-04 16:30:11Z

1

Julia, 20 bytes

nothing fancy here, just applying the basic definition

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

Try it online!

edited Feb 4, 2021 at 16:30

answered Feb 4, 2021 at 13:32

MarcMush

6,26511 silver badges16 bronze badges

Add a comment |

Neil · Accepted Answer · 2021-02-04 19:00:17Z

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.

att · Accepted Answer · 2021-02-04 19:37:04Z

1

Wolfram Language (Mathematica), 11 bytes

#!/(#-#2)!&

Try it online!

answered Feb 4, 2021 at 19:37

att

19.7k2 gold badges14 silver badges56 bronze badges

Add a comment |

Unrelated String · Accepted Answer · 2021-02-05 00:31:35Z

1

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: ,_!:/

edited Feb 5, 2021 at 0:31

answered Feb 4, 2021 at 14:29

Unrelated String

21.2k3 gold badges28 silver badges54 bronze badges

Add a comment |

beaker · Accepted Answer · 2021-02-06 19:39:10Z

1

MATL, 7 bytes

Xn0G:p*

Because snog :p*

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

Try it online!

answered Feb 6, 2021 at 19:39

beaker

2,6391 gold badge9 silver badges18 bronze badges

Add a comment |

Bubbler · Accepted Answer · 2021-02-09 00:28:41Z

1

Factor, ²⁸ 21 bytes

[ [0,b) n-v product ]

Try it online!

Inspired by Jonathan Allan's Jelly answer. Now beats the built-in solution!

Takes two numbers n k from the stack, subtracts 0..k-1 from n, and computes the product. The product of an empty sequence is 1.

Factor, 27 bytes

USE: math.combinatorics
nPk

Try it online!

There's a built-in for this ... except that the import is horribly long.

edited Feb 9, 2021 at 0:28

answered Feb 5, 2021 at 7:47

Bubbler

73.8k5 gold badges142 silver badges443 bronze badges

Add a comment |

Aaroneous Miller · Accepted Answer · 2021-04-20 23:45:36Z

1

+100

Vyxal, 2 bytes

∆ƈ

Try it Online!

Another built-in, like 05AB1E, but not quite as concise. First input is k, second input is n.

answered Apr 20, 2021 at 23:45

Aaroneous Miller

9,1101 gold badge20 silver badges37 bronze badges

Add a comment |

Axuary · Accepted Answer · 2021-04-20 23:52:25Z

1

Excel, 14 bytes

=PERMUT(A1,A2)

An Excel built-in.

answered Apr 20, 2021 at 23:52

Axuary

3,4065 silver badges11 bronze badges

Add a comment |

Shaggy · Accepted Answer · 2021-02-04 23:05:31Z

0

Japt, 6 bytes

o áV l

Try it here

answered Feb 4, 2021 at 23:05

Shaggy

41.6k4 gold badges34 silver badges92 bronze badges

Add a comment |

Kjetil S · Accepted Answer · 2021-02-05 17:45:48Z

0

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

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

Try it online!

answered Feb 5, 2021 at 17:45

Kjetil S

5,4879 silver badges17 bronze badges

Add a comment |

Olivier Grégoire · Accepted Answer · 2021-02-06 22:07:01Z

0

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

edited Feb 6, 2021 at 22:07

answered Feb 6, 2021 at 22:00

Olivier Grégoire

14.3k3 gold badges30 silver badges56 bronze badges

Add a comment |

alephalpha · Accepted Answer · 2021-02-09 00:18:18Z

0

Pari/GP, 16 bytes

p(n,k)=n!/(n-k)!

Try it online!

answered Feb 9, 2021 at 0:18

alephalpha

46.5k7 gold badges60 silver badges172 bronze badges

Add a comment |

Wasif · Accepted Answer · 2021-04-20 07:58:55Z

0

Python 2, 54 bytes

lambda n,k:g(n)/g(n-k)
from math import factorial as g

Try it online!

There's a better python solution already.....

answered Apr 20, 2021 at 7:58

Wasif

12.3k1 gold badge16 silver badges46 bronze badges

Add a comment |

What is Permutation Coefficient

Examples:

Input Format

Output Format

Test Cases

Constraints in input

(Not to be confused with Binomial Coefficient)

28 Answers 28

APL (Dyalog Extended), 5 bytes

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

Python 3.8 (pre-release), 31 bytes

C (gcc), 34 32 27 bytes

Husk, 4 bytes

Jelly, 3 bytes

How?

JavaScript ES6, 25 bytes

05AB1E, 1 byte

Whispers v2, 34 bytes

R, 26 25 bytes

MathGolf, 5 bytes

PowerShell, 28 bytes

PowerShell 7, 43 bytes

Pyth, 4

Explanation

x86 Machine Language, 14 bytes

R, 36 35 bytes

Charcoal, 7 bytes

Julia, 20 bytes

Retina, 37 bytes

Wolfram Language (Mathematica), 11 bytes

Jelly, 4 bytes

Jelly, 4 bytes

MATL, 7 bytes

Factor, 28 21 bytes

Factor, 27 bytes

Vyxal, 2 bytes

Excel, 14 bytes

Japt, 6 bytes

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

Java (JDK), 45 bytes

Pari/GP, 16 bytes

Python 2, 54 bytes

Your Answer

Sign up or log in

Post as a guest

Linked

Related

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

Factor, ²⁸ 21 bytes