പെർ‌മ്യൂട്ടേഷൻ കോഫിഫിഷ്യൻറ്


വൈഷമ്യ നില മീഡിയം
പതിവായി ചോദിക്കുന്നു ബാങ്ക്ബസാർ സോം
ഡൈനാമിക് പ്രോഗ്രാമിംഗ് മഠം ക്രമമാറ്റം

പ്രശ്നം പ്രസ്താവന

“പെർ‌മ്യൂട്ടേഷൻ കോഫിഫിഷ്യൻറ്” എന്ന ഈ പ്രശ്‌നത്തിൽ‌, നമുക്ക് n & k ന്റെ മൂല്യങ്ങൾ‌ നൽ‌കുമ്പോൾ‌ അത് കണ്ടെത്തേണ്ടതുണ്ട്.

ഉദാഹരണം

n = 5, k = 2
20

വിശദീകരണം: ഈ മൂല്യം എൻപിആർ ക്രമമാറ്റ ഗുണകത്തിന്റെ സമവാക്യം ഉപയോഗിച്ച് കണ്ടെത്തി. nPr = n! / (nr)!

പെർ‌മ്യൂട്ടേഷൻ കോഫിഫിഷ്യൻറ് കണ്ടെത്തുന്നതിനുള്ള സമീപനം

പെർ‌മ്യൂട്ടേഷൻ കോഫിഫിഷ്യന്റിനെക്കുറിച്ച് അറിയാൻ. നാം അറിഞ്ഞിരിക്കണം ക്രമമാറ്റം, ഇത് 1 മുതൽ n വരെയുള്ള സംഖ്യകളുടെ ക്രമരഹിതമായ ക്രമം മാത്രമാണ്. അതിനാൽ, പെർ‌മ്യൂട്ടേഷൻ എന്താണെന്ന് ഇപ്പോൾ നമുക്കറിയാം. എന്നാൽ പെർ‌മ്യൂട്ടേഷൻ കോഫിഫിഷ്യന്റ് എന്താണ്?

ഇത് ഓർഡർ ചെയ്യാനുള്ള വഴികളുടെ എണ്ണം മാത്രമാണ് r പുറത്തുള്ള കാര്യങ്ങൾ വ്യത്യസ്ത കാര്യങ്ങൾ. അതിനാൽ, ഇതിന്റെ അർത്ഥം ലളിതമാക്കാൻ? ഇതിനർത്ഥം ഞങ്ങൾക്ക് ചിലത് ഉണ്ടായിരുന്നു എന്നാണ് വ്യത്യസ്ത ഘടകങ്ങൾ, തുടർന്ന് ഞങ്ങൾ ചിലത് തിരഞ്ഞെടുക്കുന്നു അതിൽ നിന്നുള്ള ഘടകങ്ങൾ, ഇപ്പോൾ അവ പുന ar ക്രമീകരിക്കുന്നതിനുള്ള വഴികൾ കണ്ടെത്തേണ്ടതുണ്ട്. nPr എല്ലാ വഴികളും സൂചിപ്പിക്കുന്നു. ഉദാഹരണത്തിന്, 3 വ്യത്യസ്ത ഘടകങ്ങളുടെ ഒരു കൂട്ടത്തിൽ നിന്ന് തിരഞ്ഞെടുത്ത 2 ഘടകങ്ങൾ പുന range ക്രമീകരിക്കുന്നതിനുള്ള വഴികളെ 2P3 സൂചിപ്പിക്കുന്നു.

പെർ‌മ്യൂട്ടേഷൻ കോഫിഫിഷ്യൻറ്

ആദ്യം നമ്മൾ n ഘടകങ്ങളിൽ നിന്ന് r ഘടകങ്ങൾ തിരഞ്ഞെടുക്കുന്നതിനാൽ പെർ‌മ്യൂട്ടേഷൻ കോഫിഫിഷ്യന്റും എളുപ്പത്തിൽ മനസിലാക്കാൻ കഴിയും. അങ്ങനെ nCr തുടർന്ന് ഞങ്ങൾ r ഘടകങ്ങൾ പുന range ക്രമീകരിക്കുന്നു 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

സങ്കീർണ്ണത വിശകലനം

സമയ സങ്കീർണ്ണത

O (N ^ 2 + Q), കാരണം ഞങ്ങളുടെ പെർ‌മ്യൂട്ടേഷൻ കോഫിഫിഷ്യൻറ് കണ്ടെത്തുന്നതിന് ആദ്യം ആവശ്യമായ ഉത്തരം കണക്കാക്കുന്നതിന് ആവശ്യമായ എല്ലാ പെർ‌മ്യൂട്ടേഷൻ കോഫിഫിഷ്യന്റുകളും മുൻ‌കൂട്ടി കണക്കുകൂട്ടേണ്ടതുണ്ട്. അങ്ങനെ സമയ സങ്കീർണ്ണത പോളിനോമിയലാണ്. ഇവിടെ എല്ലാ ചോദ്യങ്ങൾക്കും O (1) ൽ ഉത്തരം നൽകാം.

ബഹിരാകാശ സങ്കീർണ്ണത

O (N ^ 2), മുൻ‌കൂട്ടി തയ്യാറാക്കിയ ഫലം സംഭരിക്കുന്നതിന് ഞങ്ങൾ ഒരു 2 ഡി അറേ ഉപയോഗിച്ചു.

പെർ‌മ്യൂട്ടേഷൻ കോഫിഫിഷ്യന്റിനായുള്ള ഒപ്റ്റിമൈസ്ഡ് സമീപനം

ക്രമമാറ്റം ഗുണകം n മുതൽ n-k + 1 വരെയുള്ള സംഖ്യകളുടെ ഗുണനമല്ലാതെ മറ്റൊന്നുമല്ല. നമുക്ക് nPk in കണക്കാക്കാം O (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
ഒപ്റ്റിമൈസ് ചെയ്ത സമീപനത്തിനുള്ള ജാവ കോഡ്
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