本文概述
- C
- Java
- Python3
- C#
- 的PHP
- C ++
- C
- Java
- Python3
- C#
- 的PHP
- C
- Java
- Python3
- C#
- 的PHP
用P(n, k)表示的排列系数用来表示从一个n个元素的集合中得到一个有k个元素的有序子集的方法的个数。
从数学上讲, 它为：
文章图片
图片来源：维基
例子 ：
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在这里我们可以看到时间复杂度为O(n * k), 空间复杂度为O(n * k), 因为程序使用辅助矩阵存储结果。
我们可以在O(n)时间内完成吗？
让我们假设我们维护一个1D数组来计算最多n个阶乘。我们可以使用计算的阶乘值并应用公式P(n, k)= n！ /(n-k)!。以下是说明相同概念的程序。
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 shubhamsingh10C
// 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 GhoshC#
// 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 90O(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 Coefficientdef PermutationCoeff(n, k):
Fn = 1# Compute n! and (n-k)!
for i in range ( 1 , n + 1 ):
Fn * = i
if (i = = n - k):
Fk = Fncoeff = 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 Coefficientfunction 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感谢Shiva Kumar提出此解决方案。
【算法题（如何计算排列系数（代码实现））】本文作者：阿舒托什·库马尔(Ashutosh Kumar)。如果发现任何不正确的地方, 或者想分享有关上述主题的更多信息, 请发表评论。
推荐阅读
- Materialize CSS如何实现页面排版布局（）
- 亚马逊面试题详细分享|S18
- 亚马逊面试题分享|S19
- 亚马逊面试题分享|S20
- 亚马逊面试经验分享|S21
- 亚马逊面试题分享|套装22
- Windows8设备管理器显示umdf hid minidriver未知设备怎样办？
- Win8系统更改SkyDrive默认保存位置的技巧
- Win8应用商店安装软件失败提示0x80240437怎样办？