备案控制台
探索云世界
开发者社区 人工智能 文章 正文

全排列总结

2016-04-28 1630
版权
版权声明：
本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《 阿里云开发者社区用户服务协议》和 《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写 侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。
简介：

接触全排列已经好长时间了，一直没有抽空总结一下全排列的相关问题，下面来说一下！

v排列

　　一般地，从n个不同元素中取出m（m≤n）个元素，按照一定的顺序排成一列，叫做从n个元素中取出m个元素的一个排列(Arrangement)。特别地，当m=n时，这个排列被称作全排列(Permutation)。

v排列数公式：

                                
 
　　特别，当n==m时为全排列的公式！

v下一个全排列算法

　　lintcode链接：http://www.lintcode.com/zh-cn/problem/next-permutation/

v样例

　　左边是原始排列，右边是对应的下一个排列。

　　1,2,3 → 1,3,2

　　3,2,1 → 1,2,3

　　1,1,5 → 1,5,1

v下一个全排列算法——first

复制代码 
class Solution {
public:
    /**
     * @param nums: a vector of integers
     * @return: return nothing (void), do not return anything, modify nums in-place instead
     */
    void nextPermutation(vector<int> &nums) {//调用<algorithm>中的下一个排列算法以及排序算法
        if(!next_permutation(nums.begin(), nums.end()))
            sort(nums.begin(), nums.end(), less<int>());

}

}
复制代码

v下一个全排列算法——second

复制代码 
class Solution {
public:
    /**
     * @param nums: a vector of integers
     * @return: return nothing (void), do not return anything, modify nums in-place instead
     */
    void nextPermutation(vector<int> &nums) {
        int ld = -1;
        if(nums.size() < 1) return ;
        for(int i=nums.size()-2; i>=0; --i)//找到从右边开始第一个比它右边相邻小的数的位置
            if(nums[i] < nums[i+1]){
                ld = i;
                break;
            }
        if(ld != -1){//找到从右边开始，第一个比位置为ld所在数 大的数的位置
            int rd;
            for(int i=nums.size()-1; i>=0; --i)
                if(nums[ld] < nums[i]){
                    rd = i;
                    break;
                }
            swap(nums[ld], nums[rd]);
            //在交换之前，ld位置后面的已经是从大到小排好序的，已经没有下一个排列了
            sort(nums.begin()+ld+1, nums.end());//交换之后，将ld后面的数置为最小的排列，从小到大排序
        }
        
        if(ld == -1){
            sort(nums.begin(), nums.end());
        }
        
    }
};
复制代码

v下一个全排列算法——third

复制代码 
class Solution {
public:
    /**
     * @param nums: a vector of integers
     * @return: return nothing (void), do not return anything, modify nums in-place instead
     */
    void nextPermutation(vector<int> &nums) {        
        //挑战不使用额外的空间, 其实和方法二的思路是一样的
        int n = nums.size();
        for(int i=n-1; i>=0; --i)
            for(int j=n-1; j>i; --j)
                if(nums[i] < nums[j]){
                    swap(nums[i], nums[j]);
                    sort(nums.begin()+i+1, nums.end());
                    return ;
                }
        sort(nums.begin(), nums.end());
    }
};
复制代码

v下一个全排列的思想：

 

　　如上图所示，该全排列对应的下一个全排列是和绿色框里的数字以及红色框里的数字有关系的。显而易见的是红色框里的数列已经没有下一个排列了，因为已经是一个递减的序列了。为了得到下一个排列，我们将绿色框里的数字和红色框里右边起第一个比绿色框中数字大的数字交换位置(也就是4 和 5交换位置)。这样还不是下一个全排列，交换之后红色框内的序列为7 4 3 2 1 0， 将它变成递增序列 0 1 2 3 4 7，就得到了下一个全排列。

　　因为，一个全排列，末尾的一段区间肯定是递减的（如上图的红色框区间），如果这段区间一直延伸到首部，那么也就没有下一个全排列了，否则找到和这段区间最近的一个数字（上图中绿色框中的数字），然后经过上述的处理就可以得到下一个全排列了。

　　the second method 就是先找到绿色框数字的位置(ld)， 然后在寻找红色框中右边第一个比绿色框中数字大的数字的位置(rd);

　　the third method的意思就是从右边开始寻找第一对(i, j)，满足nums[i]<nums[j], 对应second method中(ld, rd)。该方法没有用到额外的存储空间。

v上一个全排列算法

　　注：算法思想和下一个全排列的思想正好相反，步骤一致！

　   lintcode链接:http://www.lintcode.com/zh-cn/problem/previous-permutation/

v样例

　　给出排列[1,3,2,3]，其上一个排列是[1,2,3,3]

　　给出排列[1,2,3,4]，其上一个排列是[4,3,2,1]

v上一个全排列算法——first

复制代码 
class Solution {
public:
    /**
     * @param nums: An array of integers
     * @return: An array of integers that's previous permuation
     */
    vector<int> previousPermuation(vector<int> &nums) {        //直接调用<algrotihm>中的算法prev_permutation()
         if(!prev_permutation(nums.begin(), nums.end()))
           sort(nums.begin(), nums.end(), greater<int>());
         return nums;          
    }
};
复制代码

v上一个全排列算法——second

复制代码 
class Solution {
public:
    /**
     * @param nums: An array of integers
     * @return: An array of integers that's previous permuation
     */
    vector<int> previousPermuation(vector<int> &nums) {      
        int ld = -1;
        if(nums.size() <= 1) return nums;
        for(int i=nums.size()-2; i>=0; --i)//找到从右边开始第一个比它右边相邻大的数的位置
            if(nums[i] > nums[i+1]){
                ld = i;
                break;
            }
        if(ld != -1){//找到从右边开始，第一个比位置为ld所在数 小的数的位置
            int rd;
            for(int i=nums.size()-1; i>=0; --i)
                if(nums[ld] > nums[i]){
                    rd = i;
                    break;
                }
            swap(nums[ld], nums[rd]);
            //在交换之前，ld位置后面的已经是从小到大排好序的，已经没有上一个排列了
            //交换之后，将ld后面的数置为最大的排列，从大到小排序
            sort(nums.begin()+ld+1, nums.end(), greater<int>());
        }
        
        if(ld == -1){
            sort(nums.begin(), nums.end(), greater<int>());
        }
        return nums;      
    }
};
复制代码

v上一个全排列算法——third

复制代码 
class Solution {
public:
    /**
     * @param nums: An array of integers
     * @return: An array of integers that's previous permuation
     */
    vector<int> previousPermuation(vector<int> &nums) {     
        int n = nums.size();
        for(int i=n-1; i>=0; --i)
            for(int j=n-1; j>i; --j)
                if(nums[i] > nums[j]){
                    swap(nums[i], nums[j]);
                    sort(nums.begin()+i+1, nums.end(), greater<int>());
                    return nums;
                }
        sort(nums.begin(), nums.end(), greater<int>());
        return nums;
    }
};
复制代码

v得到所有全排列算法

　　lintcode链接：http://www.lintcode.com/zh-cn/problem/permutations/

v全排列算法——first

　　注：非递归，由下一个全排列算法——third方法实现

复制代码 
class Solution {
public:
    /**
     * @param nums: A list of integers.
     * @return: A list of permutations.
     */
    vector<vector<int> > vv;

    vector<vector<int> > permute(vector<int> nums) {
        if(nums.size() == 0) return vv;
        sort(nums.begin(), nums.end());
        //方法1： 非递归实现
        int n = nums.size();
        bool flag = true;
        vv.push_back(nums);
        while(flag){
            flag = false;
            for(int i=n-1; i>=0; --i){
                for(int j=n-1; j>i; --j)
                    if(nums[i] < nums[j]){
                        swap(nums[i], nums[j]);
                        sort(nums.begin()+i+1, nums.end());
                        vv.push_back(nums);
                        flag = true;
                        break;
                    }
                if(flag) break;
            }
        }       
        return vv;
    }
};
复制代码

v全排列算法——second

复制代码 
class Solution {
public:
    /**
     * @param nums: A list of integers.
     * @return: A list of permutations.
     */
    vector<vector<int> > vv;

    vector<vector<int> > permute(vector<int> nums) {
        if(nums.size() == 0) return vv;
        sort(nums.begin(), nums.end());        
        //方法2：调用<algorithm>中的next_permutation()
        do{
            vv.push_back(nums);
        }while(next_permutation(nums.begin(), nums.end()));            
        return vv;
    }
};
复制代码

v全排列算法——third

　　注：递归思路：一共有nn个位置，然后每个位置枚举可能出现的数字（注意处理重复数字的情况）

复制代码 
class Solution {
public:
    /**
     * @param nums: A list of integers.
     * @return: A list of permutations.
     */
    vector<vector<int> > vv;    
    ///
    int nn;//没有 unique 之前的数组的大小
    map<int, int> mp;    
    void dfs_1(int cur, vector<int> &v, vector<int> nums){
        if(cur >= nn){
            vv.push_back(v);
            return;
        }
        for(int i=0; i<nums.size(); ++i)
            if(mp[nums[i]]){//如果nums[i]这个数字没有枚举完
                --mp[nums[i]];
                v.push_back(nums[i]);
                dfs_1(cur+1, v, nums);
                v.pop_back();
                ++mp[nums[i]];
            }
    }    
    ////        
    vector<vector<int> > permute(vector<int> nums) {
        if(nums.size() == 0) return vv;
        sort(nums.begin(), nums.end());        
        //方法3：递归
        for(int i=0; i<nums.size(); ++i)//统计每个重复元素的个数
            ++mp[nums[i]];
        nn = nums.size();
        unique(nums.begin(), nums.end());//对数组进行去重
        vector<int> v;
        dfs_1(0, v, nums);       
        return vv;
    }
};
复制代码

v全排列算法——forth

　　注：递归思路：每一个数，不断的和后面的数交换位置，每交换一次就会得到一个新的排列

复制代码 
class Solution {
public:
    /**
     * @param nums: A list of integers.
     * @return: A list of permutations.
     */
    vector<vector<int> > vv;
    void dfs_2(int ld, int rd, vector<int> nums){
        if(ld == rd){
            vv.push_back(nums);
            return ;
        }
        for(int i=ld; i<=rd; ++i){
            swap(nums[ld], nums[i]);
            dfs_2(ld+1, rd, nums);
            swap(nums[ld], nums[i]);
        }
    }
      
    vector<vector<int> > permute(vector<int> nums) {
        if(nums.size() == 0) return vv;
        sort(nums.begin(), nums.end());        
        dfs_2(0, nums.size()-1, nums);
        return vv;
    }
};
复制代码

v排列序号(按字典序排序属于第几个全排列)

　　注：不含重复数字的排列！

　　lintcode链接：http://www.lintcode.com/zh-cn/problem/permutation-index/

v样例

　　例如，排列[1,4,2]是第2个全排列。

v排列序号算法

　　算法思想请参考：http://www.cnblogs.com/hujunzheng/p/5020211.html

复制代码 
class Solution {
public:
    /**
     * @param A an integer array
     * @return a long integer
     */
    long long permutationIndex(vector<int>& A) {//一个一个来肯定会超时// vector<int> permu(A.begin(), A.end());
        // sort(permu.begin(), permu.end());
        // int cnt = 0;
        // do{
        //     int i;
        //     for(i=0; i<A.size(); ++i)
        //         if(A[i]!=permu[i])
        //             break;
        //     ++cnt;
        //     if(i>=A.size()) break;
        // }while(next_permutation(permu.begin(), permu.end()));
        // return cnt;
                
        vector<int> a;
        int len = A.size();
        int cnt[len];
        cnt[len-1] = 0;
        a.push_back(A[len-1]);
        for(int i=len-2; i>=0; --i){//统计每个数后面有多少个比它小的数的个数
            vector<int>::iterator it = lower_bound(a.begin(), a.end(), A[i]);
            cnt[i] = it-a.begin();
            a.insert(it, A[i]);
        }
        
        long long ans=1, fac=1, c=1;
        for(int i=len-2; i>=0; --i)
            ans += (fac*=c++)*cnt[i];
        return ans;
    }
};
复制代码

v第k个排列

　　注：给定 n 和 k，求123..n组成的排列中的第 k 个排列。

　　lintcode链接：http://www.lintcode.com/zh-cn/problem/permutation-sequence/

v样例

　　对于 n = 3, 所有的排列是：123, 132, 213, 231, 312, 321.

　　如果 k = 4, 第4个排列为，231.

v康托展开的公式 ：

　　X=an*(n-1)!+an-1*(n-2)!+...+ai*(i-1)!+...+a2*1!+a1*0!，ai为整数，并且0<=ai<i(1<=i<=n)

　　适用范围：没有重复元素的全排列

v例题：

　　找出第16个n = 5的序列（12345）。康托展开只要O(n)就行 ，下面来说说具体怎么做:

　　根据第一行的那个全排列公式，15 / 4! = 0 …15  =>  有0个数比它小的数是1，所以第一位是1

　　拿走刚才的余数15，用15 / 3! = 2 …3   =>  剩下的数里有两个数比它小的是4（1已经没了），所以第二位是4

　　拿走余数3， 用 3 / 2! = 1 …1   =>  剩下的数里有一个数比它小的是3，所以第三位是3

　　拿走余数1， 用 1/  1! = 1 …0    =>  剩下的数里有一个数比它小的是 5（只剩2和5了），所以第四位是5

　　所以排列是 1,4,3,5,2

v第k个排列算法

 

复制代码 
class Solution {
public:
    /**
      * @param n: n
      * @param k: the kth permutation
      * @return: return the k-th permutation
      */
     
    string getPermutation(int n, int k) {
        if(n==1) return "1";
        int f[n+1];
        bool use[n+1];
        f[1] = 0;
        f[2] = 1;
        memset(use, false, sizeof(use));
        for(int i=3; i<=n; ++i)
            f[i] = f[i-1]*(i-1);
        string ans = "";
        --k;//要计算的排列之前有多少个排列
        for(int i=n; i>=2; --i){
            int cnt = 0;
            int c = k/f[i];//假设该排列的这位数是x，c就是比x小的数（之前没有用过）的个数
            k%=f[i];
            for(int j=1; j<=n; ++j){//寻找符合要求的x的值
                if(!use[j]){
                    if(cnt == c){
                        ans += j+'0';
                        use[j] = true;
                        break;
                    }
                    ++cnt;
                }
            }
        }
        for(int j=1; j<=n; ++j)
            if(!use[j]){
                ans += j+'0';
                break;
            }
        return ans;
    }
};
复制代码

 

v带重复元素的排列

　　题目链接：http://www.lintcode.com/zh-cn/problem/permutations-ii/

v带重复元素的排列——first

　　思路：next_permutation()本身支持带重复元素的全排列

复制代码 
class Solution {
public:
    /**
     * @param nums: A list of integers.
     * @return: A list of unique permutations.
     */
    vector<vector<int> > ans;
    
    vector<vector<int> > permuteUnique(vector<int> &nums) {
        // write your code here
        sort(nums.begin(), nums.end());
        do{
            ans.push_back(nums);
        }while(next_permutation(nums.begin(), nums.end()));

return ans;
    }
};
复制代码

 

v带重复元素的排列——second

　　思路：枚举每个位置肯能出现的数字。

复制代码 
class Solution {
public:
    /**
     * @param nums: A list of integers.
     * @return: A list of unique permutations.
     */
    vector<vector<int> > ans;
    
    map<int, int> cnt;//记录每个数字在nums中出现的次数 
    void dfs(int n, vector<int> &nums, vector<int> &v){
        if(v.size() >= n){
            ans.push_back(v);
            return ;
        }
        
        for(int i=0; i<nums.size(); ++i)
            if(cnt[nums[i]]){
                --cnt[nums[i]];
                v.push_back(nums[i]);
                dfs(n, nums, v);
                v.pop_back();
                ++cnt[nums[i]];
            }
    }
    
    vector<vector<int> > permuteUnique(vector<int> &nums) {
        // write your code here
        sort(nums.begin(), nums.end());
      
        for(int i=0; i<nums.size(); ++i)
             ++cnt[nums[i]];
         int n = nums.size();
         nums.erase(unique(nums.begin(), nums.end()), nums.end());//清除重复的元素
         vector<int> v;
         dfs(n, nums, v);
              
        return ans;
    }
};
复制代码

 

v带重复元素的排列——third

　　思路：和 “全排列算法——first”方法类似，唯一不同的是下面代码中红色部分。

复制代码 
class Solution {
public:
    /**
     * @param nums: A list of integers.
     * @return: A list of unique permutations.
     */
    vector<vector<int> > ans;

    vector<vector<int> > permuteUnique(vector<int> &nums) {
        // write your code here
        sort(nums.begin(), nums.end());       
        bool flag = true;
        while(flag){
            flag = false;
            ans.push_back(nums);
            for(int i=nums.size()-1; i>=0; --i){
                for(int j=nums.size()-1; j>i; --j)
                    if(nums[i] < nums[j]){
                        flag = true;
                        while(j-1>i && nums[j-1]==nums[j]) --j;//如果前面有相同的数字，找到最左边的数字
                        swap(nums[i], nums[j]);
                        sort(nums.begin()+i+1, nums.end());
                        break;
                    }
                if(flag) break;
            }
        }
        return ans;
    }
};
复制代码

 

文章标签：
算法
机器学习/深度学习
人工智能
hjzgg
目录
相关文章
菊头蝙蝠
|
3月前
|
Java
leetcode-46：全排列
leetcode-46：全排列
菊头蝙蝠
21 1
下雪了-LKY
|
3天前
|
存储
全排列问题
全排列问题
下雪了-LKY
7 0
菊头蝙蝠
|
3月前
|
Java
leetcode-47：全排列 II
leetcode-47：全排列 II
菊头蝙蝠
21 0
宏阳李老师
|
9月前
|
C++
1199：全排列
1199：全排列
宏阳李老师
108 0
.昭阳.
|
7月前
全排列
全排列，
.昭阳.
22 0
小李の踢踏舞步
|
8月前
|
机器学习/深度学习 存储 算法
算法训练Day29|* 491.递增子序列* 46.全排列* 47.全排列 II
算法训练Day29|* 491.递增子序列* 46.全排列* 47.全排列 II
小李の踢踏舞步
37 0
LeetCode连庆
|
10月前
|
机器学习/深度学习 算法 安全
LeetCode - #47 全排列 II
不积跬步，无以至千里；不积小流，无以成江海，Swift社区 伴你前行。如果大家有建议和意见欢迎在文末留言，我们会尽力满足大家的需求。
LeetCode连庆
35 0
Far_Stars
|
10月前
leetcode:47.全排列 II
给定一个可包含重复数字的序列，返回所有不重复的全排列。
Far_Stars
36 0
Far_Stars
|
10月前
leetcode:46.全排列
给定一个没有重复数字的序列，返回其所有可能的全排列。
Far_Stars
35 0
songwei4615.
leetcode 46 全排列
leetcode 46 全排列
songwei4615.
37 0
leetcode 46 全排列