# 算法题：如何计算排列系数？代码实现

2021年3月23日14:46:57 发表评论 870 次浏览

## 本文概述

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

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

## C

// A Dynamic Programming based
// solution that uses table P[][]
// to calculate the Permutation
// Coefficient
#include<bits/stdc++.h>

// Returns value of Permutation
// Coefficient P(n, k)
int permutationCoeff( int n, int k)
{
int P[n + 1][k + 1];

// Calculate value of Permutation
// Coefficient in bottom up manner
for ( int i = 0; i <= n; i++)
{
for ( int j = 0; j <= std::min(i, k); j++)
{
// Base Cases
if (j == 0)
P[i][j] = 1;

// Calculate value using
// previosly stored values
else
P[i][j] = P[i - 1][j] +
(j * P[i - 1][j - 1]);

// This step is important
// as P(i, j)=0 for j>i
P[i][j + 1] = 0;
}
}
return P[n][k];
}

// Driver Code
int main()
{
int n = 10, k = 2;
printf ( "Value of P(%d, %d) is %d " , n, k, permutationCoeff(n, k));
return 0;
}

## Java

// Java code for Dynamic Programming based
// solution that uses table P[][] to
// calculate the Permutation Coefficient
import java.io.*;
import java.math.*;

class GFG
{

// Returns value of Permutation
// Coefficient P(n, k)
static int permutationCoeff( int n, int k)
{
int P[][] = new int [n + 2 ][k + 2 ];

// Calculate value of Permutation
// Coefficient in bottom up manner
for ( int i = 0 ; i <= n; i++)
{
for ( int j = 0 ;
j <= Math.min(i, k);
j++)
{
// Base Cases
if (j == 0 )
P[i][j] = 1 ;

// Calculate value using previosly
// stored values
else
P[i][j] = P[i - 1 ][j] +
(j * P[i - 1 ][j - 1 ]);

// This step is important
// as P(i, j)=0 for j>i
P[i][j + 1 ] = 0 ;
}
}
return P[n][k];
}

// Driver Code
public static void main(String args[])
{
int n = 10 , k = 2 ;
System.out.println( "Value of P( " + n + ", " + k + ")" +
" is " + permutationCoeff(n, k) );
}
}

// This code is contributed by Nikita Tiwari.

## Python3

# A Dynamic Programming based
# solution that uses
# table P[][] to calculate the
# Permutation Coefficient

# Returns value of Permutation
# Coefficient P(n, k)
def permutationCoeff(n, k):

P = [[ 0 for i in range (k + 1 )]
for j in range (n + 1 )]

# Calculate value of Permutation
# Coefficient in
# bottom up manner
for i in range (n + 1 ):
for j in range ( min (i, k) + 1 ):

# Base cases
if (j = = 0 ):
P[i][j] = 1

# Calculate value using
# previously stored values
else :
P[i][j] = P[i - 1 ][j] + (
j * P[i - 1 ][j - 1 ])

# This step is important
# as P(i, j) = 0 for j>i
if (j < k):
P[i][j + 1 ] = 0
return P[n][k]

# Driver Code
n = 10
k = 2
print ( "Value fo P(" , n, ", " , k, ") is " , permutationCoeff(n, k), sep = "")

# This code is contributed by Soumen Ghosh.

## C#

// C# code for Dynamic Programming based
// solution that uses table P[][] to
// calculate the Permutation Coefficient
using System;

class GFG
{

// Returns value of Permutation
// Coefficient P(n, k)
static int permutationCoeff( int n, int k)
{
int [, ]P = new int [n + 2, k + 2];

// Calculate value of Permutation
// Coefficient in bottom up manner
for ( int i = 0; i <= n; i++)
{
for ( int j = 0;
j <= Math.Min(i, k);
j++)
{
// Base Cases
if (j == 0)
P[i, j] = 1;

// Calculate value using previosly
// stored values
else
P[i, j] = P[i - 1, j] +
(j * P[i - 1, j - 1]);

// This step is important
// as P(i, j)=0 for j>i
P[i, j + 1] = 0;
}
}
return P[n, k];
}

// Driver Code
public static void Main()
{
int n = 10, k = 2;
Console.WriteLine( "Value of P( " + n +
", " + k + ")" + " is " +
permutationCoeff(n, k) );
}
}

// This code is contributed by anuj_67..

## 的PHP

<?php
// A Dynamic Programming based
// solution that uses table P[][]
// to calculate the Permutation
// Coefficient

// Returns value of Permutation
// Coefficient P(n, k)
function permutationCoeff( \$n , \$k )
{
\$P = array ( array ());

// Calculate value of Permutation
// Coefficient in bottom up manner
for ( \$i = 0; \$i <= \$n ; \$i ++)
{
for ( \$j = 0; \$j <= min( \$i , \$k ); \$j ++)
{

// Base Cases
if ( \$j == 0)
\$P [ \$i ][ \$j ] = 1;

// Calculate value using
// previosly stored values
else
\$P [ \$i ][ \$j ] = \$P [ \$i - 1][ \$j ] +
( \$j * \$P [ \$i - 1][ \$j - 1]);

// This step is important
// as P(i, j)=0 for j>i
\$P [ \$i ][ \$j + 1] = 0;
}
}
return \$P [ \$n ][ \$k ];
}

// Driver Code
\$n = 10; \$k = 2;
echo "Value of P(" , \$n , " , " , \$k , ") is " , permutationCoeff( \$n , \$k );

// This code is contributed by anuj_67.
?>

Value of P(10, 2) is 90

## C ++

// A O(n) solution that uses
// table fact[] to calculate
// the Permutation Coefficient
#include<bits/stdc++.h>
using namespace std;

// Returns value of Permutation
// Coefficient P(n, k)
int permutationCoeff( int n, int k)
{
int fact[n + 1];

// Base case
fact[0] = 1;

// Calculate value
// factorials up to n
for ( int i = 1; i <= n; i++)
fact[i] = i * fact[i - 1];

// P(n, k) = n! / (n - k)!
return fact[n] / fact[n - k];
}

// Driver Code
int main()
{
int n = 10, k = 2;

cout << "Value of P(" << n << ", "
<< k << ") is "
<< permutationCoeff(n, k);

return 0;
}

// This code is contributed by shubhamsingh10

## C

// A O(n) solution that uses
// table fact[] to calculate
// the Permutation Coefficient
#include<bits/stdc++.h>

// Returns value of Permutation
// Coefficient P(n, k)
int permutationCoeff( int n, int k)
{
int fact[n + 1];

// base case
fact[0] = 1;

// Calculate value
// factorials up to n
for ( int i = 1; i <= n; i++)
fact[i] = i * fact[i - 1];

// P(n, k) = n! / (n - k)!
return fact[n] / fact[n - k];
}

// Driver Code
int main()
{
int n = 10, k = 2;
printf ( "Value of P(%d, %d) is %d " , n, k, permutationCoeff(n, k) );
return 0;
}

## Java

// A O(n) solution that uses
// table fact[] to calculate
// the Permutation Coefficient
import java .io.*;

public class GFG {

// Returns value of Permutation
// Coefficient P(n, k)
static int permutationCoeff( int n, int k)
{
int []fact = new int [n+ 1 ];

// base case
fact[ 0 ] = 1 ;

// Calculate value
// factorials up to n
for ( int i = 1 ; i <= n; i++)
fact[i] = i * fact[i - 1 ];

// P(n, k) = n! / (n - k)!
return fact[n] / fact[n - k];
}

// Driver Code
static public void main (String[] args)
{
int n = 10 , k = 2 ;
System.out.println( "Value of"
+ " P( " + n + ", " + k + ") is "
+ permutationCoeff(n, k) );
}
}

// This code is contributed by anuj_67.

## Python3

# A O(n) solution that uses
# table fact[] to calculate
# the Permutation Coefficient

# Returns value of Permutation
# Coefficient P(n, k)
def permutationCoeff(n, k):
fact = [ 0 for i in range (n + 1 )]

# base case
fact[ 0 ] = 1

# Calculate value
# factorials up to n
for i in range ( 1 , n + 1 ):
fact[i] = i * fact[i - 1 ]

# P(n, k) = n!/(n-k)!
return int (fact[n] / fact[n - k])

# Driver Code
n = 10
k = 2
print ( "Value of P(" , n, ", " , k, ") is " , permutationCoeff(n, k), sep = "")

# This code is contributed
# by Soumen Ghosh

## C#

// A O(n) solution that uses
// table fact[] to calculate
// the Permutation Coefficient
using System;

public class GFG {

// Returns value of Permutation
// Coefficient P(n, k)
static int permutationCoeff( int n, int k)
{
int []fact = new int [n+1];

// base case
fact[0] = 1;

// Calculate value
// factorials up to n
for ( int i = 1; i <= n; i++)
fact[i] = i * fact[i - 1];

// P(n, k) = n! / (n - k)!
return fact[n] / fact[n - k];
}

// Driver Code
static public void Main ()
{
int n = 10, k = 2;
Console.WriteLine( "Value of"
+ " P( " + n + ", " + k + ") is "
+ permutationCoeff(n, k) );
}
}

// This code is contributed by anuj_67.

## 的PHP

<?php
// A O(n) Solution that
// uses table fact[] to
// calculate the Permutation
// Coefficient

// Returns value of Permutation
// Coefficient P(n, k)
function permutationCoeff( \$n , \$k )
{
\$fact = array ();

// base case
\$fact [0] = 1;

// Calculate value
// factorials up to n
for ( \$i = 1; \$i <= \$n ; \$i ++)
\$fact [ \$i ] = \$i * \$fact [ \$i - 1];

// P(n, k)= n!/(n-k)!
return \$fact [ \$n ] / \$fact [ \$n - \$k ];
}

// Driver Code
\$n = 10;
\$k = 2;
echo "Value of P(" , \$n , " " , \$k , ") is " , permutationCoeff( \$n , \$k ) ;

// This code is contributed by anuj_67.
?>

Value of P(10, 2) is 90

O(n)时间和O(1)额外空间解决方案

## C

// A O(n) time and O(1) extra
// space solution to calculate
// the Permutation Coefficient
#include <iostream>
using namespace std;

int PermutationCoeff( int n, int k)
{
int P = 1;

// Compute n*(n-1)*(n-2)....(n-k+1)
for ( int i = 0; i < k; i++)
P *= (n-i) ;

return P;
}

// Driver Code
int main()
{
int n = 10, k = 2;
cout << "Value of P(" << n << ", " << k
<< ") is " << PermutationCoeff(n, k);

return 0;
}

## Java

// A O(n) time and O(1) extra
// space solution to calculate
// the Permutation Coefficient
import java.io.*;

class GFG
{
static int PermutationCoeff( int n, int k)
{
int Fn = 1 , Fk = 1 ;

// Compute n! and (n-k)!
for ( int i = 1 ; i <= n; i++)
{
Fn *= i;
if (i == n - k)
Fk = Fn;
}
int coeff = Fn / Fk;
return coeff;
}

// Driver Code
public static void main(String args[])
{
int n = 10 , k = 2 ;
System.out.println( "Value of P( " + n + ", " +
k + ") is " +
PermutationCoeff(n, k) );
}
}

// This code is contributed by Nikita Tiwari.

## Python3

# A O(n) time and O(1) extra
# space solution to calculate
# the Permutation Coefficient

def PermutationCoeff(n, k):
Fn = 1

# Compute n! and (n-k)!
for i in range ( 1 , n + 1 ):
Fn * = i
if (i = = n - k):
Fk = Fn

coeff = Fn / / Fk
return coeff

# Driver Code
n = 10
k = 2
print ( "Value of P(" , n, ", " , k, ") is " , PermutationCoeff(n, k), sep = "")

# This code is contributed
# by Soumen Ghosh.

## C#

// A O(n) time and O(1) extra
// space solution to calculate
// the Permutation Coefficient
using System;

class GFG {

static int PermutationCoeff( int n, int k)
{
int Fn = 1, Fk = 1;

// Compute n! and (n-k)!
for ( int i = 1; i <= n; i++)
{
Fn *= i;
if (i == n - k)
Fk = Fn;
}
int coeff = Fn / Fk;

return coeff;
}

// Driver Code
public static void Main()
{
int n = 10, k = 2;
Console.WriteLine( "Value of P( "
+ n + ", " + k + ") is "
+ PermutationCoeff(n, k) );
}
}

// This code is contributed by anuj_67.

## 的PHP

<?php
// A O(n) time and O(1) extra
// space PHP solution to calculate
// the Permutation Coefficient

function PermutationCoeff( \$n , \$k )
{
\$Fn = 1; \$Fk ;

// Compute n! and (n-k)!
for ( \$i = 1; \$i <= \$n ; \$i ++)
{
\$Fn *= \$i ;
if ( \$i == \$n - \$k )
\$Fk = \$Fn ;
}
\$coeff = \$Fn / \$Fk ;
return \$coeff ;
}

// Driver Code
\$n = 10; \$k = 2;
echo "Value of P(" , \$n , ", " , \$k , ")
is " , PermutationCoeff( \$n , \$k );

// This code is contributed by anuj_67.
?>

Value of P(10, 2) is 90