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

Question

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

Допустим, у меня есть три набора:

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

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

Мне нужен алгоритм, который позволил бы мне просто выбрать определенный элемент из декартового произведения без , генерируя весь набор или итерируя, пока я не достигну 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 (и, возможно, нескольких других)

Answer 1

Количество возможных комбинаций определяется как

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.

Answer 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