如何从笛卡尔乘积中选择特定项目而不计算其他项目
如何从笛卡尔乘积中选择特定项目而不计算其他项目
提问于 2012-03-30 22:27:41
我基本上相信这个问题是有答案的，但我终生都不知道该怎么做。
假设我有三个集合：
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 (可能还有其他几种语言)的解决方案。
回答 3
Stack Overflow用户
回答已采纳
发布于 2012-03-30 22:32:08
可能组合的数量由下式给出
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。
Stack Overflow用户
发布于 2019-06-13 03:40:46
我对霍华德的答案做了一个蟒蛇版本。如果你认为它可以改进，请告诉我。
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_itemStack Overflow用户
发布于 2021-01-20 17:41:03
以下是基于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))页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/9944915
复制相关文章
相似问题