N个自然数(从1到N), 全排列就有 N! 种方法 (第1位有N种可能, 第2位有N-1种可能… 第N位有1种可能, 这样乘起来就是 N阶乘). 如果规定 数字1不能在第1位, 数字2不能在第2位.. 数字N不能在第N位的话, 所有可能的排列数就是 错位排列, 英文可以用 derangement 来表示.
动态规化
我们可以用 动态规化 (Dynamic Programming) 来解决这个问题. 我们可以用 F(n) 来表示 n 个数的错位排列总数. 那么 我们在放第 n 个数的时候, 很显然可以选择的位置有 n-1 种 (不能放在第 n 位). 假设放在 第 K 位, 那么 数字 K 就有两种情况, 如果放在 第 N 位, 那么剩下的排列就是 F(n-2) 种可能. 如果不放在第 N 位, 那么剩下 N-1个数的情况就是 F(n-1). 这样得到公式:
递归终止条件: F(1) = 0, F(2) = 1.
R语言实现
有了递推公式之后就很容易写代码了, 在R语言实现如下:
f = function(n) {
if (n == 1) {
0
} else if (n == 2) {
1
} else {
(n-1) * (f(n - 1) + f(n - 2))
}
}
前面几项的值为:
> n=1:10 > Map(f, n) [[1]] [1] 0 [[2]] [1] 1 [[3]] [1] 2 [[4]] [1] 9 [[5]] [1] 44 [[6]] [1] 265 [[7]] [1] 1854 [[8]] [1] 14833 [[9]] [1] 133496 [[10]] [1] 1334961
这里用了 Map 函数把一组向量通过 函数 映射到另一组向量. 不过毕竟是递归, 在计算很大的N的时候就会重复的调用递归函数, 一是速度慢效率低, 二是很容易造成 堆叠溢出 (Stack Overflow). 我们可以把结果通过迭代得出.
f = function(n) {
a = 0
b = 1
if (n == 1) {
a
} else if (n == 2) {
b
} else {
for (i in 3:n) {
c = (i-1) * (a + b)
a = b
b = c
}
b
}
}
迭代算法的明显好处是把中间结果给保存起来则不需要重复的计算.
通项公式
F(n) 可以推导出通项公式为:
具体的推导可以看这里.
英文: Derangement Permutation Implementation using R Programming
R语言教程
- R 语言教程 – 蒙特卡罗
- R 语言教程 – Sigmoid
- R 语言教程 – 错位排列
- R 语言教程 – 连接STEEMSQL 数据库
- R 语言教程 – STEEMIT 微信群有多少钱?
- R 语言教程 – STEEMIT 大鲸啥时候点赞的?
- R 语言教程 – 通过 RStudio 来快速连接SteemSQL
强烈推荐
- 英国代购-畅购英伦
- TopCashBack 返现 (英国购物必备, 积少成多, 我2年来一共得了3000多英镑)
- Quidco 返现 (也是很不错的英国返现网站, 返现率高)
- 注册就送10美元, 免费使用2个月的 DigitalOcean 云主机(性价比超高, 每月只需5美元)
- 注册就送10美元, 免费使用4个月的 Vultr 云主机(性价比超高, 每月只需2.5美元)
- 注册就送10美元, 免费使用2个月的 阿里 云主机(性价比超高, 每月只需4.5美元)
- 注册就送20美元, 免费使用4个月的 Linode 云主机(性价比超高, 每月只需5美元) (折扣码: PodCastInit2022)
- PlusNet 英国光纤(超快, 超划算! 用户名 doctorlai)
- 刷了美国运通信用卡一年得到的积分 换了 485英镑
- 注册就送50英镑 – 英国最便宜最划算的电气提供商
- 能把比特币莱特币变现的银行卡! 不需要手续费就可以把虚拟货币法币兑换
微信公众号: 小赖子的英国生活和资讯 JustYYUK