20
\$\begingroup\$

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,

math

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)

\$\endgroup\$
7
  • 7
    \$\begingroup\$ 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}}\$ \$\endgroup\$
    – DELETE_ME
    Feb 4 at 14:23
  • 3
    \$\begingroup\$ 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. \$\endgroup\$
    – DELETE_ME
    Feb 4 at 14:27
  • 1
    \$\begingroup\$ Does this answer your question? Fun With Permutations \$\endgroup\$ Feb 4 at 19:41
  • 3
    \$\begingroup\$ @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. \$\endgroup\$
    – Arnauld
    Feb 4 at 23:04
  • 3
    \$\begingroup\$ @Arnauld and that the old challenge bans builtins. I would prefer closing the older one over this one personally \$\endgroup\$
    – rak1507
    Feb 4 at 23:11

28 Answers 28

10
\$\begingroup\$

APL (Dyalog Extended), 5 bytes

⊣÷⍥!-

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

Try it online!

\$\endgroup\$
6
\$\begingroup\$

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!

\$\endgroup\$
3
  • 3
    \$\begingroup\$ If you're doing this, why not from math import*? \$\endgroup\$ Feb 4 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 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 at 7:17
4
\$\begingroup\$

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!

\$\endgroup\$
2
  • \$\begingroup\$ I can't find anything to golf. If you want you can add this recursive one giving credit to Irratix \$\endgroup\$ Feb 4 at 15:01
  • 1
    \$\begingroup\$ @Davide Nice one - thanks! :D \$\endgroup\$
    – Noodle9
    Feb 4 at 15:06
4
\$\begingroup\$

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)
\$\endgroup\$
4
\$\begingroup\$

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
\$\endgroup\$
3
\$\begingroup\$

JavaScript ES6, 25 bytes

c=(n,k)=>k?n*c(n-1,k-1):1
\$\endgroup\$
2
  • 3
    \$\begingroup\$ You can save a byte by using currying syntax: 24 bytes \$\endgroup\$
    – Arnauld
    Feb 4 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 at 14:52
3
\$\begingroup\$

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.

\$\endgroup\$
1
  • \$\begingroup\$ I was 5 hours late... \$\endgroup\$
    – Makonede
    Feb 4 at 19:08
3
\$\begingroup\$

Whispers v2, 34 bytes

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

Try it online!

Builtins for the win

\$\endgroup\$
3
\$\begingroup\$

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

\$\endgroup\$
2
  • \$\begingroup\$ I concede defeat!!! \$\endgroup\$
    – Xi'an
    Feb 5 at 17:11
  • 1
    \$\begingroup\$ @Xi'an - Ha! Too soon! I just managed to sneak-away another byte! \$\endgroup\$ Feb 6 at 15:45
2
\$\begingroup\$

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)
\$\endgroup\$
1
  • \$\begingroup\$ +1 to MathGolf for calling the first command !! in this context \$\endgroup\$ Feb 7 at 2:31
2
\$\begingroup\$

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.

\$\endgroup\$
2
\$\begingroup\$

Pyth, 4

.P.*

Try it online!

Explanation

    Q      Implicit input of 2-tuple
  .*       splat
.P         nPr
           Explicit output
\$\endgroup\$
1
  • 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\$ Feb 4 at 19:33
2
\$\begingroup\$

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.

\$\endgroup\$
2
\$\begingroup\$

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!

\$\endgroup\$
3
  • 2
    \$\begingroup\$ The R battle is on! \$\endgroup\$ Feb 5 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 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\$ Feb 6 at 14:24
1
\$\begingroup\$

Charcoal, 7 bytes

IΠ⁻N…⁰N

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

      N Input `k`
    …⁰  Range from `0` to `k-1`
   N    Input `n`
  ⁻     Subtract i.e. range from `n-k+1` to `n` (inclusive)
 Π      Product
I       Cast to string
        Implicitly print
\$\endgroup\$
1
\$\begingroup\$

Julia, 20 bytes

nothing fancy here, just applying the basic definition

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

Try it online!

\$\endgroup\$
1
\$\begingroup\$

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.

\$\endgroup\$
1
\$\begingroup\$

Wolfram Language (Mathematica), 11 bytes

#!/(#-#2)!&

Try it online!

\$\endgroup\$
1
\$\begingroup\$

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

\$\endgroup\$
1
\$\begingroup\$

MATL, 7 bytes

Xn0G:p*

Because snog :p*

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

Try it online!

\$\endgroup\$
1
\$\begingroup\$

Factor, 28 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.

\$\endgroup\$
1
+100
\$\begingroup\$

Vyxal, 2 bytes

∆ƈ

Try it Online!

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

\$\endgroup\$
0
\$\begingroup\$

Japt, 6 bytes

o áV l

Try it here

\$\endgroup\$
0
\$\begingroup\$

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

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

Try it online!

\$\endgroup\$
0
\$\begingroup\$

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;}
\$\endgroup\$
0
\$\begingroup\$

Pari/GP, 16 bytes

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

Try it online!

\$\endgroup\$
0
\$\begingroup\$

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

\$\endgroup\$
0
\$\begingroup\$

Excel, 14 bytes

=PERMUT(A1,A2)

An Excel built-in.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy