如何从笛卡尔积中选择特定项目而不计算其他项目

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从(独占)via 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.