Рубрики

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

Перестановка относится к процессу упорядочения всех членов данного набора для формирования последовательности. Количество перестановок на множестве из n элементов определяется как n! где «!» обозначает факториал.
Коэффициент перестановки, представленный P (n, k), используется для представления количества способов получить упорядоченное подмножество, имеющее k элементов из набора из n элементов.

Математически это дано как:

Источник изображения: Wiki

Примеры :

P(10, 2) = 90
P(10, 3) = 720
P(10, 0) = 1
P(10, 1) = 10

Коэффициент также можно вычислить рекурсивно, используя следующую рекурсивную формулу:

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

Если мы внимательно наблюдаем, мы можем проанализировать, что проблема имеет перекрывающуюся подструктуру, поэтому мы можем применить динамическое программирование здесь. Ниже приведена программа, реализующая ту же идею.

С

// Динамическое программирование на основе
// решение, использующее таблицу P [] []
// рассчитать перестановку
// Коэффициент
#include<bits/stdc++.h>

  
// Возвращает значение перестановки
// Коэффициент P (n, k)

int permutationCoeff(int n, int k)

{

    int P[n + 1][k + 1];

  

    // Рассчитать значение перестановки

    // Коэффициент снизу вверх

    for (int i = 0; i <= n; i++)

    {

        for (int j = 0; j <= std::min(i, k); j++)

        {

            // Базовые случаи

            if (j == 0)

                P[i][j] = 1;

  

            // Рассчитать значение, используя

            // ранее сохраненные значения

            else

                P[i][j] = P[i - 1][j] + 

                          (j * P[i - 1][j - 1]);

  

            // Этот шаг важен

            // так как P (i, j) = 0 для j> i

            P[i][j + 1] = 0;

        }

    }

    return P[n][k];

}

  
// Код драйвера

int main()

{

    int n = 10, k = 2;

    printf("Value of P(%d, %d) is %d ",

            n, k, permutationCoeff(n, k));

    return 0;

}

Джава

// Java-код для динамического программирования
// решение, использующее таблицу P [] [] для
// вычисляем коэффициент перестановки

import java.io.*;

import java.math.*;

  

class GFG 

{

      

    // Возвращает значение перестановки

    // Коэффициент P (n, k)

    static int permutationCoeff(int n, 

                                int k)

    {

        int P[][] = new int[n + 2][k + 2];

      

        // Рассчитать значение перестановки

        // Коэффициент снизу вверх

        for (int i = 0; i <= n; i++)

        {

            for (int j = 0

                 j <= Math.min(i, k); 

                 j++)

            {

                // Базовые случаи

                if (j == 0)

                    P[i][j] = 1;

      

                // Вычисляем значение, используя предыдущий

                // сохраненные значения

                else

                    P[i][j] = P[i - 1][j] + 

                               (j * P[i - 1][j - 1]);

      

                // Этот шаг важен

                // так как P (i, j) = 0 для j> i

                P[i][j + 1] = 0;

            }

        }

        return P[n][k];

    }

      

    // Код драйвера

    public static void main(String args[])

    {

        int n = 10, k = 2;

        System.out.println("Value of P( " + n + ","+ k +")"

                           " is " + permutationCoeff(n, k) );

    }

}

  
// Этот код предоставлен Никитой Тивари.

python3

# Динамическое программирование на основе
# решение, которое использует
# таблица P [] [] для расчета
Коэффициент перестановки

  
# Возвращает значение перестановки
Коэффициент P (n, k)

def permutationCoeff(n, k):

  

    P = [[0 for i in range(k + 1)] 

            for j in range(n + 1)]

  

    # Рассчитать значение перестановки

    Коэффициент в

    # снизу вверх

    for i in range(n + 1):

        for j in range(min(i, k) + 1):

  

            # Базовые случаи

            if (j == 0):

                P[i][j] = 1

  

            # Рассчитать стоимость, используя

            # ранее сохраненные значения

            else:

                P[i][j] = P[i - 1][j] + (

                           j * P[i - 1][j - 1])

  

            # Этот шаг важен

            # как P (i, j) = 0 для j> i

            if (j < k):

                P[i][j + 1] = 0

    return P[n][k]

  
Код водителя

n = 10

k = 2

print("Value fo P(", n, ", ", k, ") is ",

       permutationCoeff(n, k), sep = "")

  
# Этот код предоставлен Soumen Ghosh.

C #

// C # код для динамического программирования
// решение, использующее таблицу P [] [] для
// вычисляем коэффициент перестановки

using System;

  

class GFG 

{

      

    // Возвращает значение перестановки

    // Коэффициент P (n, k)

    static int permutationCoeff(int n, 

                                int k)

    {

        int [,]P = new int[n + 2,k + 2];

      

        // Рассчитать значение перестановки

        // Коэффициент снизу вверх

        for (int i = 0; i <= n; i++)

        {

            for (int j = 0; 

                j <= Math.Min(i, k); 

                j++)

            {

                // Базовые случаи

                if (j == 0)

                    P[i,j] = 1;

      

                // Вычисляем значение, используя предыдущий

                // сохраненные значения

                else

                    P[i,j] = P[i - 1,j] + 

                            (j * P[i - 1,j - 1]);

      

                // Этот шаг важен

                // так как P (i, j) = 0 для j> i

                P[i,j + 1] = 0;

            }

        }

        return P[n,k];

    }

      

    // Код драйвера

    public static void Main()

    {

        int n = 10, k = 2;

        Console.WriteLine("Value of P( " + n + 

                        ","+ k +")" + " is "

                        permutationCoeff(n, k) );

    }

}

  
// Этот код предоставлен anuj_67 ..

PHP

<?php
// Динамическое программирование на основе
// решение, использующее таблицу P [] []
// рассчитать перестановку
// Коэффициент

  
// Возвращает значение перестановки
// Коэффициент P (n, k)

function permutationCoeff( $n, $k)

{

    $P = array(array());

  

    // Рассчитать значение перестановки

    // Коэффициент снизу вверх

    for($i = 0; $i <= $n; $i++)

    {

        for($j = 0; $j <= min($i, $k); $j++)

        {

              

            // Базовые случаи

            if ($j == 0)

                $P[$i][$j] = 1;

  

            // Рассчитать значение, используя

            // ранее сохраненные значения

            else

                $P[$i][$j] = $P[$i - 1][$j] + 

                            ($j * $P[$i - 1][$j - 1]);

  

            // Этот шаг важен

            // так как P (i, j) = 0 для j> i

            $P[$i][$j + 1] = 0;

        }

    }

    return $P[$n][$k];

}

  

    // Код драйвера

    $n = 10; $k = 2;

    echo "Value of P(",$n," ,",$k,") is ",

               permutationCoeff($n, $k);

  
// Этот код предоставлен anuj_67.
?>


Выход :

Value of P(10, 2) is 90 

Здесь, как мы можем видеть, временная сложность равна O (n * k), а сложность пространства равна O (n * k), так как программа использует вспомогательную матрицу для хранения результата.

Можем ли мы сделать это в O (N) время?
Давайте предположим, что мы поддерживаем один одномерный массив для вычисления факториалов до n. Мы можем использовать вычисленное факториальное значение и применить формулу P (n, k) = n! / (нк) !. Ниже приведена программа, иллюстрирующая ту же концепцию.

С

// AO (n) решение, которое использует
// таблица фактов [] для расчета
// Коэффициент перестановки
#include<bits/stdc++.h>

  
// Возвращает значение перестановки
// Коэффициент P (n, k)

int permutationCoeff(int n, int k)

{

    int fact[n + 1];

  

    // базовый вариант

    fact[0] = 1;

  

    // Рассчитать значение

    // факториалы до n

    for (int i = 1; i <= n; i++)

        fact[i] = i * fact[i - 1];

  

    // P (n, k) = n! / (н - к)!

    return fact[n] / fact[n - k];

}

  
// Код драйвера

int main()

{

    int n = 10, k = 2;

    printf ("Value of P(%d, %d) is %d ",

             n, k, permutationCoeff(n, k) );

    return 0;

}

Джава

// AO (n) решение, которое использует
// таблица фактов [] для расчета
// Коэффициент перестановки

import java .io.*;

  

public class GFG {

      

    // Возвращает значение перестановки

    // Коэффициент P (n, k)

    static int permutationCoeff(int n, 

                                int k)

    {

        int []fact = new int[n+1];

      

        // базовый вариант

        fact[0] = 1;

      

        // Рассчитать значение

        // факториалы до n

        for (int i = 1; i <= n; i++)

            fact[i] = i * fact[i - 1];

      

        // P (n, k) = n! / (н - к)!

        return fact[n] / fact[n - k];

    }

      

    // Код драйвера

    static public void main (String[] args)

    {

        int n = 10, k = 2;

        System.out.println("Value of"

        + " P( " + n + ", " + k + ") is "

        + permutationCoeff(n, k) );

    }

}

  
// Этот код предоставлен anuj_67.

python3

# AO (n) решение, которое использует
# таблица фактов [] для расчета
# Коэффициент перестановки

  
# Возвращает значение перестановки
Коэффициент P (n, k)

def permutationCoeff(n, k):

    fact = [0 for i in range(n + 1)]

  

    # базовый вариант

    fact[0] = 1

  

    # Рассчитать стоимость

    # факториалы до n

    for i in range(1, n + 1):

        fact[i] = i * fact[i - 1]

  

    # P (n, k) = n! / (Nk)!

    return int(fact[n] / fact[n - k])

  
Код водителя

n = 10

k = 2

print("Value of P(", n, ", ", k, ") is ",

        permutationCoeff(n, k), sep = "")

  
# Этот код добавлен
# Сумен Гош

C #

// AO (n) решение, которое использует
// таблица фактов [] для расчета
// Коэффициент перестановки

using System;

  

public class GFG {

      

    // Возвращает значение перестановки

    // Коэффициент P (n, k)

    static int permutationCoeff(int n, 

                                int k)

    {

        int []fact = new int[n+1];

      

        // базовый вариант

        fact[0] = 1;

      

        // Рассчитать значение

        // факториалы до n

        for (int i = 1; i <= n; i++)

            fact[i] = i * fact[i - 1];

      

        // P (n, k) = n! / (н - к)!

        return fact[n] / fact[n - k];

    }

      

    // Код драйвера

    static public void Main ()

    {

        int n = 10, k = 2;

        Console.WriteLine("Value of"

        + " P( " + n + ", " + k + ") is "

         + permutationCoeff(n, k) );

    }

}

  
// Этот код предоставлен anuj_67.

PHP

<?php
// AO (n) Решение, которое
// использует таблицу фактов [] для
// вычисляем перестановку
// Коэффициент

  
// Возвращает значение перестановки
// Коэффициент P (n, k)

function permutationCoeff($n, $k)

{

    $fact = array();

  

    // базовый вариант

    $fact[0] = 1;

  

    // Рассчитать значение

    // факториалы до n

    for ($i = 1; $i <= $n; $i++)

        $fact[$i] = $i * $fact[$i - 1];

  

    // P (n, k) = n! / (Nk)!

    return $fact[$n] / $fact[$n - $k];

}

  

    // Код драйвера

    $n = 10;

    $k = 2;

    echo"Value of P(",$n," ", $k,") is ",

            permutationCoeff($n, $k) ;

              
// Этот код предоставлен anuj_67.
?>


Выход :

Value of P(10, 2) is 90 

AO (n) время и O (1) дополнительное пространство решение

С

// AO (n) время и O (1) дополнительно
// космическое решение для расчета
// Коэффициент перестановки
#include <iostream>

using namespace std;

  

int PermutationCoeff(int n, int k)

{

    int P = 1;

  

    // Вычисляем n * (n-1) * (n-2) .... (n-k + 1)

    for (int i = 0; i < k; i++)

        P *= (n-i) ;

  

    return P;

}

  
// Код драйвера

int main()

{

    int n = 10, k = 2;

    cout << "Value of P(" << n << ", " << k

         << ") is " << PermutationCoeff(n, k);

  

    return 0;

}

Джава

// AO (n) время и O (1) дополнительно
// космическое решение для расчета
// Коэффициент перестановки

import java.io.*;

  

class GFG 

{

    static int PermutationCoeff(int n, 

                                int k)

    {

        int Fn = 1, Fk = 1;

      

        // Вычисляем n! и (нк)!

        for (int i = 1; i <= n; i++)

        {

            Fn *= i;

            if (i == n - k)

            Fk = Fn;

        }

        int coeff = Fn / Fk;

        return coeff;

    }

      

    // Код драйвера

    public static void main(String args[])

    {

        int n = 10, k = 2;

        System.out.println("Value of P( " + n + ","

                                         k +") is "

                            PermutationCoeff(n, k) );

    }

}

      
// Этот код предоставлен Никитой Тивари.

python3

# AO (n) время и O (1) дополнительно
# космическое решение для расчета
# Коэффициент перестановки

  

def PermutationCoeff(n, k):

    Fn = 1

  

    # Вычисли n! и (нк)!

    for i in range(1, n + 1):

        Fn *= i

        if (i == n - k):

            Fk = Fn

  

    coeff = Fn // Fk

    return coeff

  
Код водителя

n = 10

k = 2

print("Value of P(", n, ", ", k, ") is ",

       PermutationCoeff(n, k), sep = "")

  
# Этот код добавлен
# Сумен Гош.

C #

// AO (n) время и O (1) дополнительно
// космическое решение для расчета
// Коэффициент перестановки

using System;

  

class GFG {

      

    static int PermutationCoeff(int n, 

                                int k)

    {

        int Fn = 1, Fk = 1;

      

        // Вычисляем n! и (нк)!

        for (int i = 1; i <= n; i++)

        {

            Fn *= i;

            if (i == n - k)

                Fk = Fn;

        }

        int coeff = Fn / Fk;

          

        return coeff;

    }

      

    // Код драйвера

    public static void Main()

    {

        int n = 10, k = 2;

        Console.WriteLine("Value of P( "

                   + n + "," + k +") is "

              + PermutationCoeff(n, k) );

    }

}

      
// Этот код предоставлен anuj_67.

PHP

<?php
// AO (n) время и O (1) дополнительно
// космическое PHP решение для расчета
// Коэффициент перестановки

  

function PermutationCoeff( $n, $k)

{

    $Fn = 1; $Fk;

  

    // Вычисляем n! и (нк)!

    for ( $i = 1; $i <= $n; $i++)

    {

        $Fn *= $i;

        if ($i == $n - $k)

        $Fk = $Fn;

    }

    $coeff = $Fn / $Fk;

    return $coeff;

}

  
// Код драйвера

$n = 10; $k = 2;

echo "Value of P(" , $n , ", " , $k , ")

        is " , PermutationCoeff($n, $k);

  
// Этот код предоставлен anuj_67.
?>


Выход :

Value of P(10, 2) is 90 

Спасибо Шива Кумар за предложение этого решения.

Эта статья предоставлена Ашутошем Кумаром . Пожалуйста, напишите комментарии, если вы обнаружите что-то неправильное, или вы хотите поделиться дополнительной информацией по обсуждаемой теме

Рекомендуемые посты:

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

0.00 (0%) 0 votes