锐客网

  1. 首页 > it技术 > >

带重复的全排列问题

明白带重复的全排列首先要明白不带重复的全排列（不带重复的全排列链接）
在不带重复的全排列中说到在排列1，2，3，4插入5有5种方式，会生成5种新的排列。
如果我们在1，1，2，3中插如4也有五种方式，
（1）4，1，1，2，3
（2）1，4，1，2，3
（3）1，1，4，2，3
（4）1，1，2，4，3
（5）1，1，2，3，4
生成了五种排列
但如果在1，2，3，4中插如1
（1）1，1，2，3，4
（2）1，1，2，3，4
（3）1，2，1，3，4
（4）1，2，3，1，4
（5）1，2，3，4，1
虽然有五种插入方式，但是发现生成的第一种排列和第二种排列是相同的，只生成了四种排列
现在我们定义f（i）为第一位到第i-1位中有f（i）个元素与第i位的元素相同那么一段数字所生成的全排列种数为∏（i-f（i））。
如1，1，2，2，3，3的全排列，（1-0）*（2-1）*（3-0）*（4-1）*（5-0）*（6-1）=175
代码分析：
以1，1，2，3为例，建一颗搜索树（不明白的可以点这里）
带重复的全排列问题
文章图片

这样做肯定会产生重复的排列，现在要做的就是找到重复的元素并去掉。首先看那些排列时重复的。
带重复的全排列问题
文章图片

黄色标注，代表这些排列都是重复的，不难发现，重复的排列都是同根节点的子节点出现重复时，以这个子节点为跟 的子树就会产生重复。所以保证每一行每种元素不出现两次（同一根节点的时候）
代码实现：

#include #include #include #include #include using namespace std; int n; void print(const int a[]){ for(int i=0; i

【带重复的全排列问题】转载于:https://www.cnblogs.com/wz-archer/p/10591415.html

    推荐阅读


    上一篇：全国大学API接口分享

    下一篇：linux|linux shell 之if-------用if做判断