时间戳

首页 > 解决方案 > 使用递归从两个列表创建对列表

python - 使用递归从两个列表创建对列表

问题描述

我需要创建一个函数，该函数将两个列表作为参数，并使用 python 3.x 中的递归返回两个列表中元素对的列表。

输入create_all_pairs([1,2], [3,4])应该给我：

[(1,3), (1,4), (2,3), (2,4)].

我用 3 种不同的方式创建了这个函数：使用 for 循环、使用 while 循环和使用列表推导。

def create_all_pairs_for(xs, ys):
    lst = []
    for x in xs:
        for y in ys:
            lst.append((x,y))
    return lst

def create_all_pairs_while(xs, ys):
    lst = []
    xscount = 0
    yscount = 0
    while xscount < len(xs):
        while yscount < len(ys):
            lst.append((xs[xscount], ys[yscount]))
            yscount += 1
        xscount += 1
        yscount = 0
    return lst

def create_all_pairs_listcomp(xs, ys):
    lst = [(a,b) for a in xs for b in ys]
    return lst

如何使用递归编写此函数？这是我到目前为止所得到的，但我感到完全迷失了。

def create_all_pairs_rec(xs, ys):
    if not xs:
        return []
    else:
        return list(map(create_all_pairs_rec(xs, ys)), ys)

标签： pythonlistrecursiontuples

解决方案

以下将是一个递归实现：

def create_all_pairs(xs, ys):
    if not (xs and ys):
        return []
    return [(xs[0], y) for y in ys] + create_all_pairs(xs[1:], ys)

虽然这有点作弊，因为它只使用递归来减少 ，但这xs是一个真正的递归分而治之的解决方案，它递归地减小 和 的问题xs大小ys：

def create_all_pairs(xs, ys):
    if not (xs and ys):  # base case 1: any empty list
        return []
    if len(xs) == len(ys) == 1:  # base case 2: two singleton lists
        return [(xs[0], ys[0])]
    mid_x, mid_y = len(xs) // 2, len(ys) // 2
    return create_all_pairs(xs[:mid_x], ys[:mid_y]) + create_all_pairs(xs[:mid_x], ys[mid_y:]) + \
           create_all_pairs(xs[mid_x:], ys[:mid_y]) + create_all_pairs(xs[mid_x:], ys[mid_y:])

>>> create_all_pairs([1, 2], [3, 4])
[(1, 3), (1, 4), (2, 3), (2, 4)]
>>> create_all_pairs([1, 2, 3], [3, 4, 5])
[(1, 3), (1, 4), (1, 5), (2, 3), (3, 3), (2, 4), (2, 5), (3, 4), (3, 5)]

推荐阅读