有重复元素的全排列问题

有重复元素的全排列问题
只是在没有重复的全排列问题上去除重复的部分即可

思想方法：递归
例如
s[4]=aacc

1. s[0] 作为head 全排列剩下的三个
2. s[1] 与s[0] 交换 由于s[1]==s[0] 不交换
   如果交换，那么全排列剩下的三个，剩下的三个依然是acc 与情况一相同，我们不能出现重复的，所以不能交换
3. s[2] 与s[0] 交换，由于前面并没有出现过c所以可以交换
4. s[3] 与s[0] 交换，由于s[2]==s[3] 不交换
   如果交换，那么和情况3重复，解释与2相同
5. 交换过后的字符串就可以根据递归的方式递归计算剩下 的三个元素的全排列，两个元素的全排列，直到只剩一个元素的全排列，就说明已经没有元素了，就可以输出了

如何去掉重复的元素
判断需要交换的元素是否在前面出现过，如果出现过就返回false，不能交换，如果没有出现过就可以交换
可以看下图，从begin开始到p-1，因为我们可以发现已经有一个c了，如果交换，就会出现重复的现象，所以在这里beigin和p不能交换

下面的代码是一个没有输出的解决重复元素全排列的问题

//判断是否可以交换
bool isSwap(string str,int begin,int p)
{
	//是否可以交换，就是看是交换的元素和前面的那些元素有没有重复
	for(int i=begin;i<p;i++)
	{
		if(str[p]==str[i])
		return false;
	}
	return true;
}


void Per(string str,int begin,int end)   //从begin开始到end结尾的str的带有重复元素的全排列
{
//位置1
	for(int i=begin;i<=end;i++)
	{
		/*如果begin可以和i交换就交换，不可以那么就继续循环*/
		if(isSwap(str,begin,i))
		{
			swap(str[begin],s[i]);
			//确定好了头元素，那么就可以排列剩下的了
			//位置2
			per(str,begin+1,end);
			//位置3
			swap(str[begin],s[i]);
			//位置4
		}
	}
}

重复的全排列就是比没有重复元素的多了个比较

如果需要输出，在什么情况下进行输出呢？
因为如果交换一次，那么就会产生一个新的序列，所以我尝试了在位置2进行元素的输出，结果是错误的
位置2虽然进行了一次交换，但是这个序列的交换并没有完成一次的遍历，只有完成一次的遍历才能算作是一次排列
就例如对aacc进行排列，第一次一定是s[0]与s[0]进行交换，这样才能完成后面s[1]-s[3]的全排列，如果在这个时候进行输出，将相当于s[1]-s[3]没有进行排列就会输出一次aacc，接下来就会进行s[1]与s[1]的交换，又会输出aacc，所以这个地方是不正确的

那么在全排列之后进行输出总可以吧，这也是不可以的，这个是在每次全排列之后进行输出，也就是当aacc中s[4]与s[3]进行返回后会输出aacc，然后又会在s[3]-s[3]进行返回后，输出aacc依次类推，所以是不正确的

位置4是第二次交换，会回到原来的位置也不正确

位置1，可以判断当一次排列排到最后也就是begin==end的时候，进行输出

牛客网
有重复项数字的全排列

vector<vector<int> > answer;
    set<vector<int> > ans;
    
    bool iSwap(vector<int> num, int begin,int position)   //就是看他卡面有没有相同的
    {
        
        for(int i=begin;i<position;i++)
        {
            if(num[i]==num[position])
                return false;
        }
        return true;       
    }
    
    void bfs(vector<int> &num, int begin, int endi)
    {
        
         if(begin==endi)
         { ans.insert(num);
          return;
         }
       for(int i=begin;i<=endi;i++)
       {
           if(iSwap(num,begin,i))
           {
               //把begin和i进行交换
               swap(num[begin],num[i]);
               //对剩下的元素进行排序
               bfs(num,begin+1,endi);
               swap(num[begin],num[i]);
           }
       }
    }
    
    vector<vector<int> > permuteUnique(vector<int> &num) {
        sort(num.begin(),num.end());
        bfs(num,0,num.size()-1);
        for(auto iter=ans.begin();iter!=ans.end();iter++)
        {
            answer.push_back(*iter);
        }
        return answer;
    }

如何进行升序排列输出
这道题有一个特别的要求，需要按升序进行排列输出，这里使用set进行存储，set本身就是按照升序进行排列的

递归排序练习
字符串的排序