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

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)

并且您可以通过通过从0到N（独占）的索引i对所有项目进行索引

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。

Answer 2

我制作了霍华德的答案的python版本。如果你认为可以改进，请告诉我。

def ith_item_of_cartesian_product(*args, repeat=1, i=0):
    pools = [tuple(pool) for pool in args] * repeat   
    len_product = len(pools[0])
    for j in range(1,len(pools)):
        len_product = len_product * len(pools[j])
    if n >= len_product:
        raise Exception("n is bigger than the length of the product")
    i_list = []
    for j in range(0, len(pools)):
        ith_pool_index = i
        denom = 1
        for k in range(j+1, len(pools)):
            denom = denom * len(pools[k])
        ith_pool_index = ith_pool_index//denom
        if j != 0:
            ith_pool_index = ith_pool_index % len(pools[j])
        i_list.append(ith_pool_index)
    ith_item = []
    for i in range(0, len(pools)):
        ith_item.append(pools[i][i_list[i]])
    return ith_item

Answer 3

下面是一个基于Howard答案的较短Python代码：

import functools
import operator
import itertools
def nth_product(n, *iterables):
    sizes = [len(iterable) for iterable in iterables]
    indices = [
        int((n/functools.reduce(operator.mul, sizes[i+1:], 1)) % sizes[i])
        for i in range(len(sizes))]
    return tuple(iterables[i][idx] for i, idx in enumerate(indices))