How would I get a list of pairs where every element from list1 is paired with some element from list2?

So I have this problem in my head that I'm trying to solve iteratively instead of recursively, but the solution seems to elude me despite it seemingly being so easy.

Let's say I have two lists

l1 = [a,b,c]
l2 = [1,2,3]

I want a list, where every element from l1 is paired with some element from l2. So it'll be like below:

[
[(a,1), (b,1), (c,1)],
[(a,1), (b,1), (c,2)],
[(a,1), (b,1), (c,3)],
[(a,1), (b,2), (c,1)],
[(a,1), (b,2), (c,2)],
[(a,1), (b,2), (c,3)],
[(a,1), (b,3), (c,1)],
[(a,1), (b,3), (c,2)],
[(a,1), (b,3), (c,3)],
...
]

Note that this is a bit different than simply getting a cross product (cartesian product).

Doing something like

for i in l1:
  for j in l2:
    ...

doesn't quite work here because once you have the (a,1) pair for example, you have to jump to b instead of continuing to (a,2).

From the looks of it, it seems like it shouldn't be too difficult to formulate loops to make this result, but it's not coming to me immediately. I did make a recursive solution in python for your reference though.

l1 = ['a','b','c']
l2 = [1,2,3]
l3 = []

def makepair(res,cur,l1,l2):
    if(l1==[]):
        res.append(cur)
    else:
        for i in l2:
            temp = cur[:]
            temp.append((l1[0],i))
            makepair(res,temp,l1[1:],l2)

makepair(l3,[],l1,l2)
for p in l3:
    print(p)

The above code basically prints the example I explained. Can someone help me write this iteratively? I don't care about which language.

> Note that this is a bit different than simply getting a cross product (cartesian product).

Actually, it is exactly a Cartesian product, of list2 with list2 with list2, using list1 as indices.

Note that cross product and Cartesian product are pretty unrelated. In python, you can get the Cartesian product with the standard library, using itertools.product. For the cross product, use the numpy library.

Using itertools.product

from itertools import product

list1 = ['a','b','c']
list2 = [1,2,3]

print( [list(zip(list1, p)) for p in product(list2, repeat=len(list1))] )
# [[('a', 1), ('b', 1), ('c', 1)],
#  [('a', 1), ('b', 1), ('c', 2)],
#  [('a', 1), ('b', 1), ('c', 3)],
#  [('a', 1), ('b', 2), ('c', 1)],
#  ...,
#  [('a', 3), ('b', 3), ('c', 3)]]

Using for-loops

Of course, if the number of elements in list1 is small and constant, python's itertools.product is equivalent to nested simple loops:

def indexed_cartesian_product(l1, l2):
    a, b, c = l1
    for x in l2:
        for y in l2:
            for z in l2:
                yield ((a, x), (b, y), (c, z))

print(list(indexed_cartesian_product('abc', [1,2,3])))
# [(('a', 1), ('b', 1), ('c', 1)),
#  (('a', 1), ('b', 1), ('c', 2)),
#  (('a', 1), ('b', 1), ('c', 3)),
#  (('a', 1), ('b', 2), ('c', 1)),
#  ...,
#  (('a', 3), ('b', 3), ('c', 3))]

Starting with just an empty row, then building up from that one column at a time (Python implementation):

l1 = ['a','b','c']
l2 = [1,2,3]

l3 = [[]]
for column in l1:
    l3 = [
        row + [(column, value)]
        for row in l3
        for value in l2
    ]

for p in l3:
    print(p)

Same but written more in the style of other languages:

l3 = [[]]
for column in l1:
    new_l3 = []
    for row in l3:
        for value in l2:
            new_row = row + [(column, value)]
            new_l3.append(new_row)
    l3 = new_l3

Bonus solution using itertools (producing an iterator of tuples of pairs instead of a list of list of pairs, but that's easy to adjust if really necessary.

from itertools import repeat, product

l1 = ['a','b','c']
l2 = [1,2,3]

result = product(*map(zip, map(repeat, l1), repeat(l2)))

for p in result:
    print(p)

I wrote up a solution that basically translates the recursion into a stack. Afterall, all recursions run on a stack. (Link if you want to play with it yourself)

l1 = ['a','b','c']
l2 = [1,2,3]
l3 = []

stack = [[]]
while(len(stack)>0):
    check = stack.pop()
    if (len(check) == len(l1)):
        l3.append(check)
    else:
        for e in l2:
            stack.append(check+[(l1[len(check)],e)])
print(l3)

If we really wanted to save memory, I think this could be done without building the stack like this though. But considering the stack would be at most as big as the resulting list, therefore needing that much space anyway, I guess it's not a priority in my problem statement. But if we change up the problem a little bit and say we are checking if a "specific" combination exists, then the space can be wasteful. Afterall, building the entire combination will create a size of (len_l2)^(len_l1). Because this is exponential, it can get nasty really fast, so I think it's worth considering clever solutions that won't build the stack like this. (Note, the stack at each point should be smaller than (len_l2)^(len_l1), but I don't know how much smaller. Not sure how much smaller it would be on average, and also not sure how much smaller it is at its worst point. But I think it'll still be exponential)

An example scenario for finding a "specific" case might be if both l1 and l2 are made of numbers, and you are getting the sum of (each element in l1)*(some element in l2), and you must check whether there is some combination where the sum matches a specific number. In such a case, solutions using stuff like itertools.product start to become less useful because if you have to iterate through so much data, ideally you want to break the moment you find your specific case instead of building all possible options first and then iterating through them to see if the case exists.

I also made a pretty messy solution that doesn't build a stack. I did this in C++ instead of python because my original goal was to do this idea in C++ anyways. (Just initially used python for better readability)

#include <iostream>
#include <bits/stdc++.h>

using namespace std;

//cur will be in the form of [0,1,2], and would need to be transformed to [(a,1),(b,2),(c,3)]
void add_to_l3(vector<vector<pair<char,int>>> &l3, vector<char> &l1, vector<int> &l2, vector<int> &cur) {
    vector<pair<char,int>> paired_cur(l1.size()); 
    for(int x=0; x<l1.size(); x++){
        paired_cur[x] = {l1[x], l2[cur[x]]};
    }
    l3.push_back(paired_cur);
}

int main()
{
    vector<char> l1 = {'a','b','c'};
    vector<int> l2 = {1, 2, 3};
    vector<vector<pair<char,int>>> l3;
    vector<int> cur(l1.size(), 0);
    //cur[i] stores the index of the number at l2 that would be paired with l1[i]
    int i = l1.size()-1;
    //Start with the base case of [(a,1),(b,1),(c,1)] and keep the pointer at the back of the array pointing at (c,1)
    //We iterate through l2's spot at the pointer such as [(a,1),(b,1),(c,2)] until we can't any more (which is at [(a,1),(b,1),(c,3)])
    //Afterwards, we decrement the pointer and notify that we decremented the pointer. We would now be pointing at (b,1)
    //If we can increment the l2's spot there, increment it, and then reset all the l2's spot for every element in the right of that to the base case. Start the pointer at the back of the array again.
    //If we couldn't increment the L2's spot, keep decrementing the pointer until we find the location that could increment l2's spot, and then reset all l2's spot for elements to the right of it.
    //Do this until we run out of spaces to decrement the pointer.
    add_to_l3(l3,l1,l2,cur);
    bool back=false;
    //This boolean checks if we decremented the pointer
    while(i>=0) {
        if(cur[i] < l2.size()-1) {
            cur[i]++;
            if(back==true) {
                for(i=i+1; i<l1.size(); i++) {
                    cur[i]=0;
                }
                back=false;
                i=l1.size()-1;
            }
            //cout << i << endl;
            add_to_l3(l3,l1,l2,cur);
        }
        else {
            i--;
            back=true;
        }
    }
    for (auto &e : l3) {
        for (auto &p : e) {
            cout << '(' << p.first << ',' << p.second << ')';
        }
        cout << endl;
    }
    return 0;
}

The idea behind this is that we start with

[(a,1),(b,1),(c,1)]

and start by pointing at (c,1).

Increment the l2 part of the pair until we can't like so:

[(a,1),(b,1),(c,2)] and [(a,1),(b,1),(c,3)]

Then we backtrack the pointer to point at (b,1) and increment the l2 part, or if that is also maxed out (because it is (b,3)), we keep backtracking until we reach a location where we can increment the l2 part. Once we increment the l2 part, we reset all the l2 part to the right of it to the base case.

So when we are pointing at (b,1), that gets changed to (b,2). And then (c,3) gets reset to (c,1). Therefore, we have [(a,1),(b,2),(c,1)]

It's messy but this allows us to be holding onto just one set of combination at a time, while also having full control of observing each combination at the moment we reach it.

Please let me know if you have any feedback of making this simpler