Как выбрать конкретный элемент из декартова продукта без вычисления каждого другого элемента

Я в основном убежден, что есть ответ на эту проблему, но для меня жизнь не может понять, как это сделать.

Скажем, у меня три набора:

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

И я знаю, как вычислить декартово/кросс-продукт, (ant он покрыт повсеместно, на этом сайте и в другом месте), поэтому я не буду пересматривать это здесь.

Я ищу алгоритм, который позволит мне просто выбрать конкретный элемент из декартова продукта без генерации всего набора или итерации до тех пор, пока я не достигню n-го элемента.

Конечно, я мог бы легко выполнить итерацию для небольшого примера, подобного этому, но код, над которым я работаю, будет работать с гораздо большими наборами.

Поэтому я ищу функцию, позволю назвать ее "CP", где:

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' ]

И ответ получается в O (1) раз, более или менее.

Я следил за тем, чтобы было возможно (черт, даже просто!) рассчитать индексы элементов из A, B, C, которые я хочу, а затем просто вернуть их из исходных массивов, но мои попытки правильно выполнить эту работу до сих пор, гм, не сработали.

Я кодирую в Perl, но могу легко переносить решение из Python, JavaScript или Java (и, возможно, нескольких других)

Ответы

Ответ 1

Число возможных комбинаций ist задано

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

и вы можете индексировать все элементы индексом i от 0 до N (эксклюзивно) с помощью

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

где

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

(все множества считаются индексируемыми начиная с нуля, / является целым делением).

Чтобы получить ваш пример, вы можете сдвинуть индекс на 1.

Ответ 2

Я сделал Python-версию ответа Говарда. Пожалуйста, дайте мне знать, если вы думаете, что это может быть улучшено.

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