我基本上相信这个问题有答案,但我一生都不知道如何做到这一点。
假设我有三套:
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(可能还有其他一些)移植解决方案
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。
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
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))
的轻量且简短的 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]