数组穷举全排列问题

最近看到这样一个问题，有n个位置，每个位置可以放 +-*/ 符号中的任意一个，要求输出所有的放置情况。

举个例子，假设n为4，下面几种都是可以放置的情况：

+ + + +
+ - + +
+ + - +
+ - * /

这几种放置方式都是可以的。

我首先想到的是，这个问题类似于八皇后问题，只不过没有回溯条件，既然没有回溯条件，不如就在一个while循环里不断生成当前长度的所有子集合，于是就写出了下面的算法：

def func1():
    chars = ['+', '-', '*', '/']
    length = 4

    i = 0
    result = [[]]
    while i < length:
        tmp = []
        for curr_set in result:
            for char in chars:
                tmp.append(curr_set + [char])
        result = tmp
        i += 1
    return result

当然这种方法是不够优雅的，因为占用了很多内存，且需要一定思考量。

于是有人指出，用进制的思想来写，+-*/ 如果代表0,1,2,3的话，刚好可以用4进制的数字来表示，于是想到了用4进制来实现，于是有了下面的代码。

def func2():
    replace_map = {
        '0': '+',
        '1': '-',
        '2': '*',
        '3': '/'
    }

    def trans_4_scale(n, fill_lenth):
        result = []
        curr_num = n
        while curr_num > 0:
            mod = curr_num % 4
            curr_num >>= 2
            result.append(str(mod))
        result.reverse()
        result_str = ''.join(result).zfill(fill_lenth)
        for k, v in replace_map.items():
            result_str = result_str.replace(k, v)
        result = list(result_str)
        return result

    for i in range(4 ** 4):
        yield trans_4_scale(i, 8)

这种方法就比之前优雅了很多，不但节省了内存，而且更直观易懂，不过没有对比就没有伤害，有人提出4进制用2进制的2位就可以表示了，而且关于二进制有很多现成的算法，不如就把算法改成2进制吧，改完之后，果然清晰了很多，下面是改进代码。

def func3():
    replace_map = {
        '00': '+',
        '01': '-',
        '10': '*',
        '11': '/'
    }

    def dec(val):
        v = f'{val:0b16}'
        return [replace_map[v[i:i+2]] for i in range(0, len(v), 2)]
    for i in range(4 ** 4):
        yield dec(i)

其实我觉得上面的算法已经足够完美了，但是我还是想到了另一种解法，顺便也提一下，灵感来自于数组全排列的递归算法，数组初始化全为+，然后从固定第一位分别为+-*/，并进入子问题，子问题结束后将当前位替换回+，保证子问题执行完后，父问题不受影响，于是写出了下面的代码：

def func4():

    start_arr = ['+', '+', '+', '+']

    def all_sort(arr, curr_index, length):
        if curr_index == length:
            yield arr
        else:
            yield from all_sort(arr, curr_index+1, length)
            for elm in ['-', '*', '/']:
                arr[curr_index] = elm
                yield from all_sort(arr, curr_index+1, length)
            arr[curr_index] = '+'
    for arr in all_sort(start_arr, 0, 4):
        yield arr

这样就完成了这个问题的讨论，没想到这样的一个问题，有这么多解法。

最后编辑于：2020.09.02 22:48:17