PROGRAMMING:Output permutation

Input the integer n (3 < = n < = 7), write the program, output the full arrangement of '1,2,..., n' integers, and output them in dictionary order.
###Input format:
Enter a positive integer n on one line.
###Output format:
Output the full permutation of 1 to N in dictionary order. Each permutation occupies one line, and there is no space between the numbers.
###Input example:
Here is a set of inputs. For example:
```in
three
```
###Output example:
The corresponding output is given here. For example:
```out
one hundred and twenty-three
one hundred and thirty-two
two hundred and thirteen
two hundred and thirty-one
three hundred and twelve
three hundred and twenty-one
```







answer：If there is no answer, please comment
```
def InsertCharToStr(STR,CHAR):
arr =[]
s_ len = len(STR)
index =0
while index <= s_ len:
#Split string
arr.append(STR[:index]+CHAR+STR[ index:s_ len])
index = index + 1
return arr
def InsertCharToArray(array,CHAR):
index = 0
re_ array = []
while index < len(array):
re_ array = re_ array + InsertCharToStr(array[index],CHAR)
index = index + 1
return re_ array
def Perm(STR):
resultlst = [STR[0]]
for item in STR[1:]:
resultlst = InsertCharToArray(resultlst,item)
return resultlst
n=int(input())
s="".join([chr(i+ord("0")) for i in range(1,n+1)])
lst=Perm(s)
lst.sort()
for ele in lst:
print(ele)
```