Dados dos enteros positivos n y k , la tarea es contar el número de permutaciones especiales. Una permutación especial P se define como una permutación de los primeros n números naturales en los que existen al menos (n – k) índices tales que P i = i .
Prerrequisito: Trastornos
Ejemplos:
Entrada: n = 4, k = 2
Salida: 7
{1, 2, 3, 4}, {1, 2, 4, 3}, {4, 2, 3, 1}, {2, 1, 3, 4 }, {1, 4, 3, 2}, {1, 3, 2, 4} y {3, 2, 1, 4} son las únicas permutaciones especiales posibles.Entrada: n = 5, k = 3
Salida: 31
Enfoque: Deje que la función f x denote el número de permutaciones especiales en las que existen exactamente x índices tales que P i = i . Por lo tanto, la respuesta requerida será:
f (n – k) + f (n – k + 1) + f (n – k + 2) + … + f (n – 1) + f norte
Ahora, f x se puede calcular eligiendo x índices de n donde P i = i y calculando el número de desarreglos para (n – i) otros índices ya que para ellos P i no debería ser igual a i y luego multiplicando el resultado por n C x ya que puede haber diferentes formas de seleccionar x índices de n .
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program to count the number
// of required permutations
#include <bits/stdc++.h>
using namespace std;
#define ll long long int
// Function to return the number of ways
// to choose r objects out of n objects
int nCr(int n, int r)
{
int ans = 1;
if (r > n - r)
r = n - r;
for (int i = 0; i < r; i++) {
ans *= (n - i);
ans /= (i + 1);
}
return ans;
}
// Function to return the number
// of derangements of n
int countDerangements(int n)
{
int der[n + 1];
der[0] = 1;
der[1] = 0;
der[2] = 1;
for (int i = 3; i <= n; i++)
der[i] = (i - 1) * (der[i - 1]
+ der[i - 2]);
return der[n];
}
// Function to return the required
// number of permutations
ll countPermutations(int n, int k)
{
ll ans = 0;
for (int i = n - k; i <= n; i++) {
// Ways to choose i indices from n indices
int ways = nCr(n, i);
// Derangements of (n - i) indices
ans += ways * countDerangements(n - i);
}
return ans;
}
// Driver Code to test above functions
int main()
{
int n = 5, k = 3;
cout << countPermutations(n, k);
return 0;
}
Java
// Java program to count the number
// of required permutations
public class GFG{
// Function to return the number of ways
// to choose r objects out of n objects
static int nCr(int n, int r)
{
int ans = 1;
if (r > n - r)
r = n - r;
for (int i = 0; i < r; i++) {
ans *= (n - i);
ans /= (i + 1);
}
return ans;
}
// Function to return the number
// of derangements of n
static int countDerangements(int n)
{
int der[] = new int[ n + 3];
der[0] = 1;
der[1] = 0;
der[2] = 1;
for (int i = 3; i <= n; i++)
der[i] = (i - 1) * (der[i - 1]
+ der[i - 2]);
return der[n];
}
// Function to return the required
// number of permutations
static int countPermutations(int n, int k)
{
int ans = 0;
for (int i = n - k; i <= n; i++) {
// Ways to choose i indices from n indices
int ways = nCr(n, i);
// Derangements of (n - i) indices
//System.out.println(ans) ;
ans += (ways * countDerangements(n- i));
}
return ans;
}
// Driver Code to test above functions
public static void main(String []args)
{
int n = 5, k = 3;
System.out.println(countPermutations(n, k)) ;
}
// This code is contributed by Ryuga
}
Python3
# Python 3 program to count the number # of required permutation # function to return the number of ways # to chooser objects out of n objects def nCr(n, r): ans = 1 if r > n - r: r = n - r for i in range(r): ans *= (n - i) ans /= (i + 1) return ans # function to return the number of # degrangemnets of n def countDerangements(n): der = [0 for i in range(n + 3)] der[0] = 1 der[1] = 0 der[2] = 1 for i in range(3, n + 1): der[i] = (i - 1) * (der[i - 1] + der[i - 2]) return der[n] # function to return the required # number of permutations def countPermutations(n, k): ans = 0 for i in range(n - k, n + 1): # ways to chose i indices # from n indices ways = nCr(n, i) # Derangements of (n-i) indices ans += ways * countDerangements(n - i) return ans # Driver Code n, k = 5, 3 print(countPermutations(n, k)) # This code is contributed by # Mohit kumar 29 (IIIT gwalior)
C#
// C# program to count the number
// of required permutations
using System;
public class GFG{
// Function to return the number of ways
// to choose r objects out of n objects
static int nCr(int n, int r)
{
int ans = 1;
if (r > n - r)
r = n - r;
for (int i = 0; i < r; i++) {
ans *= (n - i);
ans /= (i + 1);
}
return ans;
}
// Function to return the number
// of derangements of n
static int countDerangements(int n)
{
int []der = new int[ n + 3];
der[0] = 1;
der[1] = 0;
der[2] = 1;
for (int i = 3; i <= n; i++)
der[i] = (i - 1) * (der[i - 1]
+ der[i - 2]);
return der[n];
}
// Function to return the required
// number of permutations
static int countPermutations(int n, int k)
{
int ans = 0;
for (int i = n - k; i <= n; i++) {
// Ways to choose i indices from n indices
int ways = nCr(n, i);
// Derangements of (n - i) indices
//System.out.println(ans) ;
ans += (ways * countDerangements(n- i));
}
return ans;
}
// Driver Code to test above functions
public static void Main()
{
int n = 5, k = 3;
Console.WriteLine(countPermutations(n, k)) ;
}
}
// This code is contributed by 29AjayKumar
PHP
<?php
// PHP program to count the number
// of required permutations
// Function to return the number of ways
// to choose r objects out of n objects
function nCr($n, $r)
{
$ans = 1;
if ($r > $n - $r)
$r = $n - $r;
for ($i = 0; $i < $r; $i++)
{
$ans *= ($n - $i);
$ans /= ($i + 1);
}
return $ans;
}
// Function to return the number
// of derangements of n
function countDerangements($n)
{
$der = array($n + 1);
$der[0] = 1;
$der[1] = 0;
$der[2] = 1;
for ($i = 3; $i <= $n; $i++)
$der[$i] = ($i - 1) *
($der[$i - 1] +
$der[$i - 2]);
return $der[$n];
}
// Function to return the required
// number of permutations
function countPermutations($n, $k)
{
$ans = 0;
for ($i = $n - $k; $i <= $n; $i++)
{
// Ways to choose i indices
// from n indices
$ways = nCr($n, $i);
// Derangements of (n - i) indices
$ans += $ways * countDerangements($n - $i);
}
return $ans;
}
// Driver Code
$n = 5;
$k = 3;
echo (countPermutations($n, $k));
// This code is contributed
// by Shivi_Aggarwal
?>
Javascript
<script>
// JavaScript program to count the number
// of required permutations
// Function to return the number of ways
// to choose r objects out of n objects
function nCr(n, r) {
var ans = 1;
if (r > n - r) r = n - r;
for (var i = 0; i < r; i++) {
ans *= n - i;
ans /= i + 1;
}
return ans;
}
// Function to return the number
// of derangements of n
function countDerangements(n) {
var der = [...Array(n + 1)];
der[0] = 1;
der[1] = 0;
der[2] = 1;
for (var i = 3; i <= n; i++)
der[i] = (i - 1) * (der[i - 1] + der[i - 2]);
return der[n];
}
// Function to return the required
// number of permutations
function countPermutations(n, k) {
var ans = 0;
for (var i = n - k; i <= n; i++) {
// Ways to choose i indices from n indices
var ways = nCr(n, i);
// Derangements of (n - i) indices
ans += ways * countDerangements(n - i);
}
return ans;
}
// Driver Code to test above functions
var n = 5,
k = 3;
document.write(countPermutations(n, k));
</script>
Producción:
31
Complejidad de Tiempo: O(N^2), ya que corre un bucle dentro de otro bucle.
Espacio Auxiliar: O(N), ya que se ha tomado N espacio extra.
Publicación traducida automáticamente
Artículo escrito por Nishant Tanwar y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA