字符串的全排列

2018-09-02 | 阅读：次

字符串的全排列

题目描述

输入一个字符串，打印出该字符串中字符的所有排列。

例如输入字符串abc，则输出由字符a、b、c 所能排列出来的所有字符串

abc、acb、bac、bca、cab 和 cba。

分析与解法

解法一、递归实现

从集合中依次选出每一个元素，作为排列的第一个元素，然后对剩余的元素进行全排列，如此递归处理，从而得到所有元素的全排列。以对字符串abc进行全排列为例，我们可以这么做：以abc为例

固定a，求后面bc的排列：abc，acb，求好后，a和b交换，得到bac
固定b，求后面ac的排列：bac，bca，求好后，c放到第一位置，得到cba
固定c，求后面ba的排列：cba，cab。

代码可如下编写所示：

void CalcAllPermutation(char* perm, int from, int to)
{
	if (to <= 1)
	{
		return;
	}

	if (from == to)
	{
		for (int i = 0; i <= to; i++)
			cout << perm[i];
		cout << endl;
	}
	else
	{
		for (int j = from; j <= to; j++)
		{
			swap(perm[j], perm[from]);
			CalcAllPermutation(perm, from + 1, to);
			swap(perm[j], perm[from]);
		}
	}
}

解法二、字典序排列

首先，咱们得清楚什么是字典序。根据维基百科的定义：给定两个偏序集A和B,(a,b)和(a′,b′)属于笛卡尔集 A × B，则字典序定义为

(a,b) ≤ (a′,b′) 当且仅当 a < a′ 或 (a = a′ 且 b ≤ b′)。

所以给定两个字符串，逐个字符比较，那么先出现较小字符的那个串字典顺序小，如果字符一直相等，较短的串字典顺序小。例如：abc < abcd < abde < afab。

那有没有这样的算法，使得

起点：字典序最小的排列, 1-n , 例如12345
终点：字典序最大的排列，n-1, 例如54321
过程：从当前排列生成字典序刚好比它大的下一个排列

答案是肯定的：有，即是STL中的next_permutation算法。

在了解next_permutation算法是怎么一个过程之前，咱们得先来分析下“下一个排列”的性质。

假定现有字符串(A)x(B)，它的下一个排列是：(A)y(B’)，其中A、B和B’是“字符串”(可能为空），x和y是“字符”，前缀相同，都是A，且一定有y > x。
那么，为使下一个排列字典顺序尽可能小，必有：
A尽可能长
y尽可能小
B’里的字符按由小到大递增排列

现在的问题是：找到x和y。怎么找到呢？咱们来看一个例子。

比如说，现在我们要找21543的下一个排列，我们可以从左至右逐个扫描每个数，看哪个能增大（至于如何判定能增大，是根据如果一个数右面有比它大的数存在，那么这个数就能增大），我们可以看到最后一个能增大的数是：x = 1。

而1应该增大到多少？1能增大到它右面比它大的那一系列数中最小的那个数，即：y = 3，故此时21543的下一个排列应该变为23xxx，显然 xxx(对应之前的B’）应由小到大排，于是我们最终找到比“21543”大，但字典顺序尽量小的23145，找到的23145刚好比21543大。

由这个例子可以得出next_permutation算法流程为：

next_permutation算法

定义
升序：相邻两个位置ai < ai+1，ai 称作该升序的首位
步骤（二找、一交换、一翻转）
找到排列中最后（最右）一个升序的首位位置i，x = ai
找到排列中第i位右边最后一个比ai 大的位置j，y = aj
交换x，y
把第(i+ 1)位到最后的部分翻转

还是拿上面的21543举例，那么，应用next_permutation算法的过程如下：

x = 1；
y = 3
1和3交换
得23541
翻转541
得23145

23145即为所求的21543的下一个排列。参考实现代码如下：

bool CalcAllPermutation(char* perm, int num){
	int i;

	//①找到排列中最后（最右）一个升序的首位位置i，x = ai
	for (i = num - 2; (i >= 0) && (perm[i] >= perm[i + 1]); --i){
		;
	}
	// 已经找到所有排列
	if (i < 0){
		return false;
	}

	int k;
	//②找到排列中第i位右边最后一个比ai 大的位置j，y = aj
	for (k = num - 1; (k > i) && (perm[k] <= perm[i]); --k){
		;
	}

	//③交换x，y
	swap(perm[i], perm[k]);
	//④把第(i+ 1)位到最后的部分翻转
	reverse(perm + i + 1, perm + num);
	return true;
}

然后在主函数里循环判断和调用calcAllPermutation函数输出全排列即可。

解法总结

由于全排列总共有n!种排列情况，所以不论解法一中的递归方法，还是上述解法二的字典序排列方法，这两种方法的时间复杂度都为O(n!)。

####其他参考一：

https://www.cnblogs.com/big-xuyue/p/4147635.html

根据如上算法为什么能得到已知排列的下一个排列？我们来分析一下。

　　假设我们对已知排列 P1P2…Pn 求其下一个排列，默认为按字典序递增，P1P2…Pn 可能是一串数字，为了便于计算，统统将其看作一个字符串。首先我们需要清楚的一点是下一个刚好比 P1P2…Pn 大的排列应当和原排列有尽可能长的相同前缀（高位保持一致，尽可能在低位上发生变化），剩下变化的部分称为后缀，假设为 PjPj+1 … Pn ，我们的所有变化都在这个子串上进行。

对于上述子串 PjPj+1 … Pn ，隐含如下信息：

对于下一个排列的生成过程，实际上就是对子串 PjPj+1 … Pn 某些位置上的数值进行交换。
Pj 位置上的数值必然会与之后某个位置上的数值进行交换，因为 Pj 是后缀上的第一个位置，故必须发生变化，而且必须与后缀其他位置上的数字交换。
交换之后Pj位置上的数值必然比原数值大，因为我们按默认字典序递增计算下一个排列，也就是说，在 Pj 之后的某个位置上必须存在比 Pj 大的数值。

　　根据以上三点，我们就能确定 Pj 的位置了。为了保证尽可能长的前缀，我们需要从尾部向前检查，检查的条件是满足 Pi<Pi+1 。一旦满足这个条件，就保证了在后缀上至少有一个数值大于 Pi ，即 Pi+1 ，如果不满足这个条件，从后向前是一个递增的序列，在后缀上不会存在大于Pi的数值，即不满足以上第三点，继续向前检查，第一个满足 Pi<Pi+1 的 Pi 就是我们要寻找的 Pj （理由是尽可能高位保持一致）。这时候在后缀上至少存在 Pi+1 是大于 Pi （即 Pj ）的，但同时也可能后缀存在多个大于 Pj 的数值，我们应该选取哪一个与Pj交换呢？当然是刚好比 Pj 大的那个，即比Pj大的数值中最小的那个（设为 Pk ），原因很简单，如果选择了一个不是最小的数值 Pc 与 Pj 交换，那生成的排列与原排列之间必然还有其他排列（这个排列就是后缀中任何一个比 Pc 小且比 Pj 大的数值与 Pj 交换产生的排列），那就不是我们需要的下一个排列了。因此：

　　　　　　　　　　PjPj+1 … PkPk+1 … Pn（Pk为后缀中刚好比Pj大的数值）

交换之后：

　　　　　　　　　　PkPj+1 … PjPk+1 … Pn

　　此时 Pk （原 Pj ）处已经确定下来了，那后面的排列怎么排呢？我们既然是要产生刚好比原排列大的下一个排列，当然是在满足情况的前提下使新排列尽可能的小，而此时 Pk （原 Pj ）位置比原此位置上的数值大，因此后面无论怎么排，新生成的排列都比原排列大，因此在只要 Pk 之后的排列找到一个最小的就行了。而在 Pj 与 Pk 交换之前这段序列是从后向前递增有序的，那交换以后呢？

　　　　　　　　　因为 Pj < Pk ， Pj > Pk+1， Pk < Pk-1

　　　　　　　　　所以 Pk-1 > Pj > Pk+1

　　所以交换之后仍然是从后向前递增有序，因此只需要把后面的序列逆置一下就行了，最后生成的新排列就是我们所有的下一个排列。

其他参考2：

https://blog.csdn.net/qq_16234613/article/details/77169300

例如：对于2763541找出字典序的下一个排列。 2763541 （从右至左首先出现的是35，3<5）； 2763541 （在3的位置之后从右至左找到第一个比3大的数4）； 2764531 （交换3,4的位置）； 2764135 （把原来3的位置现在4位置后面的数值5,3,1反转）。

解：就是找到比2763541大的但是同时在1、2、3、4、5、6、7所有排列中比2763541大的程度中最小的一个。为了找到大的程度最小的，一般保证前面的数字位置不调换，优先调换后面数字的排列。首先注意到541是按照降序排列（为什么是降序，只要按照字典序算法，后面就一直这样。），如果我们想通过调换541的位置显然不行,5>4>1，当我们遇到3时，发现有戏，因为在3的后面有比3大的数字，我们把3往后调，把一个大的数字往前调就能把排列整体变大。那么3后面有5和4，我们选择哪一个的，显然是4，因为其增大程度较小。有因为3<4，所以调换位置后后面数字依然是降序，我们只要将其调成升序即可变成最小。

python实践：

class Solution(object):
    #1.递归实现https://blog.csdn.net/sty945/article/details/79839567
    #https://blog.csdn.net/qq_42015869/article/details/79996227，此博客写的很详细
    def FullArr1(self, lstr, begin, end):
        # lstr = list(string)
        # length = len(string)
        # if length <= 1:
        #     return string
        if begin >= end:
            print(lstr)
        else:
            j = begin
            for i in range(begin, end):
                #位置进行交换
                lstr[i], lstr[j] = lstr[j], lstr[i]
                Solution().FullArr1(lstr, begin+1, end)
                lstr[i], lstr[j] = lstr[j], lstr[i]

    #定义交换字符串位置
    def Swap(self, string, index):
        lstr = list(string)
        temp = lstr[index]
        lstr[index] = lstr[0]
        lstr[0] = temp
        return str(lstr)
    """
    case1:
    已知字符串里的字符是互不相同的，现在任意组合，比如ab，
    则输出aa，ab，ba，bb，编程按照字典序输出所有的组合。
    分析：非简单的全排列问题（跟全排列的形式不同,abc全排列的话，
    只有6个不同的输出）。 本题可用递归的思想，设置一个变量表示已输出的个数，
    然后当个数达到字符串长度时，就输出。
    """
    def case1(self, string, size, resPos):
        result = []
        if resPos == size:
            print(result)
        else:
            for i in range(0, size):
                result[resPos] = string[i]
                Solution().case1(result, string, size, resPos + 1)
        print(result)

    def case2(self, ls):
        pj = 0
        pk = 0
        maxK = []
        length = len(ls)
        for i in range(length-1, -1, -1):
            for j in range(length-2, -1, -1):
                #print(j)
                if ls[i] > ls[j]:
                    pj = ls[j]
                    print(pj)
                    for k in range(j+1, length):
                        if ls[k] > pj:
                            maxK.append(ls[k])
                    pk = max(maxK)
                else:
                    continue

if __name__ == "__main__":
    s = "ab"
    lstr = list(s)
    #print(Solution().FullArr1(lstr, 0, len(lstr)))
    #Solution().Swap(s, 1)
    #Solution().case1(s, 2, -1)
    # for i in range(0, 2):
    # print(i)
    l1 = [1, 2, 3]
    Solution().case2(l1)

运行结果：

D:\1b\Anoconda\setup\set\envs\tensorflow\python.exe E:/python_workspace/algorithm/字符串的全排列/FullArrange.py
2
1
1

类似问题

1、已知字符串里的字符是互不相同的，现在任意组合，比如ab，则输出aa，ab，ba，bb，编程按照字典序输出所有的组合。

分析：非简单的全排列问题（跟全排列的形式不同,abc全排列的话，只有6个不同的输出）。本题可用递归的思想，设置一个变量表示已输出的个数，然后当个数达到字符串长度时，就输出。

//copyright@ 一直很安静 && World Gao
//假设str已经有序
void perm(char* result, char *str, int size, int resPos)
{
  if(resPos == size)
    printf("%s\n", result);
  else
    {
      for(int i = 0; i < size; ++i)
        {
          result[resPos] = str[i];
          perm(result, str, size, resPos + 1);
        }
    }
}

2、如果不是求字符的所有排列，而是求字符的所有组合，应该怎么办呢？当输入的字符串中含有相同的字符串时，相同的字符交换位置是不同的排列，但是同一个组合。举个例子，如果输入abc，它的组合有a、b、c、ab、ac、bc、abc。

3、写一个程序，打印出以下的序列。

(a),(b),(c),(d),(e)……..(z)

(a,b),(a,c),(a,d),(a,e)……(a,z),(b,c),(b,d)…..(b,z),(c,d)…..(y,z)

(a,b,c),(a,b,d)….(a,b,z),(a,c,d)….(x,y,z)

….

(a,b,c,d,…..x,y,z)