Рубрики

Нарушения счета (перестановка, при которой элемент не появляется в исходном положении)

Derangement — это перестановка из n элементов, так что ни один элемент не появляется в исходном положении. Например, отклонение {0, 1, 2, 3} равно {2, 3, 1, 0}.

По заданному числу n найти общее количество неисправностей из набора из n элементов.

Примеры :

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}

Пусть countDer (n) будет количеством нарушений для n элементов. Ниже приведено рекурсивное отношение к нему.

countDer(n) = (n - 1) * [countDer(n - 1) + countDer(n - 2)]

Как работает вышеуказанное рекурсивное отношение?
Для элемента 0 существует n — 1 способов (это объясняет умножение на n — 1).

Пусть 0 будет помещен в индекс i . Теперь есть две возможности, в зависимости от того, помещен ли элемент i в 0 взамен.

  1. я помещен в 0: этот случай эквивалентен решению проблемы для n-2 элементов, так как два элемента только поменялись местами.
  2. i не помещается в 0: этот случай эквивалентен решению проблемы для n-1 элементов, так как теперь есть n-1 элементов, n-1 позиций, и каждый элемент имеет n-2 выбора

Ниже приведено простое решение на основе приведенной выше рекурсивной формулы.

C ++

// Наивная рекурсивная программа на C ++
// посчитать неисправности
#include <bits/stdc++.h>

using namespace std;

  

int countDer(int n)

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

if (n == 1) return 0;

if (n == 0) return 1;

if (n == 2) return 1;

  
// countDer (n) = (n-1) [countDer (n-1) + der (n-2)]

return (n - 1) * (countDer(n - 1) + 

                  countDer(n - 2));

}

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

int main()

{

    int n = 4;

    cout << "Count of Derangements is " 

         << countDer(n);

    return 0;

}

Джава

// Наивный рекурсивный Java
// программа для подсчета неисправностей

import java.io.*;

  

class GFG 

{

      

    // Функция для подсчета

    // расстройства

    static int countDer(int n)

    {

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

        if (n == 1) return 0;

        if (n == 0) return 1;

        if (n == 2) return 1;

          

        // countDer (n) = (n-1) [countDer (n-1) + der (n-2)]

        return (n - 1) * (countDer(n - 1) + 

                          countDer(n - 2));

    }

      

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

    public static void main (String[] args)

    {

        int n = 4;

        System.out.println( "Count of Derangements is "

                             +countDer(n));

  

    }

}

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

python3

# Наивный рекурсивный Python3
# программа для подсчета неисправностей

  

def countDer(n):

      

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

    if (n == 1): return 0

    if (n == 0): return 1

    if (n == 2): return 1

      

    # countDer (n) = (n-1) [countDer (n-1) + der (n-2)]

    return (n - 1) * (countDer(n - 1) + 

                      countDer(n - 2))

  
Код водителя

n = 4

print("Count of Derangements is ", countDer(n))

  

  
# Этот код предоставлен Azkia Anam.

C #

// Наивный рекурсивный C #
// программа для подсчета неисправностей

using System;

  

class GFG 

{

      

    // Функция для подсчета

    // расстройства

    static int countDer(int n)

    {

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

        if (n == 1) return 0;

        if (n == 0) return 1;

        if (n == 2) return 1;

          

        // countDer (n) = (n-1) [countDer (n-1) + der (n-2)]

        return (n - 1) * (countDer(n - 1) + 

                          countDer(n - 2));

    }

      

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

    public static void Main ()

    {

        int n = 4;

        Console.Write( "Count of Derangements is " +

                        countDer(n));

  

    }

}

  
// Этот код предоставлен нитин митталь.

PHP

<?php
// Наивная рекурсивная PHP-программа
// посчитать неисправности

  

function countDer($n)

{

      

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

    if ($n == 1) 

        return 0;

    if ($n == 0)

        return 1;

    if ($n == 2) 

        return 1;

      

    // countDer (n) = (n-1) [countDer (n-1) +

    // der (n-2)]

    return ($n - 1) * (countDer($n - 1) + 

                       countDer($n - 2));

}

  

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

    $n = 4;

    echo "Count of Derangements is ", countDer($n);

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


Выход:

Count of Derangements is 9

Сложность времени: T (n) = T (n-1) + T (n-2), которая является экспоненциальной.
Мы можем наблюдать, что эта реализация делает повторную работу. Например, см. Дерево рекурсии для countDer (5), countDer (3) оценивается дважды.

cdr() ==> countDer()

                    cdr(5)   
                 /         \     
             cdr(4)          cdr(3)   
           /      \         /     \
       cdr(3)     cdr(2)  cdr(2)   cdr(1)

Эффективным решением является использование динамического программирования для хранения результатов подзадач в массиве и построения массива снизу вверх.

C ++

// Динамическое программирование на C ++
// программа для подсчета неисправностей
#include <bits/stdc++.h>

using namespace std;

  

int countDer(int n)

{

    // Создать массив для хранения

    // подсчитывает подзадачи

    int der[n + 1];

  

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

    der[0] = 1;

    der[1] = 0;

    der[2] = 1;

  

    // Заполняем der [0..n] снизу вверх

    // используя приведенную выше рекурсивную формулу

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

        der[i] = (i - 1) * (der[i - 1] + 

                            der[i - 2]);

  

    // Возвращаем результат для n

    return der[n];

}

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

int main()

{

    int n = 4;

    cout << "Count of Derangements is " 

         << countDer(n);

    return 0;

}

Джава

// Динамическое программирование на основе
// Java-программа для подсчета неисправностей

import java.io.*;

  

class GFG 

{

      

    // Функция для подсчета

    // расстройства

    static int countDer(int n)

    {

        // Создать массив для хранения

        // подсчитывает подзадачи

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

      

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

        der[0] = 1;

        der[1] = 0;

        der[2] = 1;

      

        // Заполняем der [0..n] снизу вверх

        // способ, использующий выше рекурсивный

        // формула

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

            der[i] = (i - 1) * (der[i - 1] + 

                                der[i - 2]);

      

        // Возвращаем результат для n

        return der[n];

    }

      

    // Драйвер программы

    public static void main (String[] args) 

    {

        int n = 4;

        System.out.println("Count of Derangements is "

                            countDer(n));

      

    }

}

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

python3

# Динамическое программирование на основе Python3
# программа для подсчета неисправностей

  

def countDer(n):

      

    # Создать массив для хранения

    # подсчитывает подзадачи

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

      

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

    der[0] = 1

    der[1] = 0

    der[2] = 1

      

    # Заполните der [0..n] снизу вверх

    # используя приведенную выше рекурсивную формулу

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

        der[i] = (i - 1) * (der[i - 1] + 

                            der[i - 2])

          

    # Вернуть результат для n

    return der[n]

  
Код водителя

n = 4

print("Count of Derangements is ", countDer(n))

  
# Этот код предоставлен Azkia Anam.

C #

   
// Динамическое программирование на основе
// C # программа для подсчета неисправностей

using System;

  

class GFG 

{

      

    // Функция для подсчета

    // расстройства

    static int countDer(int n)

    {

        // Создать массив для хранения

        // подсчитывает подзадачи

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

      

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

        der[0] = 1;

        der[1] = 0;

        der[2] = 1;

      

        // Заполняем der [0..n] снизу вверх

        // способ, использующий выше рекурсивный

        // формула

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

            der[i] = (i - 1) * (der[i - 1] + 

                                der[i - 2]);

      

        // Возвращаем результат для n

        return der[n];

    }

      

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

    public static void Main () 

    {

        int n = 4;

        Console.Write("Count of Derangements is "

                       countDer(n));

      

    }

}

  
// Этот код предоставлен нитин митталь

PHP

<?php
// Динамическое программирование на основе PHP
// программа для подсчета неисправностей

  

function countDer($n)

{

    // Создать массив для хранения

    // подсчитывает подзадачи

  

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

    $der[0] = 1;

    $der[1] = 0;

    $der[2] = 1;

  

    // Заполняем der [0..n] снизу вверх

    // используя приведенную выше рекурсивную формулу

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

        $der[$i] = ($i - 1) * ($der[$i - 1] + 

                               $der[$i - 2]);

  

    // Возвращаем результат для n

    return $der[$n];

}

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

$n = 4;

echo "Count of Derangements is ",

                    countDer($n);

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



Выход :

Count of Derangements is 9

Сложность времени: O (n)
Вспомогательное пространство: O (n)

Спасибо Уткаршу Триведи за предложенное решение.

Ссылки:
https://en.wikipedia.org/wiki/Derangement

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

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

Нарушения счета (перестановка, при которой элемент не появляется в исходном положении)

0.00 (0%) 0 votes