Very easy to understand C++ with explanation


  • 0

    The subfactorial function can be used to calculate the amount of derangements as follows:

    !n=(n-1)( !(n-1) + !(n-2) )

    Let's break this formula down into individual parts for simple and easy understanding:

    Part 0: !n=(n-1)( !(n-1) + !(n-2) )

    This part of the equation is basically just the way we refer to the subfactorial function of N. Let's create a function name d(n) such that d(n)=!n, then we can write this formula as follows with the same meaning, but instead of a leading "!", we have a leading function name "d":

    d(n)=(n-1)( d(n-1) + d(n-2) )

    Part 1: d(n)=(n-1)( d(n-1) + d(n-2) )

    We know by definition of a derangement, there are (N-1) possible repositions available for any arbitrary i-th position in an array from 1 to N inclusive: [1,2,3,...,N-2,N-1,N]. This is because there are N numbers, and any arbitrary i-th position is allowed to be repositioned into any of those N positions EXCEPT for the i-th position.

    Let's stop here and look at a simple example where N=2. For N=2, there are two elements in the array [1,2]. There are (N-1) possible repositions available. For N=2, (N-1)=(2-1)=1. That 1 position is available for each of these N numbers. That is the reason why this formula multiples by (N-1). 1 can be moved into 2's position, and 2 can be moved into 1's position:

    Before derangement: [1,2]
    After derangement: [2,1]

    There is only one derangement when N=2. We will build the base case from this example of N=2 after describing the recursive case in Part 2 below. This will soon be referred to as d(2) when discussing the base cases in part 3 below.

    Part 2 - Recursive Cases: d(n)=(n-1)( d(n-1) + d(n-2) )

    This section describes the recursive case. After we have chosen an arbitrary i-th position, that i-th position can either 1) be repositioned into the first position, or it can 2) be repositioned into any other position EXCEPT the first position.

    Case 1: if the i-th position is repositioned into the first position, then this can be done by swapping position 1 with position i:

    Before swap: [ 1, . . . , i, . . . , N ]
    After swap: [ i, . . . , 1, . . . , N ]

    So for this case, there are 2 set positions, position 1 is set to i, and position i is set to 1. Then there are N-2 positions to be deranged leftover, since 1 and i are already in their respective deranged positions for this use case. 1 and i are a total of 2 unique positions. N without these two positions ( 1 and i ) is formulated as N-2. These leftover N-2 positions still need to be deranged and are written in the formula as follows:

    d(n)=(n-1)( d(n-1) + d(n-2) )

    Case 2: if the i-th position is repositioned into any other position EXCEPT the first position, then we have N-1 positions to choose from (all N positions, EXCEPT for the first position). We subtract one from N, since the first position is NOT a possibility for this use case. Those N-1 positions still need to be deranged ( these N-1 positions include the arbitrary i-th position where 2<=i<=N ):

    d(n)=(n-1)( d(n-1) + d(n-2) )

    These two use cases are then added together in order to include all possible use cases in the return count of derangements.

    d(n)=(n-1)( d(n-1) + d(n-2) )

    Then the (N-1) possible repositions available for each use case is multiplied by the sum of these two use cases. This is the complete formula. All possible repositions (N-1) multiplied by the sum of all possible use cases for each reposition ( d(n-1) + d(n-2) ).

    d(n)=(n-1)( d(n-1) + d(n-2) )

    Part 3 - Base Cases:

    d(0) = 1
    d(1) = 0

    This is strange, right? To simply explain this, let's first take a look at d(1) more closely. How many possible ways can we derange an array of one: [ 1 ]? There are none. We cannot move 1 to another position other than it's original position. Therefore, d(1) = 0.

    Then why does d(0) = 1? Short answer: because this works and makes sense, similar to why 0 factorial = 1. Long answer: let's take a look back at our previous d(2) example:

    d(n)=(n-1)( d(n-1) + d(n-2) )

    N=2
    d(2)=(2-1)( d(2-1) + d(2-2) )
    d(2)=(1)( d(1) + d(0) )
    d(2)=d(1) + d(0)

    We know there is 1 derangement for an array of 2:

    Original arrangement: [1,2]
    After 1 derangement: [2,1]

    Therefore, d(2) = 1, and we also know from above that d(1) = 0. Since we know d(2), and we know d(1), we can derive d(0) as follows:

    d(2) = d(1) + d(0)
    1 = 0 + d(0)
    1 = d(0)

    Part 4 - Simple C++ Solution:

    This solution uses dynamic programming to build from the base cases 0,1, ... until N where curr_n is the current value of N being calculated, dn is the amount of derangements for that current value of N. And dn_minus_2 and dn_minus_1 are the two previous derangement calculations for dn.

    class Solution{
    public:
        int findDerangement(int n){
            if (n==0) { return 1; }
            if (n==1) { return 0; }
            int dn=1, dn_minus_1=0, dn_minus_2=1;
            for (int curr_n=2; curr_n <= n; curr_n++){
                dn=(int)((( curr_n - 1L )*( dn_minus_1 + dn_minus_2 ))%1000000007);
                dn_minus_2=dn_minus_1;
                dn_minus_1=dn;
            }
            return dn;
        }
    };
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.