How to select specific item from cartesian product without calculating every other item

Question

I'm mostly convinced that there is an answer to this problem, but for the life of me can't figure out how to do it.

Let's say I have three sets:

A = [ 'foo', 'bar', 'baz', 'bah' ]
B = [ 'wibble', 'wobble', 'weeble' ]
C = [ 'nip', 'nop' ]

And I know how to calculate the cartesian / cross product, (ant it's covered all over the place, on this site and elsewhere) so I won't go over that here.

What I'm looking for is an algorithm that would allow me to simply select a specific item from the cartesian product without generating the whole set or iterating until I reach the nth item.

Of course, I could easily iterate for a small example set like this, but the code I am working on will be working with much larger sets.

Therefore, I'm looking for a function, let's call it 'CP', where:

CP(1) == [ 'foo', 'wibble', 'nip' ]
CP(2) == [ 'foo', 'wibble', 'nop' ]
CP(3) == [ 'foo', 'wobble', 'nip' ]
CP(4) == [ 'foo', 'wobble', 'nop' ]
CP(5) == [ 'foo', 'weeble', 'nip' ]
CP(6) == [ 'foo', 'weeble', 'nop' ]
CP(7) == [ 'bar', 'wibble', 'nip' ]
...
CP(22) == [ 'bah', 'weeble', 'nop' ]
CP(23) == [ 'bah', 'wobble', 'nip' ]
CP(24) == [ 'bah', 'wobble', 'nop' ]

And the answer is produced in O(1) time, more or less.

I've been following the idea that it should be possible, (heck, even simple!) to calculate the indices of the elements from A,B,C that I want and then simply return the them from the original arrays, but my attempts to make this work correctly have so far, um, not worked.

I'm coding in Perl, but I can handily port a solution from Python, JavaScript, or Java (and probably a few others)

Stela

Since there was nothing I found on the CPAN that did this sort of 'lazy' calculation, I've uploaded the following module so others don't have to code it themselves: metacpan.org/release/Set-CartesianProduct-Lazy – Stela

Answer 1

The number of possible combinations ist given by

N = size(A) * size(B) * size(C)

and you can index all items by an index i ranging from 0 to N (exclusive) via

c(i) = [A[i_a], B[i_b], C[i_c]]

where

i_a = i/(size(B)*size(C)) 
i_b = (i/size(C)) mod size(B)
i_c = i mod size(C)

(all sets are assumed to be indexable starting wih zero, / is integer division).

In order to get your example you may shift the index by 1.

Rafat

Answer 2

I made a python version of the answer by Howard. Please let me know if you think it can be improved.

def ith_item_of_cartesian_product(*args, repeat=1, i=0):
    pools = [tuple(pool) for pool in args] * repeat   
    len_product = len(pools[0])
    for j in range(1,len(pools)):
        len_product = len_product * len(pools[j])
    if n >= len_product:
        raise Exception("n is bigger than the length of the product")
    i_list = []
    for j in range(0, len(pools)):
        ith_pool_index = i
        denom = 1
        for k in range(j+1, len(pools)):
            denom = denom * len(pools[k])
        ith_pool_index = ith_pool_index//denom
        if j != 0:
            ith_pool_index = ith_pool_index % len(pools[j])
        i_list.append(ith_pool_index)
    ith_item = []
    for i in range(0, len(pools)):
        ith_item.append(pools[i][i_list[i]])
    return ith_item

Compote

Answer 3

Here is a shorter Python code based on Howard's answer:

import functools
import operator
import itertools

def nth_product(n, *iterables):
    sizes = [len(iterable) for iterable in iterables]
    indices = [
        int((n/functools.reduce(operator.mul, sizes[i+1:], 1)) % sizes[i])
        for i in range(len(sizes))]
    return tuple(iterables[i][idx] for i, idx in enumerate(indices))

Cartload