算法小例

遇到一个很有意思的算法问题:
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(_))