小郑之家~

典例1


def main(s='abc'):

n = len(s)
assert n>=1

if n==1:
return [s]

ret = []
a = [0]*(n+1)
book = [0]*(n+1)

def dfs(step):
# 保存的条件是当所有的字符串都已经放好了
if step==n+1:
ret.append(a[1:])

for i in range(1,n+1):   # 每次都会把所有的字符遍历一次，看看有没有visited, 如果没有就参观.
if book[i]==0:
a[step] = s[i-1]
book[i] = 1

dfs(step+1)
book[i] = 0

return
dfs(1)
ret = ["".join(x) for x in ret]  # 刚才是用列表来保存的，现在用字符串
return ret

print(main())



def main(n):

assert n>=1

if n==1:
return [1]

ret = []
a = [0]*(n+1)
book = [0]*(n+1)

def dfs(step):
if step==n+1:
ret.append(a[1:])

for i in range(1,n+1):
if book[i]==0:
a[step] = i
book[i] = 1

dfs(step+1)
book[i] = 0

return

dfs(1)
return ret

print(main(3))



def fun():

def permuteDFS(nums, start):
# 每次是走到最后的时候才会append
if start >= len(nums):
print(nums)

for i in range(start, len(nums)):
nums[start], nums[i] = nums[i], nums[start]
permuteDFS(nums, start+1)
nums[start], nums[i] = nums[i], nums[start]

permuteDFS(list(range(1,4)), 0)

fun()
~



def fun2():

ret = []
def permuteDFS(nums, start, ret):
# 每次是走到最后的时候才会append
if start >= len(nums):
ret.append(nums)

for i in range(start, len(nums)):
nums[start], nums[i] = nums[i], nums[start]
permuteDFS(nums, start+1, ret)
nums[start], nums[i] = nums[i], nums[start]

permuteDFS(list(range(1,4)), 0, ret)
print(ret)
return ret



ret.append(copy.copy(nums))
ret.append(nums[:])



递归法2


import copy

def permute(nums):

if len(nums) == 1:
return [nums]

first = nums[0]
nums = nums[1:]

words = permute(nums)
# 然后让first去insert
ret = []
for x in words:
for i in range(len(x)+1):
x.insert(i, first)
y = copy.copy(x)  # 如果不copy的话，因为后面又把这个删除了所以没用
ret.append(y)
del(x[i])  # 是为了让下一次insert其它的位置

return ret

print(permute([1,2,3]))



def permuteString(s):
if len(s) == 1:
return [s]

first = s[0]
s = s[1:]

words = permuteString(s)
ret = []
for x in words:
for i in range(len(x)+1):
x = x[:i] + first + x[i:]
ret.append(x[:])
x = x[:i] +x[i+1:]
return ret

print(permuteString("abc"))