18

我主要相信这个问题有一个答案，但对于我的生活来说，我无法弄清楚如何去做。

假设我有三组：

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

4

3 回答 3

29

可能组合的数量由下式给出

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。

于 2012-03-30T14:32:07.553 回答
0

这是基于霍华德回答的更短的 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))
于 2021-01-20T09:41:03.333 回答
0

我制作了霍华德答案的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
于 2019-06-12T19:40:45.843 回答