精华内容
下载资源
问答
  • 含有相同元素的全排列
    千次阅读
    2018-05-22 18:29:23

    递归的解决子字符串的全排列,

    这里需要注意的是重复元素需要预先判断

    例如 aabcbd

    当进行到k = 1,接下来求 子串bcbd的全排列,但是后面有两个b,无论这两个b中的哪一个与此时的a交换,后面子串都包含字符abcd 也就是 子串的全排列相同,又因为 原先的a 在相同的b交换后都变成了 b 也就是 这两种交换下的全排列相同

    所以重复,需要跳过保留其中的一种就可以了。查询是否重复的区间为当前进行到的位置k 和 准备交换的位置i,在i之前若有重复的,则说明k位置元素不需要再与i位置元素进行交换了.

    全排列:每个k位置与其之后的元素进行交换,然后递归的解决子串(有重复元素的按照上述方法处理就可以了),交换后也有个回溯的过程

    string str,p;
    
    bool check(string a, int k, int i)
    	{
    		if(i > k){ //排除 i ==k 也就是 允许自身交换 
    			for(int j = k; j < i; ++j){
    				if(a[j] == a[i])
    					return false;
    			} 
    		}
    		return true;
    	}
    
    void perm(string a,int k, int m)//m为最后一个元素下标
    	{
    		if(k == m){
    			for(int i = 0; i < a.size(); ++i){
    				printf("%c",a[i]);
    			}
    			cout <<endl;
    			return ;
    		}
    		
    		for(int i = k; i <= m; ++i){//注意等号
    			if(check(a,k,i)){
    				swap(a[i],a[k]);
    				perm(a,k+1,m);
    				swap(a[i],a[k]);
    			}
    		}
    	}

    更多相关内容
  • 1.给定一个数组,数组中元素均不相同,写出数组元素的全排列组合 ...由于数组中不含相同元素,所有不用考虑重复问题,现在我们来解析 [1,2,3]的全排列是如何得到的: 1,2,3的全排列,我们先看后两个数[2,3]的...

    1.给定一个数组,数组中元素均不相同,写出数组元素的全排列组合

    比如: 
    [1,2,3]
    Output:
    [
      [1,2,3],
      [1,3,2],
      [2,1,3],
      [2,3,1],
      [3,1,2],
      [3,2,1]
    ]

    由于数组中不含相同元素,所有不用考虑重复问题,现在我们来解析 [1,2,3]的全排列是如何得到的:

    1,2,3的全排列,我们先看后两个数[2,3]的全排列,很明显是2,3 和3,2,分别以2开头和3开头

    然后看[1,2,3]的全排列,分别为1,2,3;1,3,2;2,1,3;2,3,1;3,1,2;3,2,1;它们是以1开头和2,3全排列的组合,

    以2开头1,3,全排列的组合,以3开头1,2,全排列的组合

    也就是说我们可以将三个数的全排列问题转化为两个数的全排列问题,方法是:将数组中的每一个数均与数组的第一位的数进行交换,然后对剩下的数进行全排列;每一次交换后要交换回去,因为每一次都是在[1,2,3]的基础上进行的

    以[1,2,3]为例就是,数组中的每一个元素都与第一为元素进行交换,1与第一位元素交换,得1,2,3;然后交换回去,为下一次交换做准备

    2与第一位元素交换,得2,1,3

    3与第一位元素交换,得3,2,1

    然后对于得到1,2,3;2,1,3;3,2,1问题就可以缩减为除去第一位后2,3; 1,3; 2,1的全排列,然后与第一位组合

    而对于2,3的全排列,也可以使用同样的方法,分别将元素2,3与第一位元素进行交换,继续缩减问题,转化为1个元素的全排列问题,对于2,3就是2,3;3,2;然后转化为单元素3和2的全排列问题

                              1,2,3                   //原问题    
                         /      |      \
                    1,2,3      2,1,3    3,2,1         //遍历数组将数组元素分别与第一位元素交换,缩减问题为两个数的全排列问题,将问题缩减为了[2,3];[1,3];[2,1]的全排列问题
                   /    \     /    \     /     \
             1,2,3  1,3,2  2,1,3  2,3,1 3,2,1  3,1,2 //遍历数组[2,3],将数组元素分别与第一位元素交换,将问题缩减为1个数的全排列问题,即将问题缩减为[2]和[3]的全排列问题;其他数组[1,3];[2,1]类似处理
                |     |      |      |    |       |
             1,2,3   1,3,2  2,1,3  2,3,1 3,2,1  3,1,2 //可以继续这一步,也可以不继续,就是i = nums.size() 和nums.size()-1的区别
    
    所以明显看出可以用深度优先搜索解决,因为每一步所做的处理是相同的

     

    class Solution {
    public:
        vector<vector<int>> permute(vector<int>& nums) 
        {
            int len = nums.size();
            vector<vector<int>> res;
            DFS(nums,0,res);
            return res;
        }
    private:
        void DFS(vector<int>&nums,int i,vector<vector<int>>& res)
        {
            if(i == nums.size())//因为每一次交换就可以将问题缩减一级,所以nums.size()次交换就可以将问题缩减为0级,0个数的全排列问题,问题最终得到解决,当然缩减到1级也是可以的(就是没有了最后自身与自身的交换而已)
            {
                res.push_back(nums);
                return;
            }
            for(int j = i; j < nums.size();j++)//遍历数组,分别将每一位元素与当前数组首位元素交换
            {
                swap(nums[i],nums[j]);//通过交换来实现全排列
                DFS(nums,i+1,res);
                swap(nums[i],nums[j]);//进行下一次交换时,是在原数组的基础上进行的,所以必须把首位元素交换回来
            }
            return;
        }
        
        
    };

    2.给定一个数组,数组中元素可以相同,写出数组元素的全排列组合,组合中不可以出现相同的排列

    例如:
    Input: [1,1,2,2]
    Output:
    [[1,1,2,2],[1,2,1,2],[1,2,2,1],[2,1,1,2],[2,1,2,1],[2,2,1,1]]

    我们先来简单分析一下,仍然采用缩减问题的方法,遍历数组中每一个元素与第一个元素交换,得到四个数组

     [1,1,2,2];[1,1,2,2];[2,1,1,2];[2,1,2,1]我们发现缩减的问题有重复,有些缩减的问题是不可取的(重复),所以我们在交换之前要判断一下,该元素交换后的数组是否已经出现过,出现过则是重复问题,要舍弃;

    所以在遍历元素与数组首元素交换时要判断是否已经出现过重复的结果,那么如何判断呢?

    在[1,1,2,2]为一般性,我们用 i 代表数组首元素的下标,j 遍历数组元素时元素的下标,由于均与第一个元素交换,所以我们可以尝试着将第一个元素作为标志位,[1,1,2,2] i = 0,j =0时交换为[1,1,2,2];此时标志位为首元素1,就是说如果后面遍历的元素中再出现1,则与i=0 处的元素相交换后会产生重复(就是 i = 0,j = 1,这种情况,交换过后结果为[1,1,2,2],重复,所以这种情况应该舍去);当i =0,j = 2时,与标志位1不等,所以可以交换,为[2,1,1,2],此时首元素位置处为2,标志位更新为2;这样就可以避免首元素为2的重复,(注,这里与上面不含重复元素的数组的全排列的不同之处在于,它交换后并不交换回来,而是在交换的基础上进行下去,当然这样的目的是为了避免重复)

    而且这样做的前提是,数组中的元素必须按大小进行排列,否则

    if(i != j && nums[i] == nums[j])
    {
        continue;
    }

    不能剔除掉所有的重复排列;而且由于交换后不交换回来,而且要保持  遍历数组时的连续性(即这一次遍历交换在上次遍历交换的基础上进行,其实就是为了保留本次的标志位),所以程序中用的是指传递,而不是引用

    这样在交换[1,1,2,2]中的第2个元素与首元素标志位后,就变为了[2,1,1,2],之后在[2,1,1,2]的基础上进行判断,而不再采用[1,1,2,2];

    如果用引用,则由于每一次都是深度优先搜索,中间有很多次交换性,如果交换后不交换回来,则会破坏数组元素的有序性,如果交换后交换回来,则每一次又都会在[1,1,2,2]的基础上进行,而不会保留上一次的标志位

    完整程序如下:

    class Solution {
    public:
        vector<vector<int>> permuteUnique(vector<int>& nums) 
        {
            sort(nums.begin(),nums.end());
            vector<vector<int>> res;
            int len = nums.size();
            if(len == 0)
            {
                return res;
            }
            
            DFS(nums,0,res);
            return res;
        }
    private:
        void DFS(vector<int> nums,int i ,vector<vector<int>> & res)
        {
            if(i == nums.size())
            {
                res.push_back(nums);
                return;
            }
            for(int j = i;j < nums.size();j++)
            {
                if(j != i && nums[i] == nums[j])
                {
                    continue;
                }
                swap(nums[i],nums[j]);
                DFS(nums,i+1,res);   
            }
        }
    };

    3.下一个排列

    在这个问题中我们不在要求求出所以元素的全排列,而只是想知道按字典比当前排列大的最近的排列是什么,如果当前排列已经是最大排列,则给出最小排列

    比如

    1,2,3 → 1,3,2  //1,3,2是比排列1,2,3大的最近的排列
    3,2,1 → 1,2,3  //3,2,1已经是最大排列,所以转写为最小排列 1,2,3
    1,1,5 → 1,5,1  //1,5,1 是比排列 1,1,5大的最近的排列

    为简单起见先考虑整数,

    比如   123 ,我们想要求由这三个数字组成比它大的最近的元素我们会怎么做,由于要求比123大且差值最小,所以能不动百位数1就不动1,由于个位数3比十位数3大,所以交换后132 > 123;符合要求

    那么 1243 呢?秉承原则,高位能不动就不动,而且只能操作该位本身和低于它的位,从十位入手,由于4>3,所以不能动十位(因为4,3交换后变小),而2<4所以可以通过调整百位来使其增大,为了使其增大的最小,我们应该在4,3中选择一个比2大且差值最小的数,应选择3,同时十位和个位数应该按升序排列(由于在1243中,找到百位2时才满足高位小于低位,所以从十位到个位是降序排列的,只要对其进行反转即可),这样才能使其增大但增大的最少。

    再以 56486431为例进行说明,由于 1 < 3, 3 < 4所以任意交换个十百位均只能使其减小,继续比较 4<6,6<8,8>4,所以可以调整4所在的这一位,在比4这一位低的位中进行查找大于4但差值最小的数,明显是6,与之交换,变为 56 684431,我们发现交换完毕后,6之后的数明显是降序排列,所以我们对其进行翻转就可以得到我们的目标数,56 613448,这就是比56486431大但差值最小的数,也是这几个数的全排列

    完整程序如下:需要先进行相邻位的比较,找到需要调整的位,然后在比该位低的位中找一个比该位处的数大但差值最小的数,交换两者,然后将该位之后的元素进行翻转

    class Solution {
    public:
        void nextPermutation(vector<int>& nums) 
        {
            //寻找应该被交换的点
            int i = nums.size()-2;
            while(i >= 0 && nums[i+1] <= nums[i])//找到需要调整的位。如果该数组元素排列已经是最大值,则 i = -1;最后将数组全部翻转即可
            {
                i--;
            }
            if(i >= 0)
            {
                int j = nums.size()-1;
                while(i >= 0 && nums[j] <= nums[i])//找到比需要调整位处的数大但查找最小的数
                {
                    j--;
                }
                swap(nums[i],nums[j]);//交换两者
                
            }
            reverse(nums.begin()+i+1,nums.end());//翻转
        }
    };

     

    展开全文
  • 有重复元素全排列

    2019-10-09 12:45:34
    全排列的本质:对于一个字符串,递归的令每一个元素与其后面的每一个元素交换。 或者可以理解为 例如字符串abc:先观察第一个元素a,将a分别与b,c交换 得到bac cba 再对于abc, bac, cba 观察第二个元素,与第三...

    使用递归的方法解决全排列问题

    全排列的本质:对于一个字符串,递归的令每一个元素与其后面的每一个元素交换。

    或者可以理解为

    例如字符串abc:先观察第一个元素a,将a分别与b,c交换 得到bac  cba

                                再对于abc, bac, cba  观察第二个元素,与 第三个元素交换得 acb, bca, cab

                                所以abc的全排列为 abc, bac, cba, acb, bca, cab

    若是字符串中有重复元素,那么 需要判断在一个元素与所有后续元素的交换过程中,有没有重复的元素即将被交换,如果有的话则跳过这次交换。

    代码如下:

    #include <iostream>
    // 有重复元素的全排列
    using namespace std;
    
    // 全排列的总个数
    int Num = 0;
    
    void swap(char &a, char &b) {
        char temp;
        temp = a;
        a = b;
        b = temp;
    }
    
    // 判断s[i]的值是否在s[cur]~s[i]中出现过
    bool no_same(char* s, int cur, int i){
        // 如果s[cur]的值在前面出现过,那么若s[cur]参与交换就会产生相同的排列
        for(int k = cur; k < i; ++k){
            if(s[i] == s[k]){
                return false;
            }
        }
        return true;
    }
    
    void full_per(char* s, int cur, int len){
        // 终止条件:当前参与交换的是最后一个元素
        if(cur == len-1){
            // 输出一个排列
            for(int i = 0; i < len; ++i){
                cout << s[i];
            }
            cout << endl;
            Num++;
        }
        // 递归实现:当前cur元素与后面的每一个元素交换
        for(int i = cur; i < len; ++i){
            // 如果s[cur]没有出现过,进入递归交换
            if(no_same(s, cur, i)) {
                swap(s[i], s[cur]);
                full_per(s, cur + 1, len);
                // 换回来,保证交换的有序进行
                swap(s[i], s[cur]);
            }
        }
    }
    
    int main() {
        int n;
        cin >> n;
        char s[20];
        cin >> s;
        // 计算字符数组长度,减去回车和结束符
        full_per(s, 0, n);
        cout << Num << endl;
        return 0;
    }

    使用字典序的方法解决全排列问题

    先求出最小串如 “123456” 显然最大串为“654321”

    字典序全排列的原理:生成的下一个排序恰好比当前排列大,由此从小到大生成的排序集合一定是全排列。

    显然,使用字典序可以直接排除重复元素的问题。

    参考:https://zh.wikipedia.org/wiki/%E5%85%A8%E6%8E%92%E5%88%97%E7%94%9F%E6%88%90%E7%AE%97%E6%B3%95

    展开全文
  • 输入一个字符串(可能有重复字符),输出该字符串中所有字符的全排列。 示例: 输入:s = "abb" 输出:["abb","bab","bba"] 思路 首先对给定字符串排序,使相同的字符排在一起; 利用回溯法,搜索出所有可能的情况...

    输入一个字符串(可能有重复字符),输出该字符串中所有字符的全排列。
    示例:
    输入:s = "abb"
    输出:["abb","bab","bba"]
    题目来源:LeetCode 剑指 Offer 38. 字符串的排列

    思路

    1. 首先对给定字符串排序,使相同的字符排在一起;
    2. 利用回溯法,搜索出所有可能的情况;
    3. 剪枝,如果当前位置的字符和上一位置的字符相同,且上一字符已被选,此情况跳过,实现去重;
    4. 本篇利用的是位运算记录字符是否被选中。

    代码

    class Solution {
    public:
        void dfs(int u, int n, vector<char>& cur, string s, vector<string>& ans, int pos) {
            if (u == n) {
                string res = "";
                for (char c : cur)
                    res += c;
                ans.push_back(res);
                return;
            }
            
            for (int i = 0; i < n; i ++ ) {
                if (i && s[i] == s[i - 1] && (pos >> (i - 1) & 1)) continue; //相同且上一字符被选
                if ((pos >> i) & 1) continue; //当前字符被选
                cur.push_back(s[i]);
                dfs(u + 1, n, cur, s, ans, pos | (1 << i));
                cur.pop_back();
            }
        }
    
        vector<string> permutation(string s) {
            sort(s.begin(), s.end());
            vector<string> ans;
            int n = s.size();
            vector<char> cur; //当前已选中的字符
            dfs(0, n, cur, s, ans, 0);
            return ans;
        }
    };
    
    展开全文
  • 全排列—含重复元素

    2020-10-06 10:49:46
    种,因为含有重复元素,故对其进行全排列含有重复的全排列类型。故在处理含有重复元素的问题时,需要对这些重复的元素进行相应的处理,即在进行全排列中需要对相应的重复元素进行去重。 二、相应的算法 1.交换法 ...
  • 有重复元素全排列问题

    千次阅读 2020-12-18 22:10:09
    有重复元素全排列问题 只是在没有重复的全排列问题上去除重复的部分即可 思想方法:递归 例如 s[4]=aacc s[0] 作为head 全排列剩下的三个 s[1] 与s[0] 交换 由于s[1]==s[0] 不交换 如果交换,那么全排列剩下的三...
  • 全排列问题(不含相同元素和含有相同元素) Leetcode46 Leetcode47 回溯解法+Java代码
  • 本文主要介绍基于分治方式(递归)和枚举方式(循环)来构建指定字符串的全排列方法,两种方法都可以解决重复元素全排列 欢迎探讨,如有错误敬请指正 如需转载,请注明出处 http://www.cnblogs.com/nullzx/ ...
  • i++){ //每次开始递归之前判断本元素是否已经遍历 if(!set.contains(nums[i])){ //加入set标志本数已经遍历过 set.add(nums[i]); //替换本位置表示本位置的数确定下来 swap(nums,index,i); //接着下一个位置的判断 ...
  • 含有重复元素序列的全排列。 示例1: 输入:1,1,3 输出: 1 1 3 1 3 1 3 1 1 二、解题思路 ​ 回溯方法的思想及模板参考回溯系列-算法思想与模板,根据此算法的模板我们就可以解决此题。不重复元素的...
  • 含有重复元素集合的全排列 给定一个可包含重复数字的整数集合 nums ,按任意顺序 返回它所有不重复的全排列。 示例 1: 输入:nums = [1,1,2] 输出: [[1,1,2], [1,2,1], [2,1,1]] 示例 2: 输入:nums = [1,2,3] ...
  • 当前元素和相同元素交换产生的排列是重复的 所以在swap之前我们要先判断,该位置的元素是否已经和index交换过了。具体的实现是通过一个哈希表来记录出现过的元素 class Solution { List<List<Integer>>...
  • 文章目录1. 问题定义2. 递归生成1~n的排列3. 复杂度分析4. 排列树(解答树)5....即若n=3,则有全排列 {123,132,213,231,312,321}\{123,132,213,231,312,321\}{123,132,213,231,312,321}。 或者输...
  • 有一个含n个整数的数组a,所有元素均不相同,求其所有元素全排列 例如,a[]={1,2,3},得到结果是(1,2,3)、(1,3,2)、(2,3,1)、(2,1,3)、(3,1,2)、(3,2,1) 2. 解题思路 3. ...
  • 剑指 Offer II 083. 没有重复元素集合的全排列 / 剑指 Offer II 084. 含有重复元素集合的全排列
  • 实际上就相当于 111 000 这样含有重复的数字全排列问题 对于含有重复数据的全排列,实际上是对递归回溯过程中的数形递归结构进行剪枝操作,即:递归树中的同一层不能有重复数据出现,要实现这一点在递归的过程中...
  • 给定一个可包含重复数字的整数集合 nums ,按任意顺序 返回它所有不重复的全排列。 示例 1: 输入:nums = [1,1,2] 输出: [[1,1,2], [1,2,1], [2,1,1]] 示例 2: 输入:nums = [1,2,3] 输出:[[1,2,3],[1,3,2],[2,1...
  • 有一个含有n个整数的数组a,所有元素均不相同,求其所有元素全排列(n)(回溯法)
  • 给定一个可包含重复数字的整数集合 nums ,按任意顺序 返回它所有不重复的全排列。 示例1 输入:nums = [1,1,2] 输出: [[1,1,2], [1,2,1], [2,1,1]] 示例2 输入:nums = [1,2,3] 输出:[[1,2,3],[1,3,2],[2,1,3],[2...
  • 题目 力扣 思路 回溯 和上一题思路相似,不同之处是在遍历之前加一个遍历,判断如果当前元素与上一个元素相同而且上一个元素已访问或未访问时,就continue。 代码 class Solution { public: vector> ans; vector vis...
  • 输入:所有字符各不相同的一个字符串,长度为1~6,如:abc 输出:字符串中所有字符构成的全排列(要求存放在一个char型二维数组中),如:abc,acb,bac,bca,cab,cba 这道题适合采用递归的解法,总体上有两种思路:...
  • 对不重复的元素进行全排列 提示:文章写完后,目录可以自动生成,如何生成可参考右边的帮助文档 ...排列结果中的每个元素来自于原始数组,数量和内容与原始数组相同,只是元素的位置发生了改变。 比如对abc字符
  • 题目描述:将一个数组全排列后输出。eg1:{“a”,“b”,“c”} ——&gt;[a, b, c]、[a, c, b]、[b, a, c]、[b, c, a]、[c, a, b]、[c, b, a]eg2:{"a", "c", "c", "d"...
  • 给定一字符串,可能含有相同元素。请借助递归设计算法求出该字符串的所有不同的排序。输入格式:第一行输入一个整数T(小于等于10),代表有T组测试样例。接下来T行,每行给定一串字符串(长度小于等于9,且至少有3个...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 2,061
精华内容 824
关键字:

含有相同元素的全排列