Create a list of pairs from two lists using recursion

Question

I need to create a function that takes two lists as arguments and returns a list of the pairs of the elements in the two lists using recursion in python 3.x.

The input create_all_pairs([1,2], [3,4]) should give me :

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

I have created this function in 3 differen ways: using for-loops, using while-loops and using list comprehension.

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

How can i write this function using recursion? This is what i have got so far, but i feel completely lost.

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

You are missing the recursive step. You are calling the recursive function again and again with the exact same arguments. The idea of recursion is to have a reduction step that will lead you to the stopping condition — Tomerikoo, Dec 15 '19 at 14:36

user2390182 · Answer 1 · 2019-12-15T15:06:18.183

3

The following would be a recursive implementation:

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)

While this is a bit of cheat, as it only uses recursion to reduce the xs, here is a true recursive divide'n'conquer solution that decreases the problem size recursively for both xs and 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)]

edited Dec 15 '19 at 15:06

answered Dec 15 '19 at 14:48

user2390182

72,016
6
67
89

not sure why, it feels like using an explicit `for` is "cheating". It feels like `create_all_pairs` should be implemented in such a way where the stop condition is `return [(xs[0], ys[0])]` (ie the stop condition is when we have 2 single-element lists). Of course the price will be a much longer call stack – DeepSpace Dec 15 '19 at 14:52
1

@DeepSpace I feel the same way. Added a more authentic recursive implementation ;) – user2390182 Dec 15 '19 at 14:56
Nice, even has a *shorter* call stack. The result order is different, though (could be fixed (if necessary) by splitting differently). – Stefan Pochmann Dec 15 '19 at 15:21

Thomas McSwain · Answer 2 · 2019-12-16T07:57:49.027

0

find_all_pairs(xs,ys,ret):
    if xs == []: #basecase
        return ret #return the list we built
    else:
        left = xs.pop() #we take an element out of the left list
        for right in ys: #for every element in the right list
            ret.append((left,right)) #we append to the list were building a (left,right) tuple
         return find_all_pairs(xs,ys,ret) #call the function again with the decremented xs and the appended ret

edited Dec 16 '19 at 07:57

answered Dec 15 '19 at 14:32

Thomas McSwain

55
7

forgot to return the function call my bad – Thomas McSwain Dec 15 '19 at 14:41
1

Please add further information about what this code does instead of just writing the code, thanks – Gastón Saillén Dec 15 '19 at 17:18

DarrylG · Answer 3 · 2019-12-15T14:55:26.080

0

All pairs is the same as the cartesion product.

We can adapt this answer for using recursion to compute cartesion product: Cross product of sets using recursion (which has a good explanation)

An advantage of this function is that it works for an arbitrary number of lists (i.e. 1, 2, 3, etc.).

def create_all_pairs(*seqs):
    if not seqs:
        return [[]]
    else:
        return [[x] + p for x in seqs[0] for p in create_all_pairs(*seqs[1:])]

print(create_all_pairs([1,2], [3,4]))

Output

[[1, 3], [1, 4], [2, 3], [2, 4]]

edited Dec 15 '19 at 14:55

answered Dec 15 '19 at 14:42

DarrylG

16,732
2
17
23

@DeepSpace--thanks, typo in my copy/paste/edit cycle. – DarrylG Dec 15 '19 at 14:45

score 0 · Answer 4 · answered Dec 15 '19 at 15:18

Another recursive implementation, which also adds entries in a more sequential order to the final list of pairs, as compared to the answer above:

def create_all_pairs(list1, list2, resulting_list, index1=0, index2=0):

    if index1 < len(list1) and index2 < (len(list2)-1):
        resulting_list.insert(0, create_all_pairs(list1, list2, resulting_list, index1, index2+1))

    elif index1 < (len(list1)-1) and index2 >= (len(list2)-1):
        resulting_list.insert(0, create_all_pairs(list1, list2, resulting_list, index1+1, 0))

    if index1 == 0 and index2 == 0:
        resulting_list.insert(0, (list1[index1], list2[index2]))

    return (list1[index1], list2[index2])

resulting_list = list()
create_all_pairs([1, 2, 3], [3, 4, 5], resulting_list)

print("Resulting list is:", resulting_list)

Result:

Resulting list is: [(1, 3), (1, 4), (1, 5), (2, 3), (2, 4), (2, 5), (3, 3), (3, 4), (3, 5)]

Stefan Pochmann · Answer 5 · 2019-12-15T16:01:33.277

0

def all_pairs(x, y):
    return x and y and [(x[0], y[0])] + all_pairs(x[:1], y[1:]) + all_pairs(x[1:], y)

Based on @schwobaseggl's "true recursive" solution, just splitting differently.

edited Dec 15 '19 at 16:01

answered Dec 15 '19 at 15:45

Stefan Pochmann

27,593
8
44
107

Create a list of pairs from two lists using recursion

5 Answers5