一尘不染

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

algorithm

我最相信这个问题的答案,但是我一生都无法解决。

假设我有三套:

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(可能还有其他一些)移植解决方案


阅读 220

收藏
2020-07-28

共1个答案

一尘不染

给出的可能组合数ist

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

您可以通过i范围从0N(不包括)的索引来索引所有项目

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。

2020-07-28