פּערמיוטיישאַן קאָואַפישאַנט


שוועריקייט לעוועל מיטל
אָפט געבעטן אין באַנקבאַזאַר Xome
דינאַמיש פּראָגראַממינג מאַט פּערמיוטיישאַן

פּראָבלעם סטאַטעמענט

אין דעם פּראָבלעם "פּערמיוטיישאַן קאָואַפישאַנט", מיר דאַרפֿן צו געפֿינען עס ווען מיר באַקומען די וואַלועס פון N & K.

בייַשפּיל

n = 5, k = 2
20

דערקלערונג: דעם ווערט פון N P r איז געפֿונען מיט די פאָרמולע פון ​​די פּערמיוטיישאַן קאָואַפישאַנט. nPr = n! / (nr)!

צוגאַנג צו געפֿינען פּערמיוטיישאַן קאָואַפישאַנט

צו באַקומען וויסן וועגן פּערמיוטיישאַן קאָואַפישאַנט. מיר מוזן זיין אַווער פון פּערמיוטיישאַן, עס איז גאָרנישט אָבער קיין טראַפ - סיקוואַנס פון נומערן פון 1 צו n. איצט מיר וויסן וואָס איז פּערמוטאַטיאָן. אָבער וואָס איז פּערמיוטיישאַן קאָואַפישאַנט?

עס איז גאָרנישט אָבער נומער פון וועגן צו סדר r טינגז אויס פון פאַרשידענע זאכן. אַזוי, צו פאַרפּאָשעטערן וואָס דאָס מיטל? דעם מיטל אַז מיר האָבן עטלעכע אַנדערש עלעמענטן און דעמאָלט מיר קלייַבן עטלעכע עלעמענטן פון עס און איצט מיר דאַרפֿן צו געפֿינען די וועגן צו ריעריינינג זיי. נפּר דינאָוץ אַלע וועגן פון טאן. פֿאַר בייַשפּיל, 3P2 דינייץ וועגן צו ריעריינדזש 2 עלעמענטן אויסדערוויילט פון אַ גאַנג פון 3 פאַרשידענע עלעמענטן.

פּערמיוטיישאַן קאָואַפישאַנט

פּערמוטאַטיאָן קאָואַפישאַנט קענען אויך זיין לייכט פארשטאנען ווי ערשטער מיר קלייַבן r יסודות פֿון n עלעמענטן. אַזוי אַז איז nCr דערנאָך מיר ריעריינדזש ר עלעמענטן, אַזוי נפּר = נקר * ר! .

רעקורסיווע פאָרמולע פֿאַר דער דור פון פּערמיוטיישאַן קאָואַפישאַנט

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

מיר קענען געפֿינען די פארלאנגט ענטפֿערס מיט דינאַמיש פּראָגראַממינג פֿאַר די רעקורסיווע פאָרמולע צו רעכענען עס יפישאַנטלי.

קאָדעקס

C ++ קאָד צו באַקומען פּערמיוטיישאַן קאָואַפישאַנט

#include<bits/stdc++.h>
using namespace std;

int P[51][51];

//precomputePermutationCoefficient
void precomputePermutationCoefficients()
{

  for (int i = 0; i <= 50; i++)
  {
    for (int j = 0; j <= i; j++)
    {
      // Base Cases
      if (j == 0)
        P[i][j] = 1;
      else
        P[i][j] = P[i - 1][j] + j * P[i - 1][j - 1]; // use recursive formula
    }
  }
}

int main()
{
  // precomputations being done for n = 50, you can change the value of n
  precomputePermutationCoefficients();
  int noOfQueries;cin>>noOfQueries;
  while(noOfQueries--){
    // here n & k do not satisfy the properties of permutation coefficient
    // then we will answer it as 0
    int n,k;cin>>n>>k;
    if(n<=50 && k<=50)
      cout<<P[n][k]<<endl;
    else
      cout<<0<<endl;
  }
}
1
5 2
20

דזשאַוואַ קאָד צו באַקומען פּערמיוטיישאַן קאָואַפישאַנט

import java.util.*;

class Main{
  static int P[][];

  // precompute permutation coefficient
  static void precomputePermutationCoefficients() 
  {

    for (int i = 0; i <= 50; i++) 
    { 
      for (int j = 0; j <= i; j++) 
      { 
        // Base Cases 
        if (j == 0) 
          P[i][j] = 1; 
        else
          P[i][j] = P[i - 1][j] + j * P[i - 1][j - 1]; // use recursive formula
      } 
    }	
  } 

  public static void main(String[] args)
  {
    P = new int[51][51];
    // precomputations being done for n = 50, you can change the value of n
    precomputePermutationCoefficients();
    Scanner sc = new Scanner(System.in);
    int noOfQueries;
    noOfQueries = sc.nextInt();
    while(noOfQueries-- > 0){
      // here n & k do not satisfy the properties of permutation coefficient
      // then we will answer it as 0
      int n = sc.nextInt();
      int k = sc.nextInt();
      if(n<=50 && k<=50)
        System.out.println(P[n][k]);		
      else
        System.out.println(0);
    }
  }
}
1
5 2
20

קאַמפּלעקסיטי אַנאַליסיס

צייט קאַמפּלעקסיטי

אָ (N ^ 2 + Q), ווייַל צו געפֿינען אונדזער פּערמיוטיישאַן קאָואַפישאַנט, מיר מוזן ערשטער צונויפרעכענען אַלע פּערמיוטיישאַן קאָואַפישאַנץ וואָס זענען נייטיק פֿאַר די כעזשבן פון די פארלאנגט ענטפער. אזוי די צייט קאַמפּלעקסיטי איז פּאַלינאָומיאַל. דאָ קען מען ענטפֿערן אַלע פֿראגן אין אָ (1).

ספעיס קאַמפּלעקסיטי

אָ (N ^ 2), ווייַל מיר האָבן געוויינט אַ 2 ד מענגע צו קראָם די פּרעקאָמפּוטעד רעזולטאַט.

אָפּטימיזעד צוגאַנג פֿאַר פּערמיוטיישאַן קאָואַפישאַנט

זינט פּערמיוטיישאַן קאָואַפישאַנט איז גאָרנישט אָבער קייפל פון נומערן פֿון n צו n-k + 1. מיר קענען פשוט רעכענען NPK אין אָ (1) פּלאַץ און באצייטנס.

קאָדעקס

C ++ קאָד פֿאַר אָפּטימיזעד צוגאַנג
#include<bits/stdc++.h>
using namespace std;

int main(){
  int n,k;cin>>n>>k;
  int P = 1;
  for(int i=n;i>=(n-k+1);i--)
    P*=i;
  cout<<P<<endl;
}
5 2
20
דזשאַוואַ קאָד פֿאַר אָפּטימיזעד צוגאַנג
import java.util.*;

class Main{
  
  public static void main(String[] args)
  {
    Scanner sc = new Scanner(System.in);
    int n = sc.nextInt();
    int k = sc.nextInt();
    int P = 1;
    for(int i=n;i>=(n-k+1);i--)
      P*=i;
    System.out.println(P);
  }
}
5 2
20