પરમ્યુટેશન ગુણાંક


મુશ્કેલી સ્તર મધ્યમ
વારંવાર પૂછવામાં આવે છે બેંકબજાર Xome
ડાયનેમિક પ્રોગ્રામિંગ મઠ અનુમાન

સમસ્યા નિવેદન

આ સમસ્યા "પરમિટ્યુશન ગુણાંક" માં, જ્યારે અમને એન & કેની કિંમતો આપવામાં આવે છે ત્યારે આપણે તેને શોધવાની જરૂર છે.

ઉદાહરણ

n = 5, k = 2
20

સમજૂતી: આ મૂલ્ય એન.પી. આર ક્રમચય ગુણાંકના સૂત્રનો ઉપયોગ કરીને જોવા મળે છે. એનપીઆર = એન! / (એનઆરઆઈ)!

પરમ્યુટેશન ગુણાંક શોધવા માટેનો અભિગમ

પરમ્યુટેશન ગુણાંક વિશે જાણવા માટે. આપણે પરિચિત હોવા જોઈએ અનુમાન, તે 1 થી n સુધીના કોઈપણ રેન્ડમ ક્રમ સિવાય કંઈ નથી. તેથી, હવે આપણે જાણીએ છીએ કે પરમ્યુટેશન શું છે. પરંતુ ક્રમચય ગુણાંક શું છે?

તે waysર્ડર કરવાની રીતોની સંખ્યા સિવાય કંઈ નથી r વસ્તુઓ બહાર વિવિધ વસ્તુઓ. તેથી, આનો અર્થ શું છે તે સરળ બનાવવું? આનો અર્થ એ કે અમારી પાસે કેટલાક હતા વિવિધ તત્વો અને પછી અમે કેટલાક પસંદ કરીએ છીએ તેના તત્વો અને હવે આપણે તેમને ફરીથી ગોઠવવાની રીતો શોધવાની જરૂર છે. nPr કરવાના તમામ માર્ગો સૂચવે છે. ઉદાહરણ તરીકે, 3 પી 2, 2 જુદા જુદા તત્વોના સમૂહમાંથી પસંદ કરેલા 3 તત્વોને ફરીથી ગોઠવવાની રીતો સૂચવે છે.

પરમ્યુટેશન ગુણાંક

પરમ્યુટેશન ગુણાંક પણ સરળતાથી સમજી શકાય છે, કારણ કે આપણે n તત્વોમાંથી આર ઘટકોને પસંદ કરીએ છીએ. તેથી તે છે એનસીઆર પછી અમે r તત્વોને ફરીથી ગોઠવીએ છીએ, તેથી nPr = nCr * r! .

પરમ્યુટેશન ગુણાંકની ઉત્પત્તિ માટે પુનરાવર્તિત સૂત્ર

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

ઉપયોગ કરીને જરૂરી જવાબ મેળવી શકીએ છીએ ડાયનેમિક પ્રોગ્રામિંગ પુનરાવર્તિત સૂત્ર માટે તેની અસરકારક રીતે ગણતરી કરી શકાય.

કોડ

પરમ્યુટેશન ગુણાંક મેળવવા માટે સી ++ કોડ

#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

જટિલતા વિશ્લેષણ

સમય જટિલતા

ઓ (એન ^ 2 + ક્યૂ), કારણ કે અમારું ક્રમચય ગુણાંક શોધવા માટે પહેલા આપણે બધા ક્રમ્યુટેશન ગુણાંકોને પ્રિકમ્પ્યુટ કરવાની જરૂર છે જે જરૂરી જવાબોની ગણતરી માટે જરૂરી છે. આમ સમય જટિલતા બહુપદી છે. અહીં બધી પ્રશ્નોના જવાબ ઓ (1) માં આપી શકાય છે.

અવકાશ જટિલતા

ઓ (એન ^ 2), કારણ કે અમે પૂર્વનિર્ધારિત પરિણામ સંગ્રહિત કરવા માટે 2D એરેનો ઉપયોગ કર્યો છે.

પરમ્યુટેશન ગુણાંક માટે Approપ્ટિમાઇઝ અભિગમ

ક્રમચય ગુણાંક એ n થી n-k + 1 ની સંખ્યાના ગુણાકાર સિવાય કંઈ નથી. આપણે ફક્ત એનપીકે ઇનની ગણતરી કરી શકીએ છીએ ઓ (1) જગ્યા અને સમયસર.

કોડ

+પ્ટિમાઇઝ અભિગમ માટે સી ++ કોડ
#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
Javaપ્ટિમાઇઝ અભિગમ માટે જાવા કોડ
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