Massive Algorithms: LeetCode 634 - Find the Derangement of An Array

LeetCode 634 - Find the Derangement of An Array

http://bookshadow.com/weblog/2017/07/02/leetcode-find-the-derangement-of-an-array/

In combinatorial mathematics, a derangement is a permutation of the elements of a set, such that no element appears in its original position.

There's originally an array consisting of n integers from 1 to n in ascending order, you need to find the number of derangement it can generate.

Also, since the answer may be very large, you should return the output mod 109 + 7.

Example 1:

Input: 3
Output: 2
Explanation: The original array is [1,2,3]. The two derangements are [2,3,1] and [3,1,2].

Note:
n is in the range of [1, 106].

X.
https://blog.csdn.net/magicbean2/article/details/79112988
组合数学中的错排问题。当n个编号元素放在n个编号位置，元素编号与位置编号各不对应的方法数用D(n)表示，那么D(n-1)就表示n-1个编号元素放在n-1个编号位置，各不对应的方法数，其它类推。推导方法如下：

1）把第n个元素放在某一个位置，比如位置k，那么一共有(n-1)中放法。

2）放编号为k的元素，此时有两种情况：a）把k放到位置n，那么对于剩下的n-2个元素，就一共有D(n-2)种放法；b）第k个元素不放在位置n，这时k连同其余的n-2个元素都各有一个位置不能放，所以有D(n-1)种放法。

因此，D(n) = (n - 1) (D(n - 2) + D(n - 1))，特别地，有D(1) = 0, D(2) = 1

http://code.bitjoy.net/2017/07/02/leetcode-find-the-derangement-of-an-array/

假设dp[n]表示长度为n的数组的错排个数，显然dp[0]=1,dp[1]=0,dp[2]=1。如果已经知道dp[0,...,n-1]，怎样求dp[n]。考虑第n个数，因为错排，它肯定不能放在第n位，假设n放在第k位，则有如下两种情况：

数字k放在了第n位，这时，相当于n和k交换了一下位置，还剩下n-2个数需要错排，所以+dp[n-2]

数字k不放在第n位，此时，可以理解为k原本的位置是n，也就是1不能放在第1位、2不能放在第2位、...、k不能放在第n位，也就相当于对n-1个数进行错排，所以+dp[n-1]

因为n可以放在1~n-1这n-1个位置，所以总的情况数等于dp[n]=(n-1)(dp[n-1]+dp[n-2])。

这就类似于求斐波那契数列的第n项了，维护前两个变量，不断滚动赋值就好了，时间复杂度O(n)

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

公式推导过程可以参考：https://en.wikipedia.org/wiki/Derangement

错位排列可以理解成将标号为1~n的帽子分配给标号为1~n的人，每个人拿到的帽子标号都与其自身的标号不同。

假设第一个人选取了标号为i的帽子，此时可分两种情况讨论：

1. 第i个人选择第一顶帽子，则问题规模缩小为n - 2

2, 3, 4, ..., i-1, i+1, ... n 人
2, 3, 4, ..., i-1, i+1, ... n 帽

2. 第i个人不选第一顶帽子，则问题规模缩小为n - 1（相当于第i个人不能选择第1顶帽子）

2, 3, 4, ..., i-1, i, i+1, ..., n 人
2, 3, 4, ..., i-1, 1, i+1, ..., n 帽

http://www.cnblogs.com/grandyang/p/7210929.html

这道题给了我们一个数组，让我们求其错排的个数，所谓错排就是1到n中的每个数字都不在其原有的位置上，全部打乱了，问能有多少种错排的方式。博主注意到了这道题又让对一个很大的数取余，而且每次那个很大的数都是10⁹ + 7，为啥大家都偏爱这个数呢，有啥特别之处吗？根据博主之前的经验，这种结果很大很大的题十有八九都是用dp来做的，那么就建一个一维的dp数组吧，其中dp[i]表示1到i中的错位排列的个数。那么难点就是找递推公式啦，先从最简单的情况来看:

n = 1 时有 0 种错排

n = 2 时有 1 种错排 [2, 1]

n = 3 时有 2 种错排 [3, 1, 2], [2, 3, 1]

然后博主就在想知道了dp[2]，能求出dp[3]吗，又在考虑是不是算加入数字3的情况的个数。结果左看右看发现没有啥特别的规律，又在想是不是有啥隐含的信息需要挖掘，还是没想出来。于是看了一眼标签，发现是Math，我的天，难道又是小学奥数的题？挣扎了半天最后还是放弃了，上网去搜大神们的解法。其实这道题是组合数学种的错排问题，是有专门的递归公式的。

我们来想n = 4时该怎么求，我们假设把4排在了第k位，这里我们就让k = 3吧，那么我们就把4放到了3的位置，变成了：

x x 4 x

我们看被4占了位置的3，应该放到哪里，这里分两种情况，如果3放到了4的位置，那么有：

x x 4 3

那么此时4和3的位置都确定了，实际上只用排1和2了，那么就相当于只排1和2，就是dp[2]的值，是已知的。那么再来看第二种情况，3不在4的位置，那么此时我们把4去掉的话，就又变成了：

x x x

这里3不能放在第3个x的位置，在去掉4之前，这里是移动4之前的4的位置，那么实际上这又变成了排1，2，3的情况了，就是dp[3]的值。

再回到最开始我们选k的时候，我们当时选了k = 3，其实k可以等于1,2,3，也就是有三种情况，所以dp[4] = 3 * (dp[3] + dp[2])。

那么递推公式也就出来了：

dp[i] = (i - 1) * (dp[i - 1] + dp[i - 2])

有了递推公式，代码就不难写了

https://en.wikipedia.org/wiki/Derangement#Counting_derangements

Suppose that there are n people who are numbered 1, 2, ..., n. Let there be n hats also numbered 1, 2, ..., n. We have to find the number of ways in which no one gets the hat having same number as their number. Let us assume that the first person takes hat i. There are n − 1 ways for the first person to make such a choice. There are now two possibilities, depending on whether or not person i takes hat 1 in return:

Person i does not take the hat 1. This case is equivalent to solving the problem with n − 1 persons and n − 1 hats: each of the remaining n − 1 people has precisely 1 forbidden choice from among the remaining n − 1 hats (i's forbidden choice is hat 1).
Person i takes the hat 1. Now the problem reduces to n − 2 persons and n − 2 hats.

From this, the following relation is derived:

!n=(n-1)(!(n-1)+!(n-2)).\,

where !n, known as the subfactorial, represents the number of derangements, with the starting values !0 = 1 and !1 = 0.

https://discuss.leetcode.com/topic/94442/java-5-lines-o-1-space-solution

For ith element, we have switch it with one of the previous numbers 1,2,...,i-1, and for each picked number j, for the positions left except the one take by i, j can take anyone of them. So there are dp[i - 2] permutation if j can take the original position of i, and dp[i - 1] permutations if j can not take the original position of i.

https://discuss.leetcode.com/topic/94421/java-solution-with-explanation-by-using-staggered-formula

http://blog.csdn.net/zjucor/article/details/74094495

public int findDerangement(int n) {
if(n == 1) return 0;
if(n == 2) return 1;
if(n == 3) return 2;
int[] dp = new int[1+n];
dp[2] = 1;
dp[3] = 2;
for(int i=4; i<=n; i++) {
long t = ((long)dp[i-1] + dp[i-2])*(i-1);
dp[i] = (int) (t % (1e9+7));
}
return (int) (dp[n] % (10e9+7));
}

X.
下面这种解法精简了空间，因为当前值只跟前两个值有关系，所以没必要保留整个数组，只用两个变量来记录前两个值，并每次更新一下就好了
https://discuss.leetcode.com/topic/94421/java-solution-with-explanation-by-using-staggered-formula

 public int findDerangement(int n) {
        long dn2 = 0, dn1 = 1;
        long res = n==1 ? 0 : 1; 
        for (int i = 3; i <= n; i++){
            res = ((i-1) * (dn1+dn2))%1000000007;
            dn2 = dn1;
            dn1 = res;           
        }
        return (int) res;
    }

下面这种方法是对之前的递推公式进行了推导变形，使其只跟前一个数有关，具体的推导步骤是这样的：

我们假设 e[i] = dp[i] - i * dp[i - 1]

递推公式为: dp[i] = (i - 1) * (dp[i - 1] + dp[i - 2])

将递推公式带入假设，得到：

e[i] = -dp[i - 1] + (n - 1) * dp[i - 2] = -e[i - 1]

从而得到 e[i] = (-1)^n

那么带回假设公式，可得: dp[i] = i * dp[i - 1] + (-1)^n

根据这个新的递推公式，可以写出代码如下：

    int findDerangement(int n) {
        long long res = 1;
        for (int i = 1; i <= n; ++i) {
            res = (i * res + (i % 2 == 0 ? 1 : -1)) % 1000000007; 
        }
        return res;
    }

解法II 公式

d(n) = sigma( n! * (-1)^i / i! ) i∈[0, n]

    def findDerangement(self, n):
        """
        :type n: int
        :rtype: int
        """
        MOD = 10**9 + 7
        mul, sig = 1, (-1) ** n
        ans = 0
        for x in range(n, -1, -1):
            ans = (ans + mul * sig) % MOD
            mul = (mul * x) % MOD
            sig *= -1
        return ans % MOD

1
2
3
4
5
6
7
8
9
10
11
12
13
14

https://www.geeksforgeeks.org/count-derangements-permutation-such-that-no-element-appears-in-its-original-position/

Let countDer(n) be count of derangements for n elements. Below is recursive relation for it.

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

How does above recursive relation work?
There are n – 1 ways for element 0 (this explains multiplication with n – 1).

Let 0 be placed at index i. There are now two possibilities, depending on whether or not element i is placed at 0 in return.

i is placed at 0: This case is equivalent to solving the problem for n-2 elements as two elements have just swapped their positions.
i is not placed at 0: This case is equivalent to solving the problem for n-1 elements as now there are n-1 elements, n-1 positions and every element has n-2 choices

LeetCode 634 - Find the Derangement of An Array

Labels

Popular Posts