La permutación se refiere al proceso de ordenar todos los miembros de un conjunto dado para formar una secuencia. ¡El número de permutaciones en un conjunto de n elementos viene dado por n! , dónde «!» representa factorial.
El coeficiente de permutación representado por P(n, k) se usa para representar el número de formas de obtener un subconjunto ordenado que tiene k elementos de un conjunto de n elementos.
Matemáticamente se da como:
Fuente de la imagen: Wiki
Ejemplos:
P(10, 2) = 90 P(10, 3) = 720 P(10, 0) = 1 P(10, 1) = 10
El coeficiente también se puede calcular recursivamente usando la siguiente fórmula recursiva:
P(n, k) = P(n-1, k) + k* P(n-1, k-1)
Si observamos de cerca, podemos analizar que el problema tiene una subestructura superpuesta, por lo tanto, podemos aplicar aquí la programación dinámica. A continuación se muestra un programa que implementa la misma idea.
C++
// C++ program of the above approach
#include <bits/stdc++.h>
using namespace std;
// A Dynamic Programming based
// solution that uses table P[][]
// to calculate the Permutation
// Coefficient
#include<bits/stdc++.h>
// Returns value of Permutation
// Coefficient P(n, k)
int permutationCoeff(int n, int k)
{
int P[n + 1][k + 1];
// Calculate value of Permutation
// Coefficient in bottom up manner
for (int i = 0; i <= n; i++)
{
for (int j = 0; j <= std::min(i, k); j++)
{
// Base Cases
if (j == 0)
P[i][j] = 1;
// Calculate value using
// previously stored values
else
P[i][j] = P[i - 1][j] +
(j * P[i - 1][j - 1]);
// This step is important
// as P(i,j)=0 for j>i
P[i][j + 1] = 0;
}
}
return P[n][k];
}
// Driver Code
int main()
{
int n = 10, k = 2;
cout << "Value of P(" << n <<" " << k<< ") is " << permutationCoeff(n, k);
return 0;
}
// This code is contributed by code_hunt.
C
// A Dynamic Programming based
// solution that uses table P[][]
// to calculate the Permutation
// Coefficient
#include<bits/stdc++.h>
// Returns value of Permutation
// Coefficient P(n, k)
int permutationCoeff(int n, int k)
{
int P[n + 1][k + 1];
// Calculate value of Permutation
// Coefficient in bottom up manner
for (int i = 0; i <= n; i++)
{
for (int j = 0; j <= std::min(i, k); j++)
{
// Base Cases
if (j == 0)
P[i][j] = 1;
// Calculate value using
// previously stored values
else
P[i][j] = P[i - 1][j] +
(j * P[i - 1][j - 1]);
// This step is important
// as P(i,j)=0 for j>i
P[i][j + 1] = 0;
}
}
return P[n][k];
}
// Driver Code
int main()
{
int n = 10, k = 2;
printf("Value of P(%d, %d) is %d ",
n, k, permutationCoeff(n, k));
return 0;
}
Java
// Java code for Dynamic Programming based
// solution that uses table P[][] to
// calculate the Permutation Coefficient
import java.io.*;
import java.math.*;
class GFG
{
// Returns value of Permutation
// Coefficient P(n, k)
static int permutationCoeff(int n,
int k)
{
int P[][] = new int[n + 2][k + 2];
// Calculate value of Permutation
// Coefficient in bottom up manner
for (int i = 0; i <= n; i++)
{
for (int j = 0;
j <= Math.min(i, k);
j++)
{
// Base Cases
if (j == 0)
P[i][j] = 1;
// Calculate value using previously
// stored values
else
P[i][j] = P[i - 1][j] +
(j * P[i - 1][j - 1]);
// This step is important
// as P(i,j)=0 for j>i
P[i][j + 1] = 0;
}
}
return P[n][k];
}
// Driver Code
public static void main(String args[])
{
int n = 10, k = 2;
System.out.println("Value of P( " + n + ","+ k +")" +
" is " + permutationCoeff(n, k) );
}
}
// This code is contributed by Nikita Tiwari.
Python3
# A Dynamic Programming based
# solution that uses
# table P[][] to calculate the
# Permutation Coefficient
# Returns value of Permutation
# Coefficient P(n, k)
def permutationCoeff(n, k):
P = [[0 for i in range(k + 1)]
for j in range(n + 1)]
# Calculate value of Permutation
# Coefficient in
# bottom up manner
for i in range(n + 1):
for j in range(min(i, k) + 1):
# Base cases
if (j == 0):
P[i][j] = 1
# Calculate value using
# previously stored values
else:
P[i][j] = P[i - 1][j] + (
j * P[i - 1][j - 1])
# This step is important
# as P(i, j) = 0 for j>i
if (j < k):
P[i][j + 1] = 0
return P[n][k]
# Driver Code
n = 10
k = 2
print("Value of P(", n, ", ", k, ") is ",
permutationCoeff(n, k), sep = "")
# This code is contributed by Soumen Ghosh.
C#
// C# code for Dynamic Programming based
// solution that uses table P[][] to
// calculate the Permutation Coefficient
using System;
class GFG
{
// Returns value of Permutation
// Coefficient P(n, k)
static int permutationCoeff(int n,
int k)
{
int [,]P = new int[n + 2,k + 2];
// Calculate value of Permutation
// Coefficient in bottom up manner
for (int i = 0; i <= n; i++)
{
for (int j = 0;
j <= Math.Min(i, k);
j++)
{
// Base Cases
if (j == 0)
P[i,j] = 1;
// Calculate value using previously
// stored values
else
P[i,j] = P[i - 1,j] +
(j * P[i - 1,j - 1]);
// This step is important
// as P(i,j)=0 for j>i
P[i,j + 1] = 0;
}
}
return P[n,k];
}
// Driver Code
public static void Main()
{
int n = 10, k = 2;
Console.WriteLine("Value of P( " + n +
","+ k +")" + " is " +
permutationCoeff(n, k) );
}
}
// This code is contributed by anuj_67..
PHP
<?php
// A Dynamic Programming based
// solution that uses table P[][]
// to calculate the Permutation
// Coefficient
// Returns value of Permutation
// Coefficient P(n, k)
function permutationCoeff( $n, $k)
{
$P = array(array());
// Calculate value of Permutation
// Coefficient in bottom up manner
for($i = 0; $i <= $n; $i++)
{
for($j = 0; $j <= min($i, $k); $j++)
{
// Base Cases
if ($j == 0)
$P[$i][$j] = 1;
// Calculate value using
// previously stored values
else
$P[$i][$j] = $P[$i - 1][$j] +
($j * $P[$i - 1][$j - 1]);
// This step is important
// as P(i,j)=0 for j>i
$P[$i][$j + 1] = 0;
}
}
return $P[$n][$k];
}
// Driver Code
$n = 10; $k = 2;
echo "Value of P(",$n," ,",$k,") is ",
permutationCoeff($n, $k);
// This code is contributed by anuj_67.
?>
Javascript
<script>
// Javascript code for Dynamic Programming based
// solution that uses table P[][] to
// calculate the Permutation Coefficient
// Returns value of Permutation
// Coefficient P(n, k)
function permutationCoeff(n, k)
{
let P = new Array(n + 2);
for(let i = 0; i < n + 2; i++)
{
P[i] = new Array(k + 2);
}
// Calculate value of Permutation
// Coefficient in bottom up manner
for (let i = 0; i <= n; i++)
{
for (let j = 0; j <= Math.min(i, k); j++)
{
// Base Cases
if (j == 0)
P[i][j] = 1;
// Calculate value using previously
// stored values
else
P[i][j] = P[i - 1][j] + (j * P[i - 1][j - 1]);
// This step is important
// as P(i,j)=0 for j>i
P[i][j + 1] = 0;
}
}
return P[n][k];
}
let n = 10, k = 2;
document.write("Value of P(" + n + ","+ k +")" + " is " + permutationCoeff(n, k) );
// This code is contributed by decode2207.
</script>
Producción :
Value of P(10, 2) is 90
Aquí, como podemos ver, la complejidad del tiempo es O(n*k) y la complejidad del espacio es O(n*k) ya que el programa usa una array auxiliar para almacenar el resultado.
¿Podemos hacerlo en tiempo O(n)?
Supongamos que mantenemos una sola array 1D para calcular los factoriales hasta n. ¡Podemos usar el valor factorial calculado y aplicar la fórmula P(n, k) = n! / (nk)!. A continuación se muestra un programa que ilustra el mismo concepto.
C++
// A O(n) solution that uses
// table fact[] to calculate
// the Permutation Coefficient
#include<bits/stdc++.h>
using namespace std;
// Returns value of Permutation
// Coefficient P(n, k)
int permutationCoeff(int n, int k)
{
int fact[n + 1];
// Base case
fact[0] = 1;
// Calculate value
// factorials up to n
for(int i = 1; i <= n; i++)
fact[i] = i * fact[i - 1];
// P(n,k) = n! / (n - k)!
return fact[n] / fact[n - k];
}
// Driver Code
int main()
{
int n = 10, k = 2;
cout << "Value of P(" << n << ", "
<< k << ") is "
<< permutationCoeff(n, k);
return 0;
}
// This code is contributed by shubhamsingh10
C
// A O(n) solution that uses
// table fact[] to calculate
// the Permutation Coefficient
#include<bits/stdc++.h>
// Returns value of Permutation
// Coefficient P(n, k)
int permutationCoeff(int n, int k)
{
int fact[n + 1];
// base case
fact[0] = 1;
// Calculate value
// factorials up to n
for (int i = 1; i <= n; i++)
fact[i] = i * fact[i - 1];
// P(n,k) = n! / (n - k)!
return fact[n] / fact[n - k];
}
// Driver Code
int main()
{
int n = 10, k = 2;
printf ("Value of P(%d, %d) is %d ",
n, k, permutationCoeff(n, k) );
return 0;
}
Java
// A O(n) solution that uses
// table fact[] to calculate
// the Permutation Coefficient
import java .io.*;
public class GFG {
// Returns value of Permutation
// Coefficient P(n, k)
static int permutationCoeff(int n,
int k)
{
int []fact = new int[n+1];
// base case
fact[0] = 1;
// Calculate value
// factorials up to n
for (int i = 1; i <= n; i++)
fact[i] = i * fact[i - 1];
// P(n,k) = n! / (n - k)!
return fact[n] / fact[n - k];
}
// Driver Code
static public void main (String[] args)
{
int n = 10, k = 2;
System.out.println("Value of"
+ " P( " + n + ", " + k + ") is "
+ permutationCoeff(n, k) );
}
}
// This code is contributed by anuj_67.
Python3
# A O(n) solution that uses
# table fact[] to calculate
# the Permutation Coefficient
# Returns value of Permutation
# Coefficient P(n, k)
def permutationCoeff(n, k):
fact = [0 for i in range(n + 1)]
# base case
fact[0] = 1
# Calculate value
# factorials up to n
for i in range(1, n + 1):
fact[i] = i * fact[i - 1]
# P(n, k) = n!/(n-k)!
return int(fact[n] / fact[n - k])
# Driver Code
n = 10
k = 2
print("Value of P(", n, ", ", k, ") is ",
permutationCoeff(n, k), sep = "")
# This code is contributed
# by Soumen Ghosh
C#
// A O(n) solution that uses
// table fact[] to calculate
// the Permutation Coefficient
using System;
public class GFG {
// Returns value of Permutation
// Coefficient P(n, k)
static int permutationCoeff(int n,
int k)
{
int []fact = new int[n+1];
// base case
fact[0] = 1;
// Calculate value
// factorials up to n
for (int i = 1; i <= n; i++)
fact[i] = i * fact[i - 1];
// P(n,k) = n! / (n - k)!
return fact[n] / fact[n - k];
}
// Driver Code
static public void Main ()
{
int n = 10, k = 2;
Console.WriteLine("Value of"
+ " P( " + n + ", " + k + ") is "
+ permutationCoeff(n, k) );
}
}
// This code is contributed by anuj_67.
PHP
<?php
// A O(n) Solution that
// uses table fact[] to
// calculate the Permutation
// Coefficient
// Returns value of Permutation
// Coefficient P(n, k)
function permutationCoeff($n, $k)
{
$fact = array();
// base case
$fact[0] = 1;
// Calculate value
// factorials up to n
for ($i = 1; $i <= $n; $i++)
$fact[$i] = $i * $fact[$i - 1];
// P(n,k)= n!/(n-k)!
return $fact[$n] / $fact[$n - $k];
}
// Driver Code
$n = 10;
$k = 2;
echo"Value of P(",$n," ", $k,") is ",
permutationCoeff($n, $k) ;
// This code is contributed by anuj_67.
?>
Javascript
<script>
// A O(n) solution that uses
// table fact[] to calculate
// the Permutation Coefficient
// Returns value of Permutation
// Coefficient P(n, k)
function permutationCoeff(n, k)
{
let fact = new Array(n+1);
// base case
fact[0] = 1;
// Calculate value
// factorials up to n
for (let i = 1; i <= n; i++)
fact[i] = i * fact[i - 1];
// P(n,k) = n! / (n - k)!
return parseInt(fact[n] / fact[n - k], 10);
}
let n = 10, k = 2;
document.write("Value of"
+ " P(" + n + ", " + k + ") is "
+ permutationCoeff(n, k) );
</script>
Producción :
Value of P(10, 2) is 90
AO(n) tiempo y O(1) Solución Extra Espacial
C++
// A O(n) time and O(1) extra
// space solution to calculate
// the Permutation Coefficient
#include <iostream>
using namespace std;
int PermutationCoeff(int n, int k)
{
int P = 1;
// Compute n*(n-1)*(n-2)....(n-k+1)
for (int i = 0; i < k; i++)
P *= (n-i) ;
return P;
}
// Driver Code
int main()
{
int n = 10, k = 2;
cout << "Value of P(" << n << ", " << k
<< ") is " << PermutationCoeff(n, k);
return 0;
}
Java
// A O(n) time and O(1) extra
// space solution to calculate
// the Permutation Coefficient
import java.io.*;
class GFG
{
static int PermutationCoeff(int n,
int k)
{
int Fn = 1, Fk = 1;
// Compute n! and (n-k)!
for (int i = 1; i <= n; i++)
{
Fn *= i;
if (i == n - k)
Fk = Fn;
}
int coeff = Fn / Fk;
return coeff;
}
// Driver Code
public static void main(String args[])
{
int n = 10, k = 2;
System.out.println("Value of P( " + n + "," +
k +") is " +
PermutationCoeff(n, k) );
}
}
// This code is contributed by Nikita Tiwari.
C#
// A O(n) time and O(1) extra
// space solution to calculate
// the Permutation Coefficient
using System;
class GFG {
static int PermutationCoeff(int n,
int k)
{
int Fn = 1, Fk = 1;
// Compute n! and (n-k)!
for (int i = 1; i <= n; i++)
{
Fn *= i;
if (i == n - k)
Fk = Fn;
}
int coeff = Fn / Fk;
return coeff;
}
// Driver Code
public static void Main()
{
int n = 10, k = 2;
Console.WriteLine("Value of P( "
+ n + "," + k +") is "
+ PermutationCoeff(n, k) );
}
}
// This code is contributed by anuj_67.
PHP
<?php
// A O(n) time and O(1) extra
// space PHP solution to calculate
// the Permutation Coefficient
function PermutationCoeff( $n, $k)
{
$Fn = 1; $Fk;
// Compute n! and (n-k)!
for ( $i = 1; $i <= $n; $i++)
{
$Fn *= $i;
if ($i == $n - $k)
$Fk = $Fn;
}
$coeff = $Fn / $Fk;
return $coeff;
}
// Driver Code
$n = 10; $k = 2;
echo "Value of P(" , $n , ", " , $k , ")
is " , PermutationCoeff($n, $k);
// This code is contributed by anuj_67.
?>
Javascript
<script>
// A O(n) time and O(1) extra
// space solution to calculate
// the Permutation Coefficient
function PermutationCoeff(n, k)
{
let P = 1;
// Compute n*(n-1)*(n-2)....(n-k+1)
for(let i = 0; i < k; i++)
P *= (n - i);
return P;
}
// Driver code
let n = 10, k = 2;
document.write("Value of P(" + n +
", " + k + ") is " +
PermutationCoeff(n, k));
// This code is contributed by divyesh072019
</script>
Python3
# A O(n) solution that uses
# table fact[] to calculate
# the Permutation Coefficient
# Returns value of Permutation
# Coefficient P(n, k)
def permutationCoeff(n, k):
f=1
for i in range(k): #P(n,k)=n*(n-1)*(n-2)*....(n-k-1)
f*=(n-i)
return f #This code is contributed by Suyash Saxena
# Driver Code
n = 10
k = 2
print("Value of P(", n, ", ", k, ") is ",
permutationCoeff(n, k))
Producción :
Value of P(10, 2) is 90
Gracias a Shiva Kumar por sugerir esta solución.
Este artículo es una contribución de Ashutosh Kumar . Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA