Origianl Problem
Give you a number $n$, print the full permutation of the number list $(1\to n)$.
My Solution
Here we use recursion. My source code is listed below:
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
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
#!/usr/bin/env python3
"""
Permutation with recursion
Written by Polly Zhou, Tsinghua University
E-mail:
pollyjoe2003@gmail.com
Solution:
Fix one element, and permute the remaining elements.
Acknowledgement:
CSDN blog: Output the Full Permutation of A List
URL: https://blog.csdn.net/yezi1993/article/details/84143458
"""
################################
# Generate the number list: 1--n
################################
def list_generator(n):
num_list = []
num = int(n)
for i in range(0,num):
num_list.append(str(i + 1))
return num_list
####################################################
# Permutation
# We use recursion to solve the problem:
# For each trial, pick one element as the first one,
# and permute the remaining elements
####################################################
def permutation(input_list):
result_list = []
length = len(input_list)
if length == 1:
result_list.append(input_list)
return result_list
else:
for i in range(0, length):
# Fix element [i]
temp_list = input_list[:i] + input_list[i+1:]
c = input_list[i]
per_list = permutation(temp_list)
result_list += [[c] + j for j in per_list]
return result_list
##################
# Print the result
##################
def perm_print(result_list):
for i in range(0, len(result_list)):
output_str = " ".join(result_list[i])
print(output_str)
if __name__ == '__main__':
input_n = input()
original_list = list_generator(input_n)
output_list = permutation(original_list)
perm_print(output_list)
If we sometimes see a function calling itself inside itself, that is recursion.
My idea:
Recursion is an important way of thinking.
The main idea of recursion is to imitate. Because each time you call the function inside itself, it is solving the same problem, just with a lower dimension.
Therefore, for this problem, we can assign one element as the first one, do the permutation to the remaining elements, put all the situations together and we will get a full permutation.