大家好，我是吴师兄。
提前批开始啦！
早点练习，准备好秋招吧。
今天分享的是
蒙特卡洛专题
，拿下它！！！
蒙特卡洛模拟算法
蒙特卡洛模拟（Monte Carlo Simulation）是一种利用随机采样和统计分析来解决复杂问题的数值计算方法。
它得名于摩纳哥的蒙特卡洛赌场，因为这种方法
依赖于大量的随机试验
，类似于赌博中的随机性。
已知一个单位圆的半径是1，算出圆的面积就是
π
一个经典的蒙特卡洛模拟例子是估算圆周率
π
：
-
-
计算落在单位圆内的点的比例。由于圆的面积为
πr²
（半径为
0.5
，面积为
π/4
），正方形的面积为
1
，所以圆内点数与总点数之比接近于
π/4
。
-
import random
def estimate_pi(num_samples):
inside_circle = 0
for _ in range(num_samples):
x = random.uniform(0, 1)
y = random.uniform(0, 1)
if x**2 + y**2 <= 1:
inside_circle += 1
return (inside_circle / num_samples) * 4
num_samples = 1000000
pi_estimate = estimate_pi(num_samples)
print(f"Estimated Pi: {pi_estimate}")
基于这个理论基础来练习一道算法题。
题目描述与示例
题目描述
m
个学生排成一排，学生编号分别是
1
到
m
，
m
为
3
的整倍数。
老师随机抽签决定将所有学生分成
n
个
3
人的小组，
m=3*n
为了便于同组学生交流，老师决定将小组成员安排到一起，也就是同组成员彼此相连，同组任意两个成员之间无其它组的成员。
因此老师决定调整队伍，老师每次可以调整任何一名学生到队伍的任意位置，计为调整了一次，请计算最少调整多少次可以达到目标。
注意：对于小组之间没有顺序要求，同组学生之间没有顺序要求
输入描述
两行字符串，空格分隔表示不同的学生编号。
第一行是学生目前排队情况，第二行是随机抽签分组情况，从左开始每
3
个元素为一组
n
为学生的数量，
m
的范围为
[3，900]
，
m
一定为
3
的整数倍。第一行和第二行的元素个数一定相同。
输出描述
老师调整学生达到同组彼此相连的最小次数
备注
同组相连: 同组任意两个成员之间无其它组的成员 ，比如有两个小组
[4 5 6]
、
[1 2 3]
，以下结果都满足要求
1 2 3 4 5 6
1 3 2 4 5 6
2 3 1 5 6 4
5 6 4 1 2 3
以下结果不满足要求
1 2 4 3 5 6`，`4`与`5`之间存在其它组的成员`3
示例一
输入
7 9 8 5 6 4 2 1 3
7 8 9 4 2 1 3 5 6
输出
1
说明
学生目前排队情况：
7 9 8 5 6 4 2 1 3
学生分组情况：
[7 8 9]
、
[4 2 1]
、
[3 5 6]
将
3
调整到
4
之前，队列调整为
7 9 8 5 6 3 4 2 1
那么三个小组成员均彼此相连
[7 9 8]
、
[5 6 3]
、
[4 2 1]
输出：
1
示例二
输入
1 4 7 2 5 8 3 6 9
1 2 3 4 5 6 7 8 9
输出
4
说明
第一次移动：1 4 2 5 8 3 6 7 9
第二次移动：1 4 2 5 3 6 7 8 9
第三次移动：1 2 5 3 4 6 7 8 9
第四次移动：1 2 3 4 5 6 7 8 9
解题思路
本题直接考虑贪心算法来解决会比较麻烦，没办法直接从局部最优推到全局最优。
数组预处理
设未排好队的数组为
nums1
，分组结果为
nums2
。
同学人数
m = len(nums1) = len(nums2)
，组数
n = m // 3
为了方便表示分组，我们可以把在
nums2
中每隔
3
个属于同一组的同学，用
组号
进行标记。
以示例一为例，我们希望
7 9 8 5 6 4 2 1 3
7 8 9 4 2 1 3 5 6
能够用
0 0 0 2 2 1 1 1 2
0 0 0 1 1 1 2 2 2
进行重新标记。
那么我们只需要让原
nums1
中应该在同一组号中的元素，通过调整顺序而全部相邻即可。
我们可以使用哈希表
dic
进行从
nums2
中的元素到组号
i
的映射。
对于组号
i
而言，在
nums2
中的属于同一个组中的元素索引应该为
i*3+j
，其中
j
的取值是
0
、
1
、
2
。
进而构建出
nums1
中元素用组号标记的数组
nums
。
nums1 = list(map(int, input().split()))
nums2 = list(map(int, input().split()))
m = len(nums1)
n = m // 3
dic = dict()
for i in range(n):
for j in range(3):
dic[nums2[i*3+j]] = i
nums = [dic[num] for num in nums1]
检查某个组是否已经排好队
在后面的模拟过程中，我们就可以通过构建一个函数
check_group(nums, idx)
，来判断第
idx
个组是否已经是排好队的。
对于第
idx
个组而言，如果
nums[idx*3]
、
nums[idx*3+1]
和
nums[idx*3+2]
相等，则意味着第
idx
个组已经的排好队的了。
def check_group(nums, idx):
return nums[idx*3] == nums[idx*3+1] == nums[idx*3+2]
检查所有组是否已经排好队
结合
check_group(nums, idx)
函数，我们可以构建函数
check_all(nums, n)
来检查是否所有的组已经排好队。
def check_all(nums, n):
return all(check_group(nums, idx) for idx in range(n))
蒙特卡洛模拟框架
考虑蒙特卡洛模拟，我们对原数组
nums
的排队过程进行
T
次的随机模拟。
每一次模拟都从初始状态开始，挑选出最少的能够使得原数组
nums
排好队的那一次调整次数作为答案。
故构建函数
mc_simulation(nums, n)
的代码框架为
def mc_simulation(nums, n):
# 蒙特卡洛模拟的总的次数，该数值可以自行进行调整
T = 10000
# 初始化最多的调整次数，该数值可以自行进行调整
ans = 10
# T次蒙特卡洛模拟
for _ in range(T):
pass
return ans
单次蒙特卡洛模拟
整体思路
在得到预处理的
nums
之后，我们需要对
nums_new = nums[:]
，即
nums
的一份拷贝进行单次蒙特卡洛模拟。
模拟
单次调整
位置的过程
-
在
nums_new
中挑选一个下标
i
，
i
范围是
randint(0, m-1)
-
获得
num = nums_new[i]
，删除这个元素
num
-
在
nums_new
中挑选一个下标
j
，
j
的范围的
randint(0, m-2)
-
把删除的元素
num
插入到
nums_new
中下标
j
的位置
单次蒙特卡洛模拟过程需要进行多次的调整位置。
单次蒙特卡洛模拟会计算得到一个对应的调整次数，对多次蒙特卡洛模拟计算得到的调整次数
取最小值
，就是得到的全局的最少调整次数，将其作为答案输出。
编号挑选优化
当我们进行下标
i
和
j
的挑选的时候，注意到如果
i
和
j
当前已经位于同一组中，即存在
i // 3 == j // 3
成立，那么本次调整是没有意义的。
因为这样的调整只会无端增加调整次数，但并不能带来实质上的效果。
我们要尽量避免这种情况的出现，因此可以直接挑选两个不同编号的组，再从从这两个组中分别随机挑选出一个编号。其代码为
group_i = randint(0, n-1)
i = group_i * 3 + randint(0, 2)
group_j = randint(0, n-1)
while(group_j == group_i):
group_j = randint(0, n-1)
j = group_j * 3 + randint(0, 2)
组号区间优化
另外，如果位于边界的组（最左边的和最右边的）已经是分好组的结果，那么不应该选择这些组。譬如
0 0 0 3 2 2 3 2 3 1 1 1
那么边界处的
0 0 0
和
1 1 1
中的元素不应该被挑选，而应该挑选位于中间位置，尚未分好组的那些元素。
故我们可以设置两个变量
start_idx
和
end_idx
，来表示挑选的组
group_i
和
group_j
的区间。
初始化
start_idx, end_idx = 0, n-1
为尚未排好队的组的区间。
每一次随机调整之前，我们都需要更新
start_idx, end_idx
的值。即
def update_group_interval(nums, start_group, end_group):
i, j = start_group, end_group
while check_group(nums, i):
i += 1
while check_group(nums, j):
j -= 1
return i, j
而随机挑选
group_i
和
group_j
，进而挑选出具体元素下标
i
和
j
的代码也随之发生调整。
需要把
randint(0, n-1)
修改为
randint(start_group, end_group)
。
group_i = randint(start_idx, end_idx)
i = group_i * 3 + randint(0, 2)
group_j = randint(start_idx, end_idx)
while(group_j == group_i):
group_j = randint(start_idx, end_idx)
j = group_j * 3 + randint(0, 2)
同样地，检查所有组是否已经排好队的函数
check_all(nums, n)
也可以相应地进行调整，只考虑组号落在区间
[start_idx, end_idx]
内的那些组。
def check_all(nums, start_idx, end_idx):
return all(check_group(nums, idx) for idx in range(start_idx, end_idx+1))
单次蒙特卡洛模拟的代码
综合以上讨论，我们构建出单次蒙特卡洛模拟的过程如下
-
-
-
