# This is a sample Python script.
import sys
# Press Shift+F10 to execute it or replace it with your code.
# Press Double Shift to search everywhere for classes, files, tool windows, actions, and settings.
# def to_str(n, base):
# convert_string = "0123456789ABCDEF"
# if n < base:
# return convert_string[n]
# else:
# return to_str(n//base, base) + convert_string[n % base]
# frthonds3.basic import Sta
# import turtle
#
# def draw_spiral(my_tutle, line_len):
# if line_len > 0:
# my_tutle.forward(line_len)
# my_tutle.right(90)
# draw_spiral(my_tutle, line_len-50)
#
#
# my_turtle = turtle.Turtle()
# my_win = turtle.Screen()
# draw_spiral(my_turtle, 100)
# my_win.exitonclick()
# 用递归调用实现指数函数
# def exponentByIteration(a, n):
# result = 1
# for i in range(n):
# result *= a
# return result
#
# print(exponentByIteration(3, 6))
# def exponentByRecursion(a, n):
# if n == 1:
# return a
# elif n % 2 == 0:
# result = exponentByRecursion(a, n // 2)
# return result * result
# elif n % 2 == 1:
# result = exponentByRecursion(a, n // 2)
# return result * result * a
#
# print(exponentByRecursion(3, 6))
# 解释了用递归调用比用迭代调用性能高的多
# 每个递归算法都可以转换成等效的迭代算法，根据递归算法提供的思路，实现另一种迭代式的指数计算函数
# 本质上将需要计算的一系列操作存到了列表中
# def exponentWithPowerRule(a, n):
# # 第一步判断需要执行的是什么运算
# opStack = []
# while n>1:
# if n % 2 == 0:
# opStack.append("square")
# n = n//2
# elif n % 2 == 1:
# n -= 1
# opStack.append("multiply")
# # 第二步， 按照逆序依次执行这些计算
# result = a
# while opStack:
# op = opStack.pop()
#
# if op == "multiply":
# result *= a
# elif op == "square":
# result *= result
# return result
# print(exponentWithPowerRule(3, 6))
# 2023/12/19 递归法实现反转字符串
# def rev(theString):
# if len(theString) == 0 or len(theString)==1:
# # 基本情况
# return theString
# else:
# head = theString[0]
# tail = theString[1:]
# return rev(tail) + head
# print(rev("dc_lover"))
# 递归法 判断回文字符串
# def isPalindrome(theString):
# if len(theString) == 0 or len(theString) == 1:
# return True
# else:
# head = theString[0]
# middle = theString[1:-1]
# last = theString[-1]
# return head == last and isPalindrome(middle)
# print(isPalindrome("dc_loverrevol_cd"))
# print(isPalindrome("zophie"))
# 树的前序遍历
# root = {'data':'A', 'children': [{'data':'B', 'children':
# [{'data':'D','children':[]}]}, {'data':'C', 'children':
# [{'data':'E','children':[{'data':'G','children':[]},
# {'data':'H','children':[]}]}, {'data':'F','children':[]}]}] }
#
# def preorderTraverse(node):
# print(node['data'], end='')
# if len(node['children']) > 0:
# for child in node['children']:
# preorderTraverse(child)
# return
# preorderTraverse(root)
# 前序遍历和创建这颗树的顺序好像一样
# 树的后序遍历
# root = {'data':'A', 'children': [{'data':'B', 'children':
# [{'data':'D','children':[]}]}, {'data':'C', 'children':
# [{'data':'E','children':[{'data':'G', 'children':[]},
# {'data':'H','children':[]}]}, {'data':'F', 'children':[]}]}]}
#
# def postorderTraverse(node):
# for child in node['children']:
# postorderTraverse(child)
# print(node['data'], end='')
# return
# postorderTraverse(root)
# root = {'name': 'Alice', 'children': [{'name': 'Bob', 'children':
# [{'name': 'Darya', 'children': []}]}, {'name': 'Caroline',
# 'children': [{'name': 'Eve', 'children':[{'name':'Gonzalo',
# 'children':[]}, {'name':'Hadassah', 'children':[]}]}, {'name':'Fred','children':[]}]}]}
#
# def find8LetterName(node):
# print('Visiting node' + node['name'] + '...')
#
# print("checking if " + node['name'] + ' is 8 letters...')
# # 这里是基本情况
# if len(node['name']) == 8:
# return node['name']
#
# # 该条判断语句的作用是 判定当前节点存在子树
# if len(node['children']) > 0:
# for child in node['children']:
# returnValue = find8LetterName(child)
# if returnValue != None:
# return returnValue
#
# return None
#
# print(str(find8LetterName(root)))
# root = {'data':'A', 'children': [{'data':'B', 'children':
# [{'data':'D','children':[]}]}, {'data':'C', 'children':
# [{'data':'E','children':[{'data':'G','children':[]},
# {'data':'H','children':[]}]}, {'data':'F','children':[]}]}] }
#
#
# def getDepth(node):
# if len(node['children']) == 0:
# return 0
# else:
# maxChildDepth = 0
# for child in node['children']:
# childDepth = getDepth(child)
# if childDepth > maxChildDepth:
# maxChildDepth = childDepth
# return maxChildDepth + 1
#
# print(getDepth(root))
# 递归算法实现二分
# def binarySearch(needle, haystack, left=None, right=None):
# if left is None:
# left = 0
# if right is None:
# right = len(haystack)-1
#
# if left > right:
# return None
# mid = (left+right)//2
# if needle == haystack[mid]:
# return mid
# elif needle < haystack[mid]:
# return binarySearch(needle, haystack, left, mid-1)
# elif needle > haystack[mid]:
# return binarySearch(needle, haystack, mid+1, right)
#
# print(binarySearch(13, [1,4,8,11,13,16,19,19]))
# 快速排序
# def quicksort(items, left=None, right=None):
# if left is None:
# left = 0
# if right is None:
# right = len(items)-1
#
# if right <= left:
# return
#
# i = left
# pivotValue = items[right]
#
# for j in range(left, right):
# if items[j] <= pivotValue:
# items[i], items[j] = items[j], items[i]
# i += 1
#
# items[i], items[right] = items[right], items[i]
#
# quicksort(items, left, i-1)
# quicksort(items, i+1, right)
#
#
# myList = [0, 7, 6, 3, 1, 2, 5, 4]
# quicksort(myList)
# print(myList)
# 递归的获取全排列
def getPerms(chars, indent=0):
# print('.' * indent + 'Start of getPerms ("' + chars + '")')
if len(chars) == 1:
# print('.' * indent + 'When chars = "'+ chars + '" base case returns', chars)
return [chars]
permutations = []
head = chars[0]
tail = chars[1:]
tailPermutations = getPerms(tail, indent+1)
for tailPerm in tailPermutations:
for i in range(len(tailPerm)+1):
newPerm = tailPerm[0:i] + head + tailPerm[i:]
# print('.'*indent + 'New permutation:', newPerm)
permutations.append(newPerm)
return permutations
print(getPerms('ABCD'))