全排列 字典序全排列

全排列递归的方法参考 leetcode 47

字典序算法：升序

参考https://www.jianshu.com/p/58ae30cf6bca

实现：

判断了是否相等

计算全排列的数量方法为 n!/ (m!*p!*...)   m，p为重复的数字的重复量

参考 https://blog.csdn.net/sinat_36215255/article/details/78197129

#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;
vector<int>nums;

void Permutation(int len,vector<int>nums)
    {
        int j, k;
        int flag=1;  //start 0s
        while (true)
        {
        for(int i=0;i<len;i++){
                if(nums[i]==0&&flag)
                        continue;
                else{
                        flag=0;
                        printf("%d",nums[i]);
                }
        }
        printf(" ");
        flag=1;

        for (j = len - 2; j >= 0 && nums[j] >= nums[j + 1]; j--);//注意此处 j >= 0 判断条件在前,加个等号即可  

        if (j < 0) return;//结束  

        for (k = len - 1; k > j&&nums[k] <= nums[j]; k--);//加个等号即可  

        swap(nums[k], nums[j]);

        for (int l = j + 1, r = len - 1; l < r; l++, r--)
                swap(nums[l], nums[r]);
        }
    }

int calc(int len){
        int summ=1;

        for(int i=1;i<=len;i++)
                summ*=i;
        return summ;
}
int main()
    {

        int n;
        while(cin>>n)
        nums.push_back(n);
        sort(nums.begin(),nums.end());
        int len=nums.size();

        //all 0
        int flag=0;
        for(int i=0;i<len;i++)
                if(nums[i]!=0){
                        flag==1;
                        break;
                }
        if(flag)
        {
                cout<<"1 0"<<endl;
                return 0;
        }

        vector<int>dup;
        int cnt=1;
        int bef=nums[0];
        for(int i=1;i<len;i++)
                if(bef==nums[i]){
                        cnt++;
                        continue;
                }
                else
                {
                        dup.push_back(cnt);
                        cnt=1;
                        bef=nums[i];
                }

        //dup.push_back(cnt);   
        vector<int>::iterator iter=dup.begin();
        int divide=1;
        for(iter;iter!=dup.end();iter++)
                divide*=calc(*iter);
        int summ=calc(len)/divide;
        printf("%d ",summ);

        Permutation(len,nums);
        system("pause");
        return 0;
    }