我最相信这个问题的答案,但是我一生都无法解决。
假设我有三套:
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(可能还有其他一些)移植解决方案
给出的可能组合数ist
N = size(A) * size(B) * size(C)
您可以通过i范围从0到N(不包括)的索引来索引所有项目
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。