Combinatorial Generation 这书读的还是太慢，要想弄懂还是要下大功夫。从原书的得到
递归版：
def subset_rec0(l, k, res):
if k >= len(l):
print(list(filter(None, res)))
return
res[k] = None
subset_rec0(l, k + 1, res)
res[k] = l[k]
subset_rec0(l, k + 1, res)
#这样使用
subset_rec0([1, 2, 3], 0, [None, None, None])
相关理解：
书中用 0 1 的 lexicographic order 来解释。得到输出结果 （为了说明算法的简便， 假定数组元素 不为 0， 不重复）
[]
[3]
[2]
[2, 3]
[1]
[1, 3]
[1, 2]
[1, 2, 3]
从 000 开始 ，后面慢慢加 1。 000->001->010->011->100->101->110->111
前四个就是最高位位取零之后的总的递归结果。比较好理解。
产生对应的迭代版。书中 Next 算法，假定最高位为 0，是没有必要的。只需变书中 k = 0 为 k < 0 可以直接产生整体结果。
def subset_iter0(l, res):
length = len(l)
while True:
print(list(filter(None, res)))
k = length - 1
while res[k]:
res[k] = None
k -= 1
if k < 0:
break
res[k] = l[k]
subset_iter0([1, 2, 3], [None, None, None])
算法解释起来比较费劲，只能想象 000->001->010->011->100->101->110->111 这个过程。 每次迭代都从 length -1 开始。认为 length-1 是低位。里面的 while 和 res[k] = [k] 表示了一种 + 1 的动作。 低位变为 0 ， 高位 + 1 。 01 变为 10。 这就是 为什么 res[k] = None 的原因。（牢记 length-1是低位, 所以 k -= 1 是为了进位, res[k] = l[k] 变 1，这里表示对应位置的元素参与结果）
解释起来还是很不好理解。
正式因为不好理解，所以需要反复练习。为什么要用 rec0 和 iter0 。因为还有同类项。
很明显递归的方法中，交换一下赋值顺序也是完全正确的解法：
def subset_rec1(l, k, res):
if k >= len(l):
print(list(filter(None, res)))
return
res[k] = l[k]
subset_rec1(l, k + 1, res)
res[k] = None
subset_rec1(l, k + 1, res)
subset_rec1([1, 2, 3], 0, [None, None, None])
得到这样的结果
[1, 2, 3]
[1, 2]
[1, 3]
[1]
[2, 3]
[2]
[3]
[]
这样看起来就是完全逆向的计算的感觉。 从 111 -> 110 -> 101 -> 100 ->011-> 010->001->000
这就是减一。同样也是有迭代的解法。
def subset_iter1(l, res):
length = len(l)
while True:
print(list(filter(None, res)))
k = length - 1
while k < length and (not res[k]):
res[k] = l[k]
k -= 1
if k < 0:
break
res[k] = None
subset_iter1([1, 2, 3], [1, 2, 3])
这里 length - 1 依旧是低位。 里面的 while 和 res[k] = [k] 最后 res[k] = None 表示了一种 - 1 的动作。 低位变为 1 ， 高位 0 。 10 变为 01。
这个解法应该是很容易从 subset_iter0 演变过来。
一不做而不休，我想到了一种对偶的概念。 length - 1 可以变成最高位 递归解法都是从 0 到 k 。我们可以从 k 到 0 。
递归版
def subset_rec2(l, k, res):
if k < 0:
print(list(filter(None, res)))
return
res[k] = None
subset_rec2(l, k - 1, res)
res[k] = l[k]
subset_rec2(l, k - 1, res)
subset_rec2([1, 2, 3], 2, [None, None, None])
迭代版
def subset_iter2(l, res):
length = len(l)
while True:
print(list(filter(None, res)))
k = 0
while k < length and res[k]:
res[k] = None
k += 1
if k == length:
break
res[k] = l[k]
subset_iter2([1, 2, 3], [None, None, None])
迭代和递归相对前面的前两版改动非常小。得到结果
[]
[1]
[2]
[1, 2]
[3]
[1, 3]
[2, 3]
[1, 2, 3]
从 000 -> 100 -> 010 -> 110 -> 001-> 101 ->011->111 。所以我们看到还是 一直加一。
那么同理。一直减一的 ： 111 -> 011 -> 101 -> 001 -> 110-> 010 ->100->000
[1, 2, 3]
[2, 3]
[1, 3]
[3]
[1, 2]
[2]
[1]
[]
递归版
def subset_rec3(l, k, res):
if k < 0:
print(list(filter(None, res)))
return
res[k] = l[k]
subset_rec3(l, k - 1, res)
res[k] = None
subset_rec3(l, k - 1, res)
subset_rec3([1, 2, 3], 2, [None, None, None])
迭代版
def subset_iter3(l, res):
length = len(l)
while True:
print(list(filter(None, res)))
k = 0
while k < length and (not res[k]):
res[k] = l[k]
k += 1
if k == length:
break
res[k] = None
subset_iter3([1, 2, 3], [1, 2, 3])
再不能创造知识的情况下，不停的重复，好像意义不是很大。 整个 加一， 减一， 递归，迭代， 高位， 低位，及其对偶的概念，重复，我感觉自己更理解了这个算法的本质。