时间戳

首页 > 解决方案 > 找到没有相邻元素相同的系列的所有排列？

algorithm - 找到没有相邻元素相同的系列的所有排列？

问题描述

我们得到一个数字列表，其中每个数字要么单独出现，要么重复出现。现在的任务是找到排列的总数，我们可以在其中排列这个数字列表，以便列表上没有两个相邻的元素是相同的。关键是要有效地做到这一点，这就是为什么我正在寻找一种使用动态编程的算法。长度可以非常大，最多 5000 个元素，这就是为什么生成所有案例并检查案例是否正确不是一个好主意的原因。我们只想要总排列的数量，而不是列表的实际排列。

示例案例：[1,1,2,2]

输出：2

[1,2,1,2] 和 [2,1,2,1]

示例案例：[1,2,3,3]

输出：6

[3,1,2,3], [3,2,1,3], [1,3,2,3],[2,3,1,3],[3,1,3,2] 和[3,2,3,1]

示例案例：[1,1,2,2,3,3]

输出：30

标签： algorithmoptimizationcombinationspermutationdynamic-programming

解决方案

这个问题可以用包含-排除原则来解决

如果单项s数为 ，双项对数为d，则总排列数为

A0 = (s + 2 * d)! / 2^d

现在我们必须减去一对相邻的排列数。有

P1 = (s+2*d-1)! / 2^(d-1)

每个加倍元素的这种排列，以及

A1 = d *(s+2*d-1)! / 2^(d-1)

所有加倍元素的这种排列

现在我们必须添加两对相邻的排列数。有

P2 = (s+2*d-2)! / 2^(d-2)

每对加倍元素的这种排列，以及

A2 = C(d,2) * (s+2*d-2)! / 2^(d-2)

所有可能的加倍元素对的排列（其中C(n,k)是二项式系数，组合数）。

继续这个过程，改变符号，所以

A(k){k=1..d} = (-1)^k * C(d, k) * (s+2*d-k)! / 2^(d-k)

并对这个序列求和以获得最终结果

对于您的最后一个示例（s=0,d=3）：

 6!/2^3 - 3*5!/2^2 + 3*4!/2 - 3! = 
 720/8  - 360/4 +    72/2   - 6  = 
  90    - 90     +   36     - 6  = 30

推荐阅读