两两配对！

题图from BetterProgramming

最近继续搞LDR的事情。然后遇到了一个问题：假设有一个列表[1, 2, 3, 4]，我需要将列表中的元素两两分组，组成元素对；其中每一个元素只出现一次。我需要的是在此条件下出现的所有可能组合，也就是说输出应该是另一个列表：[[(1,2), (3,4)], [(1,3), (2,4)], [(1,4), (2,3)]]。那么应该怎么实现？

本来我以为这种基础的需求应该有现成的包可以用，网上多数也给了itertool.combination这个函数。但是这个函数的作用是列出所有两两（或者其他数量）的组合，元素不止出现一次，所以并不符合我的需求。我也想过自己写个轮子，觉着应该要用迭代；但是因为自己技艺不精只有个大概思路。最后在这里找到了别人写的code，记录如下：

def all_pairs(lst):
    if len(lst) < 2:
        yield []
        return
    if len(lst) % 2 == 1:
        # Handle odd length list
        for i in range(len(lst)):
            for result in all_pairs(lst[:i] + lst[i+1:]):
                yield result
    else:
        a = lst[0]
        for i in range(1,len(lst)):
            pair = (a,lst[i])
            for rest in all_pairs(lst[1:i]+lst[i+1:]):
                yield [pair] + rest

非常简单的一个小生成器，但是我觉得写法非常精妙，所以又花了两个小时学习了一下生成器的相关知识，看懂了这段代码，也一并记录下来。

基本思路

从这里开始，为了简化情况，假设输入的列表都是从1开始增大的自然数，长度为\(N\)。

既然用上了迭代，那么基本思路和我想的是差不多的。我们需要分情况讨论，并且每次迭代只进行一步：

当输入列表长度小于2时：
- 这个时候根本没有组合可以产生，那么返回一个空列表
当输入列表长度为奇数时：
- 长度为奇数代表着一定有某一个元素不能形成组合，而这个元素可能是列表里面的任何一个元素。所以这时先把这个元素挑出来从列表中去掉，然后将剩下的列表(lst[:i] + lst[i+1:])重新放入函数中。这个时候的输入列表长度为偶数，放到下一个情况讨论。
当输入列表长度为偶数时：
- 从列表中挑出两个元素并组合成元组；
- 将这两个元素在列表中去掉
- 将新的列表作为输入放到函数中

这样的思路就符合迭代的思想了。

但是这里（对我来说）有两个难点：

如何在步骤3中遍历所有可能的情况？
当输入列表的长度大于4时，如果先挑出了(1,2)，则后面有不止一种可能性，在程序中如何将这些可能性都与(1,2)联系起来？要解决这两个问题，要理解迭代的作用、以及Python中生成器的特性。

问题1

迭代器的作用本身就是为了简化每一次迭代所要做的事情，所以这个问题的答案是：在每一次迭代中不需要遍历所有可能的情况，只需遍历下一层迭代不能遍历的情况。假设输入列表是[1, 2, 3, 4, 5]，第一次迭代的时候取了(1, 2)，第二次迭代的时候因为剩下了[3, 4, 5]，这个时候是可以取到(3, 4)的，所以在第一次迭代中不需要取到(3, 4)。那么第一次（实际上是每一次）迭代中需要遍历什么组合呢？因为每一次迭代实际上是取走了列表中的两个元素，所以迭代只需要遍历下层迭代不能取到的元素即可。最方便的做法是，固定组合中的一个数（比如(1, 2)中的1），遍历另一个数（比如(1, 2)中的2可以为3、4和5）。这样遍历就保证了下层迭代的时候永远和1无关，同时在这一层迭代中遍历了与1有关的所有组合。更进一步说，既然一个迭代层中只需要取一个固定的数，那么干脆就取输入列表中的第一个数来固定就好了。这也是程序中a = lst[0]，组合的第一个数永远是是输入列表的第一个数的原因。反正到下一层时第一个数就变了，所有的组合总是能被取到的。

问题2

这个问题就要利用到生成器的特性了，也是我觉得这个生成器最精妙的地方。这里每次涉及到输出的时候用的都是yield，它使得这个函数变成了生成器。每次程序执行到yield时都会暂停，回到上一层迭代器；同时本层迭代器的所有情况被保留（或者说冻结），等待下一次被引用时继续。这个特性就使得每次迭代到末端（基本思路中的情况1）时，从最底层开始、每一层迭代都会遇到yield。在迭代中被抽出的各个pair就会通过[pair] + rest累积起来，组成一组元素对。同时这些pair在此刻的值会被yield保存起来，下次用到的时候仍会保持原状，或者被情况3的循环更新为下一组。这个特性既保证了每一组元素对集合都能被输出，又不会出现输出完之后不知道下次该遍历哪个元素的情况。通过下面的例子应该可以更好地看出来这些yield是怎么运作的。

运行实例：6元素列表

从程序中可以看出来，奇数元素列表实际上是回到偶数元素列表的情况，所以只要掌握了偶数元素列表的情况即可，这里也只举偶数的例子。

这里我们的输入列表为[1, 2, 3, 4, 5, 6]。
因为是偶数列表，程序会直接进入到第二个if判断的else部分。
这个部分首先将第一个元素拿出来，然后对第2到第6个元素进行循环。
循环的第一次取出了第二个元素2，与1组成了(1, 2)这个元素对。
这个时候剩下来的元素是[3, 4, 5, 6]，它们作为新的输入列表进入第二层迭代。
第一层迭代停在了for rest in all_pairs(lst[1:i]+lst[i+1:]):中
- 同理，第二层迭代首先取出了3，然后循环的第一次取出了4组成了(3, 4)
- 剩下的[5, 6]进入第三层迭代。
- 第二层迭代停在了for rest in all_pairs(lst[1:i]+lst[i+1:]):中
  - 继续同理，在第三层迭代中(5, 6)被取了出来。
  - 此时因为列表长度已经是2了，for i in range(1,len(lst)):只运行一次，并没有循环。
  - 但是for rest in all_pairs(lst[1:i]+lst[i+1:]):还是被执行了；程序进入第四层迭代。
    - 第四层的迭代输入数组为空，直接yield []
    - 并且由于后面接的是return，本层的生成器直接结束，不再迭代了。
  - 这个时候程序回到了第三层的迭代中，获取了rest = []的结果
  - 紧接着yield [pair] + rest被执行，实际上相当于返回了[(5, 6)]
  - 第三层迭代停在了yield [pair] + rest，回到第二层迭代。
- 类似的，第三层迭代中的结果和第二层的结果合并，第二层的yield [pair] + rest被执行，返回了[(3, 4), (5, 6)]，第二层迭代器暂停
继续类似，[(1, 2), (3, 4), (5, 6)]被第一层返回，第一层迭代器暂停。

诶怎么都暂停了？那我们只取出了第一种组合而已，哪来的其他结果？实际上这是运行next(all_pairs([1, 2, 3, 4, 5, 6]))的结果。这个时候整个生成器只完成了一步；再次运行next的话，会运行第二步。要注意这个时候三层的迭代器都停在了yield [pair] + rest这个地方。

我们继续：

第一层迭代器此时的pair为(1, 2)；它处于for rest in all_pairs(lst[1:i]+lst[i+1:]):的循环中，继续运行将恢复第二层迭代器的运行。
- 第二层迭代器此时的pair为(3, 4)；它处于for rest in all_pairs(lst[1:i]+lst[i+1:]):的循环中，继续运行将恢复第三层迭代器的运行。
  - 第三层迭代器此时的pair为(5, 6)；它处于for rest in all_pairs(lst[1:i]+lst[i+1:]):的循环中
  - 由于第四层迭代器在第一步中已经结束，for rest in all_pairs(lst[1:i]+lst[i+1:]):被结束
  - 由于for i in range(1,len(lst)):只运行一次（在第一步中已被运行），第三层迭代器结束
- 第二层迭代器的for rest in all_pairs(lst[1:i]+lst[i+1:]):循环结束（结果只有一个(5, 6)），进入for i in range(1,len(lst)):循环的第二次循环中。
- 此时i增加了1，取出的组合为(3, 5)；又进入了for rest in all_pairs(lst[1:i]+lst[i+1:]):
  - 一个新的第三层迭代器被创建，输入列表为[(4, 6)]
  - 我们这个时候应该可以直接看出来这个迭代器会且只会返回[(4, 6)]，中间过程就略过了
- 与第一步同理，这里的返回值为[(3, 5), (4, 6)]
与第一步同理，这里的返回值为[(1, 2), (3, 5), (4, 6)]

写到这里基本上我们可以直接推出之后的结果了。显然是[(1, 2), (3, 6), (4, 5)]和[(1, 3), (2, 4), (5, 6)], …。就这样通过一个一个的循环以及迭代，我们把所有可能的组合都列了出来。又利用了生成器在yield时会暂停，下次被引用时会继续的特性，每次迭代到最下层时将每一层的结果都返回，同时将上层迭代器的结果暂时冻结，下次引用整个生成器时只改变相对下层的结果，通过这样的方式遍历所有的组合可能性。

从列表中给出所有可能的配对方式 - Python生成器的妙用

基本思路

问题1

问题2

运行实例：6元素列表

CATALOG

FEATURED TAGS

FRIENDS