算法题(如何计算排列系数(代码实现))

本文概述

  • C
  • Java
  • Python3
  • C#
  • 的PHP
  • C ++
  • C
  • Java
  • Python3
  • C#
  • 的PHP
  • C
  • Java
  • Python3
  • C#
  • 的PHP
排列是指将给定集合中的所有成员排列成一个序列的过程。一个n个元素的集合上的排列数由n!给出,"!"表示的阶乘。
用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 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 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)。如果发现任何不正确的地方, 或者想分享有关上述主题的更多信息, 请发表评论。

    推荐阅读