全排列的递归和迭代算法

递归版 参考： https://dotkay.github.io/2017/10/06/computing-permutations/

def permute_rec(s, start, end):
    c = []
    if start == end:
        return [list(s)]
    else:
        for i in range(start, end + 1):
            s[start], s[i] = s[i], s[start]  # 不交换，依次和后续每个元素交换
            t = permute_rec(s, start + 1, end)
            c.extend(t)
            s[start], s[i] = s[i], s[start]
        return c

迭代版和快速排序的迭代版几乎是一样的。 https://www.allstoalls.com/blog/blog/3

def permute_iter(s):
    c = []
    lo = 0
    hi = len(s) - 1
    range_queue = Queue()
    range_queue.put([lo, hi, list(s)])
    while not range_queue.empty():
        lo, hi, r = range_queue.get()
        if lo == hi:
            c.extend([r])
        for i in range(lo, hi+1):
            r[lo], r[i] = r[i], r[lo]   # 不交换，依次和后续每个元素交换 和递归版本的概念一样
            range_queue.put([lo+1, hi, list(r)])
            r[lo], r[i] = r[i], r[lo]
    return c