leetcode总结无止境系列之排列组合算法

一、排列算法

字典序法:

对给定的字符集中的字符规定一个先后关系,在此基础上按照顺序依次产生每个排列。例如字符集{1,2,3},按字典序生成的全排列是:123,132,213,231,312,321 例如:839647521的下一个排列

  • Step1:从最右开始,找到第一个比右边小的数字4(因为4<7, 而7>5>2>1),再从最右开始,找到4右边比4大的数字5(因为4>2>1而4<5)。4、5也即从右往左找到的第一个对严格的升序对。
  • Step2:交换4、5。
  • Step3:倒置5右边的7421为1247.即得到下一个排列839651247.

该方法支持数据重复,且在C++STL中被采用。例题见下面leetcode题:Next Permutation

递归法

例如,如果集合是{a,b,c},那么这个集合中元素的所有排列是{(a,b,c),(a,c,b),(b,a,c),(b,c,a),(c,a,b),(c,b,a)},显然,给定n个元素共有n!种不同的排列,如果给定集合是{a,b,c,d},可以用下面给出的简单算法产生其所有排列,即集合(a,b,c,d)的所有排列有下面的排列组成:

(1)以a开头后面跟着(b,c,d)的排列
(2)以b开头后面跟着(a,c,d)的排列
(3)以c开头后面跟着(a,b,d)的排列
(4)以d开头后面跟着(a,b,c)的排列,这显然是一种递归的思路
注意:当给出的数组包含重复元素时,用上面的方式生成全排列便会有重复的,因而需要增加一条规则:去重的全排列就是从第一个数字起每个数分别与它后面非重复出现的数字交换。

//依次让n个字母中的一个字母"打头阵",其余n-1个字母全排列
void permutation(char *pStr, char *pBegin)
{   
    if(pStr == NULL || pBegin == NULL)
        return;
    if(*pBegin == '\0')
        printf("%s\n", pStr);
    else
        for(char* pCh = pBegin; *pCh != '\0'; pCh++)
    {
        swap(*pBegin, *pCh);
        permutation(pStr, pBegin + 1);
        swap(*pBegin, *pCh);
    }
}

tip:若对于数字的全排列,也可以递归+做标志位,这样的话就不需要做交换,只检查标志位即可。例题见下面leetcode题:Permutation和PermutationII

二、组合算法

全组合问题(求一个集合的所有子集)

思路一、二进制转化法,即将每个组合与一个二进制数对应起来,枚举二进制的同时,枚举每个组合。这种方法由于有一一对应的特质,所以要求原数组中的各元素应该各不相同,否则求出来的子集和会有重复元素。

思路二、其实是换一种方式做标记,每次改变某个元素的标识位形成一个组合。这种方法也不适用于原数组中有重复的元素

思路三、当原数组中包含重复元素时,就不能按照上面两种一一对应标记的思路,而应该对每个当前非重复元素取或者不取都组成一个结果。 例题见下面leetcode题:Subsets和SubsetsII

从n个数中选k个数

对于(n, k)问题,不停地选取集合n中的元素,直到个数为k,然后开始回溯,去掉k中的第一个元素,再纳入n中的下一个元素,依次类推不断回溯,直到遍历所有的可能性。例题见下面leetcode题:Combination.


leetcode 上相关题目汇总

1、Next Permutation

2、Permutations

3、Permutations II

4、Subsets

5、Subsets II

6、Combinations

7、Combination Sum

8、Combination Sum II

9、Permutation Sequence

crystal /
Published under (CC) BY-NC-SA in categories 面试  tagged with 算法  leetcode