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

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（也可能是其他几种语言）移植解决方案。

- Hercynium

---

由于我在 CPAN 上没有找到任何可以进行这种“懒惰”计算的东西，因此我上传了以下模块，以便其他人不必自己编写代码：https://metacpan.org/release/Set-CartesianProduct-Lazy - Hercynium

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位。

- Howard

Answer 2

这是基于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))

- Levan Gharibashvili

Answer 3

我做了一个 Howard 答案的 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

- Sohrab T