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

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

（不包括）viac(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

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

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))

Answer 4

Howard 推理

的轻量且简短的 Python 代码将可以工作（只需最小化 math 包的导入）：

def howardFun(i, lsts):
    c_i = [] #c(i)
    for j, J in enumerate(lsts):                          
        sizes = math.prod([len(l) for l in lsts][(j+1):]) #see e.g. (size(B)*size(C))
        i_j = i//sizes % len(J) #see e.g. (i/size(C)) mod size(B)
        c_i.append(J[i_j]) #append e.g. A[i_a]
    return c_i

示例：

A = [1,2,3]
B = [2,3]
C = [5,6,7]
c_9 = howardFun(9, [A,B,C]) #c(i), where i = 9
print(c_9)  

[2,3,5]

将此与内存密集型方法进行比较：

list(list(itertools.product(*[A,B,C]))[9])

[2,3,5]