python3實(shí)現(xiàn)字符串的全排列的方法(無(wú)重復(fù)字符)

最近在學(xué)一些基礎(chǔ)的算法，發(fā)現(xiàn)我的數(shù)學(xué)功底太差勁了，特別是大學(xué)的這一部分，概率論、線性代數(shù)、高數(shù)等等，這些大學(xué)學(xué)的我是忘得一干二凈（我當(dāng)時(shí)學(xué)的時(shí)候也不見(jiàn)得真的懂），導(dǎo)致現(xiàn)在學(xué)習(xí)算法，非常的吃力。唉！不說(shuō)了，補(bǔ)習(xí)中。。。

拋出問(wèn)題

求任意一個(gè)字符串的全排列組合，例如a='123',輸出 123，132，213，231，312，321。（暫時(shí)假定字符串沒(méi)有重復(fù)）

解決方案

目前有兩種解決的方法

方法一：

def str_sort(s=''):
  if len(s) <= 1:
    return [s]
  str_list = []
  for i in range(len(s)):
    for j in str_sort(s[0:i] + s[i + 1:]):
      str_list.append(s[i] + j)
  return str_list


str_list = str_sort('abc')
print(len(str_list), str_list)

這種理解起來(lái)非常好理解，就是循環(huán)遍歷每個(gè)字符，讓每個(gè)字符打頭，然后繼續(xù)遞歸遍歷后邊的字符

方法二：

#字符串任意兩個(gè)位置字符交換
def str_replace(str, x, y):
  if x == y:
    return str
  x_val = str[x:x+1]
  y_val = str[y:y+1]
  if x < y:
    str = str[0:x] + y_val + str[x+1:y] + x_val + str[y+1:len(str)]
  else:
    str = str[0:y] + x_val + str[y+1:x] + y_val + str[x+1:len(str)]
  return str
#遞歸求結(jié)果
def str_sort(str,x):
  if x == len(str):        #當(dāng)x為字符串的最大長(zhǎng)度時(shí)返回當(dāng)前字符交換的結(jié)果
    global str_list
    str_list.append(str)
    return
  for i in range(x,len(str)):
    str = str_replace(str,i,x) #遞歸遍歷第i個(gè)字符，
    str_sort(str,x+1)
    str = str_replace(str,x,i) #恢復(fù)字符串原來(lái)的順序，便于下次遍歷
s = 'abc'
global str_list
str_list = []
str_sort(s,0)
print(len(str_list), str_list)

這種方法在求解的思路上就已經(jīng)有了很大的提升，不是像上一個(gè)靠“蠻力”去解決問(wèn)題，這是遞歸的一種方式，大概原理就是，先保持前I個(gè)字符不變，遍歷交換后邊的字符，這樣一直遞歸到，最后兩個(gè)字符，然后再返回去改變倒數(shù)第三個(gè)字符，再次遍歷后邊的兩位，直到三個(gè)字符的全部輸出，也就是這樣的順序，

第一次輸出　　X(n),X(n-1),X(n-2),......X(3),X(2),X(1)

第二次輸出　　X(n),X(n-1),X(n-2),......X(3),X(1),X(2)

第三次輸出　　X(n),X(n-1),X(n-2),......X(2),X(3),X(1)

第四次輸出　　X(n),X(n-1),X(n-2),......X(2),X(1),X(3)

......

這個(gè)可能我講的不是特別清楚，理解起來(lái)不是特別容易，這種方式經(jīng)過(guò)我的測(cè)試，發(fā)現(xiàn)他更費(fèi)時(shí)。

自我感覺(jué)兩種方法區(qū)別不大，原理上是一樣的，都是先確定前面的部分，處理后邊的，從后往前走。

以上就是本文的全部?jī)?nèi)容，希望對(duì)大家的學(xué)習(xí)有所幫助，也希望大家多多支持億速云。