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)

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 — Hercynium
– Hercynium, Commented Apr 4, 2012 at 12:43
I've added a bunch of features to Set::CrossProduct v3 to handle random access. I mostly stole the code from Set::CartesianProduct::Lazy/) then extended it in many directions. — brian d foy
– brian d foy, Commented Dec 30, 2024 at 5:20

brian d foy · Accepted Answer · 2024-11-28 15:11:45Z

29

The number of possible combinations is 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.

edited Nov 28, 2024 at 15:11

brian d foy

134k31 gold badges214 silver badges613 bronze badges

answered Mar 30, 2012 at 14:32

Howard

39.3k9 gold badges68 silver badges85 bronze badges

Sign up to request clarification or add additional context in comments.

Comments

Sohrab T · Accepted Answer · 2019-06-12 19:40:45Z

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

Levan Gharibashvili · Accepted Answer · 2021-01-20 09:41:03Z

1

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))

answered Jan 20, 2021 at 9:41

Levan Gharibashvili

734 bronze badges

Comments

Ka Wa Yip · Accepted Answer · 2024-10-24 01:13:58Z

0

This light and short python code of Howard's reasoning will work (with minimal import of math package):

import math
def howardFun(i, lsts):
    c_i = [] #c(i)
    for j, J in enumerate(lsts):                          
        sizes = math.prod([len(l) for l in lsts][(j+1):]) #see e.g. (size(B)*size(C))
        i_j = i//sizes % len(J) #see e.g. (i/size(C)) mod size(B)
        c_i.append(J[i_j]) #append e.g. A[i_a]
    return c_i

Example:

A = [1,2,3]
B = [2,3]
C = [5,6,7]
c_9 = howardFun(9, [A,B,C]) #c(i), where i = 9
print(c_9)

[2, 3, 5]

Without building the whole cartesian products, it is identical to the memory-intensive approach of list(list(itertools.product(*[A,B,C]))[9])

[2, 3, 5]

answered Oct 24, 2024 at 1:13

Ka Wa Yip

3,0594 gold badges27 silver badges39 bronze badges

Collectives™ on Stack Overflow

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

4 Answers 4

Comments

Comments

Comments

Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

4 Answers 4

Comments

Comments

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related