剑指27-字符串的排列

Posted on | In |

题目描述

输入一个字符串,按字典序打印出该字符串中字符的所有排列。例如输入字符串abc,则打印出由字符a,b,c所能排列出来的所有字符串abc,acb,bac,bca,cab和cba。

输入描述:

输入一个字符串,长度不超过9(可能有字符重复),字符只包括大小写字母。

递归法求全排列，思路：对字符串a_b_c有

  • Perm(a_b_c)= a_Perm(b_c)+ b_Perm(a_c)+ c_Perm(a_b)，
  • Perm(b_c)=b_Perm(c)+c_Perm(b)，
  • Perm(a)=a。

其中加号+表示添加到序列组成的列表里。

难点在于字符序列的重复元素会带来冗余排列要如何避免。例如Perm(a_b_b)=a_Perm(b_b)+2b_Perm(a_b)产生了两个b_Perm(a_b)，原因在于先后有两个b被从a_b_b里取出。解决方案：

  • 既然原因在于重复的元素先后从序列里取出，那么只要给取出的元素做个记录，再次访问时能够识别出来，跳过即可。
1
2
3
4
5
6
7
8
9
10
11
12
def Perm(s):
    if not isinstance(s, str) or len(s) == 0:
        return []
    elif len(s) == 1:
        return [s]
    else:
        r = []
        for i in range(len(s)):
            if s[i] not in s[:i]:# s[:i]是已经取出过的元素，如果s[i]在里面出现过则跳过
                myset = [s[i]+child for child in Perm(s[:i]+s[i+1:])]
                r.extend(myset)
        return r

上述实现版本有两个不完美的地方：

  • 低效的递归
  • 输出的全排列不是字典序的

根据一个字符串序列，有效的计算其下一个字典序列的方法是存在的。这不但能避免低效的递归，而且能按字典序输出全排列。

计算下一个字典序的方法：

  • 从后向前找第一对相邻的递增元素，称前一个为替换数a，其位置为替换点。
  • 再从a的后面找一个比它大的最小元素b，如果有多个元素值与b相等，就选择最右边的那个（其实，b是从后边开始的第一个大于a的元素），交换二者位置。。
  • 将替换点之后（不包括替换点）的右子序列的元素反转。

如下版本的代码，接收参数为字符串，是不可变对象，因此把字符串转换为数组之后再操作，最后再变回字符串。有用到冒泡排序将输入转换成其最小字典序。主题部分用了一个循环，从最小字典序依次产生不重复的序列，直到最大字典序。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
def Perm(arr):
    #arr是字符串
    def bubble_sort(arr):
        l = len(arr)
        for i in range(l-1):
            for j in range(i+1,l):
                if arr[i] > arr[j]:
                    arr[i],arr[j] = arr[j],arr[i]
    
    if isinstance(arr,str):
        arr = [char for char in arr]
    bubble_sort(arr) # 得到最小字典序
    
    if len(arr) == 0:
    return []
    result = [''.join(arr)]
    is_next = True # 是否还有更大的字典序，用来判断是否结束
    while is_next:
        is_next = False
        for i in range(len(arr)-2,0-1,-1):
            if arr[i] < arr[i+1]: # 找到替换数和替换点
                is_next = True
                for j in range(len(arr)-1,i,-1):
                    if arr[i] < arr[j]:
                        arr[i], arr[j] = arr[j], arr[i]
                        arr[i+1:] = arr[i+1:][::-1] # 反转替换点之后的右子序列
                        result.append(''.join(arr))
                        break
                break
    return result