遇到一个很有意思的算法问题:
1-9个数，组成不重复的9位数，想所有的组合的情况输出
这个算法可以用循环或递归的方式做。
递归
主要思路就是：
将1-9大问题化成小问题
是不是解决1-2组合两位数即可得出1-3的结果
1-1组合一位数：
1
1-2组合两位数：
1 2
2 1
1-3组合三位数：
3 1 2
3 2 1
1 3 2
2 3 1
1 2 3
2 1 3
由此我们可以看出1-2只是在1-1的结果之上将2插入
同理1-3也是在1-2的结果（1 2 ； 2 1）中，将3插入
由此1-9就是在1-8的结果中将9插入得出
代码如下：
python的递归实现：
def dg(arr, l):
if l == 0:
yield arr
else:
end_arr = arr[-l:]
start_arr = arr[0:-l]
for i in dg(end_arr, l - 1):
for j in range(len(i) + 1):
tmp_arr = i.copy()
tmp_arr.insert(j, ' '.join(start_arr))
yield tmp_arr
arr = ["1", "2", "3","4", "5", "6","7", "8", "9"]
for i in dg(arr, len(arr) - 1):
print(' '.join(i))
python的循环实现：
arr = ["1", "2", "3","4", "5", "6","7", "8", "9"]
arr_result = [[arr[0]]]
for i in arr[1:]:
tmp_arr = arr_result.copy()
arr_result.clear()
for j in tmp_arr:
for k in range(len(j) + 1):
tmp_copy_arr = j.copy()
tmp_copy_arr.insert(k, ' '.join(i))
arr_result.append(tmp_copy_arr)
for _ in arr_result:
print(' '.join(_))
