क्रमचय गुणांक


कठिनाई स्तर मध्यम
में अक्सर पूछा BankBazaar ज़ोम
गतिशील प्रोग्रामिंग मठ परिवर्तन

समस्या का विवरण

इस समस्या में "क्रमपरिवर्तन गुणांक", हमें इसे खोजने की आवश्यकता है जब हमें n & k के मान दिए जाते हैं।

उदाहरण

n = 5, k = 2
20

स्पष्टीकरण: यह मान एनपीआर क्रमचय गुणांक के सूत्र का उपयोग करके पाया जाता है। nPr = n! / (nr)!

क्रमपरिवर्तन गुणांक खोजने के लिए दृष्टिकोण

क्रमपरिवर्तन गुणांक के बारे में जानने के लिए। हमें जागरूक होना चाहिए परिवर्तन, यह 1 से n तक की संख्याओं के किसी भी यादृच्छिक अनुक्रम के अलावा और कुछ नहीं है। तो, अब हम जानते हैं कि क्रमपरिवर्तन क्या है। लेकिन क्रमपरिवर्तन गुणांक क्या है?

यह आदेशों की संख्या के अलावा और कुछ नहीं है r की बातें अलग अलग बातें। तो, यह सरल करने के लिए इसका क्या मतलब है? इसका मतलब है कि हमारे पास कुछ था विभिन्न तत्व और फिर हम कुछ का चयन करते हैं उसमें से तत्वों और अब हमें उन्हें पुनर्व्यवस्थित करने के तरीके खोजने की आवश्यकता है। nPr करने के सभी तरीकों को दर्शाता है। उदाहरण के लिए, 3P2 2 अलग-अलग तत्वों के सेट से चुने गए 3 तत्वों को पुनर्व्यवस्थित करने के तरीकों को दर्शाता है।

क्रमचय गुणांक

क्रमचय गुणांक को भी आसानी से समझा जा सकता है क्योंकि पहले हम n तत्वों में से r तत्वों को चुनते हैं। तो वह है एनसीआर फिर हम आर तत्वों को पुनर्व्यवस्थित करते हैं, इसलिए nPr = nCr * r! ।

क्रमचय गुणांक की पीढ़ी के लिए पुनरावर्ती सूत्र

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

जटिलता विश्लेषण

समय जटिलता

O (N ^ 2 + Q), क्योंकि हमारे क्रमपरिवर्तन गुणांक को खोजने के लिए हमें पहले उन सभी क्रमोन्नति गुणांकों को रोकना होगा जो आवश्यक उत्तर की गणना के लिए आवश्यक हैं। इस प्रकार समय जटिलता बहुपद है। यहाँ सभी प्रश्नों का उत्तर O (1) में दिया जा सकता है।

अंतरिक्ष जटिलता

ओ (एन ^ 2), क्योंकि हमने प्रीकम्प्यूटेड परिणाम को संग्रहीत करने के लिए एक 2D सरणी का उपयोग किया है।

अनुमापन गुणांक के लिए अनुकूलित दृष्टिकोण

चूंकि क्रमपरिवर्तन गुणांक n से n-k + 1 तक संख्याओं के गुणन के अलावा और कुछ नहीं है। हम बस में nPk की गणना कर सकते हैं 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