求解无两个相同元素相邻的排列数问题（示例数组：[3,4,1,5,6,1,3]）

核心思路 #

采用容斥原理统计满足约束的排列数：先计算无约束全排列总数，扣除「两个3相邻」「两个1相邻」的不合规排列，再补回两类不合规情况同时发生的重复扣除部分。

元素分布说明 #

给定数组共7个元素：3重复2次、1重复2次，4/5/6各出现1次。

分步计算 #

• 无约束全排列总数计算
  含重复元素的全排列公式为：总元素数阶乘 / 各重复元素阶乘的乘积
  代入得：7! / (2! * 2!) = 5040 / 4 = 1260
• 定义不合规事件集合
  令A为「两个3相邻」的排列集合，B为「两个1相邻」的排列集合，根据容斥原理，合规排列数 = 总排列数 - |A| - |B| + |A∩B|
• 计算单个不合规事件的排列数
  • 计算|A|（两个3相邻）：将两个3绑定为1个整体，此时总元素数为6个，仅剩余1重复2次，排列数为6! / 2! = 720 / 2 = 360
  • 计算|B|（两个1相邻）：将两个1绑定为1个整体，此时总元素数为6个，仅剩余3重复2次，排列数为6! / 2! = 720 / 2 = 360
• 计算|A∩B|（两类相邻同时发生）
  同时将两个3绑定为1个整体、两个1绑定为1个整体，此时总元素数为5个且无重复，排列数为5! = 120

最终结果 #

代入公式计算得合规排列数：1260 - 360 - 360 + 120 = 660

内容的提问来源于stack exchange，提问作者Khatami Onik