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

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) время, более или менее.

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

я кодирования в Perl, но я могу сподручно порт решение от Python, JavaScript или Java (и, возможно, некоторые другие)

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

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

Для того, чтобы получить ваш пример, вы можете переместить указатель на 1.