Un Trastorno es una permutación de n elementos, de modo que ningún elemento aparece en su posición original. Por ejemplo, un trastorno de {0, 1, 2, 3} es {2, 3, 1, 0}.
Dado un número n, encuentre el número total de Trastornos de un conjunto de n elementos.
Ejemplos:
Input: n = 2
Output: 1
For two elements say {0, 1}, there is only one
possible derangement {1, 0}
Input: n = 3
Output: 2
For three elements say {0, 1, 2}, there are two
possible derangements {2, 0, 1} and {1, 2, 0}
Input: n = 4
Output: 9
For four elements say {0, 1, 2, 3}, there are 9
possible derangements {1, 0, 3, 2} {1, 2, 3, 0}
{1, 3, 0, 2}, {2, 3, 0, 1}, {2, 0, 3, 1}, {2, 3,
1, 0}, {3, 0, 1, 2}, {3, 2, 0, 1} and {3, 2, 1, 0}
Sea countDer(n) el conteo de desarreglos para n elementos. A continuación se muestra la relación recursiva con él.
countDer(n) = (n - 1) * [countDer(n - 1) + countDer(n - 2)]
¿Cómo funciona la relación recursiva anterior?
Hay n – 1 forma para el elemento 0 (esto explica la multiplicación con n – 1).
Sea 0 el índice i . Ahora hay dos posibilidades, dependiendo de si el elemento i se coloca o no en 0 a cambio.
- i se coloca en 0: este caso es equivalente a resolver el problema para n-2 elementos ya que dos elementos acaban de intercambiar sus posiciones.
- i no se coloca en 0: este caso es equivalente a resolver el problema para n-1 elementos, ya que ahora hay n-1 elementos, n-1 posiciones y cada elemento tiene n-2 opciones
A continuación se muestra la solución simple basada en la fórmula recursiva anterior:
C++
// A Naive Recursive C++ program
// to count derangements
#include <bits/stdc++.h>
using namespace std;
int countDer(int n)
{
// Base cases
if (n == 1) return 0;
if (n == 2) return 1;
// countDer(n) = (n-1)[countDer(n-1) + der(n-2)]
return (n - 1) * (countDer(n - 1) + countDer(n - 2));
}
// Driver Code
int main()
{
int n = 4;
cout << "Count of Derangements is "
<< countDer(n);
return 0;
}
Java
// A Naive Recursive java
// program to count derangements
import java.io.*;
class GFG
{
// Function to count
// derangements
static int countDer(int n)
{
// Base cases
if (n == 1) return 0;
if (n == 2) return 1;
// countDer(n) = (n-1)[countDer(n-1) + der(n-2)]
return (n - 1) * (countDer(n - 1) +
countDer(n - 2));
}
// Driver Code
public static void main (String[] args)
{
int n = 4;
System.out.println( "Count of Derangements is "
+countDer(n));
}
}
// This code is contributed by vt_m
Python3
# A Naive Recursive Python3
# program to count derangements
def countDer(n):
# Base cases
if (n == 1): return 0
if (n == 2): return 1
# countDer(n) = (n-1)[countDer(n-1) + der(n-2)]
return (n - 1) * (countDer(n - 1) +
countDer(n - 2))
# Driver Code
n = 4
print("Count of Derangements is ", countDer(n))
# This code is contributed by Azkia Anam.
C#
// A Naive Recursive C#
// program to count derangements
using System;
class GFG
{
// Function to count
// derangements
static int countDer(int n)
{
// Base cases
if (n == 1) return 0;
if (n == 2) return 1;
// countDer(n) = (n-1)[countDer(n-1) + der(n-2)]
return (n - 1) * (countDer(n - 1) +
countDer(n - 2));
}
// Driver Code
public static void Main ()
{
int n = 4;
Console.Write( "Count of Derangements is " +
countDer(n));
}
}
// This code is contributed by nitin mittal.
PHP
<?php
// A Naive Recursive PHP program
// to count derangements
function countDer($n)
{
// Base cases
if ($n == 1)
return 0;
if ($n == 2)
return 1;
// countDer(n) = (n-1)[countDer(n-1) +
// der(n-2)]
return ($n - 1) * (countDer($n - 1) +
countDer($n - 2));
}
// Driver Code
$n = 4;
echo "Count of Derangements is ", countDer($n);
// This code is contributed by nitin mittal.
?>
Javascript
<script>
// A Naive Recursive Javascript
// program to count derangements
// Function to count
// derangements
function countDer(n)
{
// Base cases
if (n == 1) return 0;
if (n == 2) return 1;
// countDer(n) = (n-1)[countDer(n-1) + der(n-2)]
return (n - 1) * (countDer(n - 1) + countDer(n - 2));
}
let n = 4;
document.write("Count of Derangements is " + countDer(n));
</script>
Producción
Count of Derangements is 9
Complejidad de tiempo: O(2^n) ya que T(n) = T(n-1) + T(n-2) que es exponencial.
Espacio Auxiliar: O(h) donde h= log n es la altura máxima del árbol.
Podemos observar que esta implementación hace un trabajo repetitivo. Por ejemplo, vea el árbol de recurrencia para countDer(5), countDer(3) se evalúa dos veces.
cdr() ==> countDer()
cdr(5)
/ \
cdr(4) cdr(3)
/ \ / \
cdr(3) cdr(2) cdr(2) cdr(1)
Una solución eficiente es utilizar la programación dinámica para almacenar los resultados de los subproblemas en una array y construir la array de forma ascendente.
C++
// A Dynamic programming based C++
// program to count derangements
#include <bits/stdc++.h>
using namespace std;
int countDer(int n)
{
// Create an array to store
// counts for subproblems
int der[n + 1] = {0};
// Base cases
der[1] = 0;
der[2] = 1;
// Fill der[0..n] in bottom up manner
// using above recursive formula
for (int i = 3; i <= n; ++i)
der[i] = (i - 1) * (der[i - 1] +
der[i - 2]);
// Return result for n
return der[n];
}
// Driver code
int main()
{
int n = 4;
cout << "Count of Derangements is "
<< countDer(n);
return 0;
}
Java
// A Dynamic programming based
// java program to count derangements
import java.io.*;
class GFG
{
// Function to count
// derangements
static int countDer(int n)
{
// Create an array to store
// counts for subproblems
int der[] = new int[n + 1];
// Base cases
der[1] = 0;
der[2] = 1;
// Fill der[0..n] in bottom up
// manner using above recursive
// formula
for (int i = 3; i <= n; ++i)
der[i] = (i - 1) * (der[i - 1] +
der[i - 2]);
// Return result for n
return der[n];
}
// Driver program
public static void main (String[] args)
{
int n = 4;
System.out.println("Count of Derangements is " +
countDer(n));
}
}
// This code is contributed by vt_m
Python3
# A Dynamic programming based Python3
# program to count derangements
def countDer(n):
# Create an array to store
# counts for subproblems
der = [0 for i in range(n + 1)]
# Base cases
der[1] = 0
der[2] = 1
# Fill der[0..n] in bottom up manner
# using above recursive formula
for i in range(3, n + 1):
der[i] = (i - 1) * (der[i - 1] +
der[i - 2])
# Return result for n
return der[n]
# Driver Code
n = 4
print("Count of Derangements is ", countDer(n))
# This code is contributed by Azkia Anam.
C#
// A Dynamic programming based
// C# program to count derangements
using System;
class GFG
{
// Function to count
// derangements
static int countDer(int n)
{
// Create an array to store
// counts for subproblems
int []der = new int[n + 1];
// Base cases
der[1] = 0;
der[2] = 1;
// Fill der[0..n] in bottom up
// manner using above recursive
// formula
for (int i = 3; i <= n; ++i)
der[i] = (i - 1) * (der[i - 1] +
der[i - 2]);
// Return result for n
return der[n];
}
// Driver code
public static void Main ()
{
int n = 4;
Console.Write("Count of Derangements is " +
countDer(n));
}
}
// This code is contributed by nitin mittal
PHP
<?php
// A Dynamic programming based PHP
// program to count derangements
function countDer($n)
{
// Create an array to store
// counts for subproblems
// Base cases
$der[1] = 0;
$der[2] = 1;
// Fill der[0..n] in bottom up manner
// using above recursive formula
for ($i = 3; $i <= $n; ++$i)
$der[$i] = ($i - 1) * ($der[$i - 1] +
$der[$i - 2]);
// Return result for n
return $der[$n];
}
// Driver code
$n = 4;
echo "Count of Derangements is ",
countDer($n);
// This code is contributed by aj_36
?>
Javascript
<script>
// A Dynamic programming based
// javascript program to count
// derangements
// Function to count
// derangements
function countDer(n)
{
// Create an array to store
// counts for subproblems
let der = new Array(n + 1);
// Base cases
der[1] = 0;
der[2] = 1;
// Fill der[0..n] in bottom up
// manner using above recursive
// formula
for (let i = 3; i <= n; ++i)
der[i] = (i - 1) * (der[i - 1] +
der[i - 2]);
// Return result for n
return der[n];
}
let n = 4;
document.write(
"Count of Derangements is " + countDer(n)
);
</script>
Producción
Count of Derangements is 9
Complejidad de tiempo: O(n)
Espacio auxiliar: O(n)
Gracias a Utkarsh Trivedi por sugerir la solución anterior.
Una solución más eficiente sin utilizar espacio adicional .
Como solo necesitamos recordar solo dos valores anteriores, en lugar de almacenar los valores en una array, se pueden usar dos variables para almacenar solo los valores anteriores requeridos.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ implementation of the above
// approach
#include <iostream>
using namespace std;
int countDer(int n)
{
// base case
if (n == 1 or n == 2) {
return n - 1;
}
// Variable for just storing
// previous values
int a = 0;
int b = 1;
// using above recursive formula
for (int i = 3; i <= n; ++i) {
int cur = (i - 1) * (a + b);
a = b;
b = cur;
}
// Return result for n
return b;
}
// Driver Code
int main()
{
cout << "Count of Derangements is " << countDer(4);
return 0;
}
// Code contributed by skagnihotri
Java
// Java implementation of the
// above approach
import java.io.*;
class GFG {
// Function to count derangements
static int countDer(int n) {
// Base case
if(n == 1 || n == 2) {
return n-1;
}
// Variable for storing prev values
int a = 0;
int b = 1;
// manner using above recursive formula
for (int i = 3; i <= n; ++i) {
int cur = (i-1)*(a+b);
a = b;
b = cur;
}
// Return result for n
return b;
}
// Driver Code
public static void main (String[] args)
{
int n = 4;
System.out.println("Count of Derangements is " +
countDer(n));
}
// Code contributed by skagnihotri
}
Python3
# Python program to count derangements
def countDer(n):
# Base Case
if n == 1 or n == 2:
return n-1;
# Variables for storing previous values
a = 0
b = 1
# using above recursive formula
for i in range(3, n + 1):
cur = (i-1)*(a+b)
a = b
b = cur
# Return result for n
return b
# Driver Code
n = 4
print("Count of Derangements is ", countDer(n))
# Code contributed by skagnihotri
C#
// C# implementation of the above
// approach
using System;
class GFG{
// Function to count
// derangements
static int countDer(int n)
{
// Base case
if (n == 1 || n == 2)
{
return n - 1;
}
// Variable for just storing
// previous values
int a = 0;
int b = 1;
// Using above recursive formula
for(int i = 3; i <= n; ++i)
{
int cur = (i - 1) * (a + b);
a = b;
b = cur;
}
// Return result for n
return b;
}
// Driver code
public static void Main()
{
Console.Write("Count of Derangements is " +
countDer(4));
}
}
// This code is contributed by koulick_sadhu
Javascript
<script>
// Javascript implementation
// of the above approach
// Function to count
// derangements
function countDer(n)
{
// Base case
if (n == 1 || n == 2)
{
return n - 1;
}
// Variable for just storing
// previous values
let a = 0;
let b = 1;
// Using above recursive formula
for(let i = 3; i <= n; ++i)
{
let cur = (i - 1) * (a + b);
a = b;
b = cur;
}
// Return result for n
return b;
}
document.write("Count of Derangements is "
+ countDer(4));
</script>
Producción
Count of Derangements is 9
Complejidad Temporal: O(n)
Espacio Auxiliar: O(1), ya que no se ha tomado ningún espacio extra.
Gracias a Shubham Kumar por sugerir la solución anterior.
Referencias:
https://en.wikipedia.org/wiki/Derangement
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