Коефіцієнт перестановки


Рівень складності Medium
Часто запитують у BankBazaar Xome
Динамічне програмування Математика Перестановка

Постановка проблеми

У цій задачі “Коефіцієнт перестановки” нам потрібно знайти її, коли нам дають значення n & k.

Приклад

n = 5, k = 2
20

Пояснення: Це значення n P r знайдено за формулою коефіцієнта перестановки. nPr = n! / (nr)!

Підхід до пошуку коефіцієнта перестановки

Щоб дізнатись про коефіцієнт перестановки. Ми повинні бути в курсі Перестановка, це не що інше, як будь-яка випадкова послідовність чисел від 1 до n. Отже, тепер ми знаємо, що таке перестановка. Але що таке коефіцієнт перестановки?

Це не що інше, як безліч способів замовлення r речі поза різні речі. Отже, спростити, що це означає? Це означає, що у нас їх було різні елементи, а потім ми вибираємо деякі елементи з нього, і тепер нам потрібно знайти шляхи їх перестановки. nPr позначає всі способи здійснення. Наприклад, 3P2 позначає способи перестановки 2 елементів, вибраних із набору з 3 різних елементів.

Коефіцієнт перестановки

Коефіцієнт перестановки також можна легко зрозуміти, оскільки спочатку ми вибираємо r елементів з n елементів. Отже, це так nCr тоді ми переставляємо 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

Код Java для отримання коефіцієнта перестановки

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), оскільки ми використовували 2D-масив для зберігання попередньо обчисленого результату.

Оптимізований підхід до коефіцієнта перестановки

Оскільки коефіцієнт перестановки - це не що інше, як множення чисел від n до n-k + 1. Ми можемо просто розрахувати nPk в O (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
Код 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