algorithm - 如何在不计算所有其他项目的情况下从笛卡尔积中选择特定项目

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。