CODEWITHSUNDEEP
algorithmlanguage-agnosticiterationcartesian-product
Federico A. Ramponi
Federico A. Ramponi

Reputation: 47075

How can I compute a Cartesian product iteratively?

This question asks how to compute the Cartesian product of a given number of vectors. Since the number of vectors is known in advance and rather small, the solution is easily obtained with nested for loops.

Now suppose that you are given, in your language of choice, a vector of vectors (or list of lists, or set of sets, etc.):

l = [ [1,2,3], [4,5], [6,7], [8,9,10], [11,12], [13] ]

If I was asked to compute its Cartesian product, that is

[ [1,4,6,8,11,13], [1,4,6,8,12,13], [1,4,6,9,11,13], [1,4,6,9,12,13], ... ]

I would proceed with recursion. For example, in quick&dirty python,

def cartesianProduct(aListOfLists):
    if not aListOfLists:
        yield []
    else:
        for item in aListOfLists[0]:
            for product in cartesianProduct(aListOfLists[1:]):
                yield [item] + product

Is there an easy way to compute it iteratively?

(Note: The answer doesn't need to be in python, and anyway I'm aware that in python itertools does the job better, as in this question.)

Upvotes: 15

Views: 7740

Answers (5)

Tsvi Sabo
Tsvi Sabo

Reputation: 675

This solution is longer but i find it easier to understand, First, compute the number of combinations composing the product (multiplication of inner lists lengths) Second, loop over the number of combinations, the combination number is a unique encoding you can decode into a products element

E.G: [["Apple", "Orange"],[1,2,3], ..] -> 0 = ["Apple", 1], 1 = ["Apple", 2], 2 = ["Apple", 3], 4 = ["Orange", 1] ... And another e.g: ["Apple", 3] is equal to [0, 2]

you can look at each element in the master list as a digit determining the base of the encoding of the next digit, since the first element is ["Apple", "Orange"] and it's size is 2, the second digit is 2 if we had:

[["Apple", "Orange"],[1,2,3], ["Shrimp", "Creep", "Sleep"]] then the digits encoding would have been a list: [1, 2, 2*3]

from functools import reduce

def get_multiplication(digits: list):
    return reduce(lambda x, y: x*y, map(len, digits)) if digits else 1
    
def get_accumalated_multiplication(x: list[list]):
    return [get_multiplication(x[:i]) for i in range(len(x))]
    
def decode_to_product(encoding: int, encoding_digits: list, x: list):
    product = [0] * len(encoding_digits)
    current_product_encoding = encoding
    for i, digit in enumerate(reversed(encoding_digits)):
        bit = 0
        while ((bit + 1) * digit)  <= current_product_encoding:
            bit += 1 
        current_product_encoding -= digit * bit
        product[i] = x[i][bit]
    return tuple(product)
    

def product(x: list[list]):
    encoding_digits = get_accumalated_multiplication(x)
    num_products = reduce(lambda x, y: x*y, encoding_digits)

    for i in range(num_products):
        yield decode_to_product(i, encoding_digits, x)

Upvotes: 0

user unknown
user unknown

Reputation: 36229

Since you asked for a language-agnostic solution, here is one in bash, but can we call it iterative, recursive, what is it? It's just notation:

echo {1,2,3},{4,5},{6,7},{8,9,10},{11,12},13

maybe interesting enough.

1,4,6,8,11,13 1,4,6,8,12,13 1,4,6,9,11,13 1,4,6,9,12,13 1,4,6,10,11,13 ...

Upvotes: 3

Mark Byers
Mark Byers

Reputation: 838276

1) Create a list of indexes into the respective lists, initialized to 0, i.e:

indexes = [0,0,0,0,0,0]

2) Yield the appropriate element from each list (in this case the first).

3) Increase the last index by one.

4) If the last index equals the length of the last list, reset it to zero and carry one. Repeat this until there is no carry.

5) Go back to step 2 until the indexes wrap back to [0,0,0,0,0,0]

It's similar to how counting works, except the base for each digit can be different.

Here's an implementation of the above algorithm in Python:

def cartesian_product(aListOfList):
    indexes = [0] * len(aListOfList)
    while True:
        yield [l[i] for l,i in zip(aListOfList, indexes)]
        j = len(indexes) - 1
        while True:
            indexes[j] += 1
            if indexes[j] < len(aListOfList[j]): break
            indexes[j] = 0
            j -= 1
            if j < 0: return

Here is another way to implement it using modulo tricks:

def cartesian_product(aListOfList):
    i = 0
    while True:
        result = []
        j = i
        for l in aListOfList:
             result.append(l[j % len(l)])
             j /= len(l)
        if j > 0: return
        yield result
        i += 1

Note that this outputs the results in a slightly different order than in your example. This can be fixed by iterating over the lists in reverse order.

Upvotes: 23

IVlad
IVlad

Reputation: 43467

You just have to manage your stack manually. Basically, do what recursion does on your own. Since recursion puts data about each recursive call on a stack, you just do the same:

Let L[i] = elements in vector i
k = 0;
st[] = a pseudo-stack initialized with 0
N = number of vectors 
while ( k > -1 )
{
  if ( k == N ) // solution, print st and --k

  if ( st[k] < L[k].count )
  {
    ++st[k]
    ++k
  }
  else
  {
    st[k] = 0;
    --k;
  }
}

Not tested, but the idea will work. Hopefully I didn't miss anything.

Edit: well, too late I guess. This is basically the same as counting, just another way of looking at it.

Upvotes: 1

Larry
Larry

Reputation: 4559

Iterate from 0 to \Pi a_i_length for all i.

for ( int i = 0; i < product; i++ ) {
    // N is the number of lists
    int now = i;
    for ( int j = 0; j < N; j++ ) {
        // This is actually the index, you can get the value easily.
        current_list[j] = now % master_list[j].length;

        // shifts digit (integer division)
        now /= master_list[j].length;  
    }
}

There are also some trivial ways to write this so you don't have to do the same work twice.

Upvotes: 2

Related Questions