错位重排怎么计算-错位重排.如何计算

错位重排是一种常见的组合数学问题，它触及到将一组元素重新排列成不同的顺序。计算错位重排的方法主要有以下几种：

1、 基于阶乘的解法：这类方法首先求出所有可能的排列方式，然后对每种排列方式进行计数，最后再除以总的排列数量。这个方法的时间复杂度是O(n!)，对大型的数据集来讲可能会非常耗时。

2、 基于动态计划的解法：这类方法通过建立一个二维数组来存储每一个元素的所有排列情况，然后通过比较两个相邻的排列来更新当前状态，最后返回结果。这个方法的时间复杂度是O(n!)，但是由于使用了空间复杂度较低的一维数组，所以相比于基于阶乘的解法效力更高。

3、 基于哈希表的解法：这类方法利用哈希表来存储已出现过的排列方式，如果发现有重复的排列，就跳过这个排列，从而大大减少了需要计算的排列数量。这个方法的时间复杂度是O(n^2)，但是对小型的数据集来讲效力很高。

4、 基于深度优先搜索的解法：这类方法通过递归地进行排列，每次递归都将数组的第一个元素替换为下一个未被使用的元素，并且检查当前排列是不是已被用过，如果没有，就继续递归；如果有，就放弃当前递归并尝试下一个未被使用的元素。这个方法的时间复杂度是O(n^2)，但是对小型的数据集来讲效力也很高。

错位重排的公式是什么？

D（1）=0

D（2）=1

D（3）=2

D（4）=9

D（5）=44

D（6）=265

D（7）=1854

错位重排的结论：

如果有n个对象，则错位重排的情况数用Dn表示，需要大家了解的是：

D2=1，D3=2，D4=9，D5=44。

错位重排的题干特征还是非常明显的，比如四个大厨烧了四道菜，每个大厨都不吃自己菜的方式有多少种，这就是3个元素的错位重排，注意不是6个元素的错位重排；

再比如有4个信封对应着四封信，每封信不装自己信封的方式有多少种就是四个元素的错位重排；有5对夫妻去跳舞，相互交换舞伴，舞伴不是自己配偶的方式有多少种，就是5个元素的错位重排。

扩展资料

：

表述为：编号是1、2、n的n封信，装入编号为1、2、n的n个信封，要求每封信和信封的编号不同，装法：

对这类问题有个固定的递推公式，记n封信的错位重排数为Dn，则D1=0，D2=1，

Dn=（n-1）（Dn-2+Dn-1） 此处n-2、n-1为下标。

n>2

只需记住Dn的前几项：D1=0，D2=1，D3=2，D4=9，D5=44。我们只需要记住结论，进行计算就可以。

参考资料来源:百度百科-错位重排