Коефицијент пермутације


Ниво тешкоће Средњи
Често питани у БанкБазаар Ксоме
Динамичко програмирање Математика Пермутација

Изјава о проблему

У овом проблему „Коефицијент пермутације“ треба да га пронађемо када нам се дају вредности н & к.

Пример

n = 5, k = 2
20

Објашњење: Ова вредност од нпр налази се помоћу формуле коефицијента пермутације. нПр = н! / (нр)!

Приступ за проналажење коефицијента пермутације

Да бисте упознали коефицијент пермутације. Морамо бити свесни Пермутација, то није ништа друго до било који случајни низ бројева од 1 до н. Дакле, сада знамо шта је Пермутација. Али шта је коефицијент пермутације?

То је ништа друго до више начина за наручивање r ствари ван различите ствари. Па, да поједноставим шта ово значи? То значи да смо их имали различите елементе и онда бирамо неке елементи из њега и сада треба да пронађемо начине да их преуређујемо. нПр означава све начине извођења. На пример, 3П2 означава начине за преуређивање 2 елемента изабраних из скупа од 3 различита елемента.

Коефицијент пермутације

Коефицијент пермутације такође се лако може разумети јер прво одаберемо р елемената од н елемената. Тако је нЦр онда преуређујемо р елементе, дакле нПр = нЦр * р! .

Рекурзивна формула за генерисање пермутационог коефицијента

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), јер смо користили 2Д низ за чување унапред израчунатог резултата.

Оптимизирани приступ за коефицијент пермутације

Пошто коефицијент пермутације није ништа друго до множење бројева од н до н-к + 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
Јава код за оптимизован приступ
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