组合的递归和迭代算法

递归解法

def comb(l, k, j, m, res):
    # we j start at 0
    n = len(l)
    if j >= len(l):
        print(list(filter(None, res)))
        return
    if m < k:
        res[j] = l[j]
        comb(l, k, j + 1, m + 1, res)
    if (k - m) < (n - j):
        res[j] = None
        comb(l, k, j + 1, m, res)

comb([1, 2, 3, 4, 5], 3, 0, 0, [None for i  in range(5)])

迭代解法

通用的打印方法

def print_res(l, res, k):
    ans = [l[res[i] - 1] for i in range(1, k+1)]
    print(ans)

def comb_iter1(l, k, j, res):
    n = len(l)
    while True:
        j = k
        print_res(l, res, k)
        while res[j] == n - k + j:
            j = j - 1
        res[j] = res[j] + 1
        if j == 0:
            break
        for i in range(j + 1, k + 1):
            res[i] = res[i-1] + 1

comb_iter1([1, 2, 3, 4, 5], 3, 3, list(range(0, 5)))

书中说 : The while loop of Algorithm  can be eliminated by making j a global variable (initialized to k) and observing that the rightmost changeable position is k if res[k] < n and is one less than its previous value if res[k] = n.

优化版：

def comb_iter2(l, k, j, res):
    # init item in res < 0
    n = len(l)
    while True:
        print_res(l, res, k)
        res[j] = res[j] + 1 # 直接开始加 
        for i in range(j + 1, k + 1):
            res[i] = res[i-1] + 1
        if j == 0:
            break
        if res[k] < n:
            j = k  # < 5 说明可以继续从这里加
        else:
            # 加到 5 之后，第一位需要舍弃 需要在下一轮 + 1
            j = j - 1

comb_iter2([1, 2, 3, 4, 5], 3, 3, list(range(0, 5)))

问题：

1. 为什么要传 list(range(0, 5))?

2. res[i] = res[i-1] + 1 是在做什么？

3. res[j] = res[j] + 1 是在做什么？

不准备做详细解释。如果对照输出和课本理解此算法，自己会发现其精妙之处。