我get_tuples(length, total)
从这里开始使用函数来生成给定长度和总和的所有元组的数组,示例和函数如下所示。创建数组后,我需要找到一种方法来返回数组中给定数量的元素的索引。.index()
通过将数组更改为列表,可以做到这一点,如下所示。但是,此解决方案或另一种也基于搜索(例如使用np.where
)的解决方案需要大量时间才能找到索引。由于数组中的所有元素(数组s
在示例中是不同的),我想知道我们是否可以构造一对一映射,即一个函数,使得给定数组中的元素,它通过对值进行一些加法和乘法来返回元素的索引这个元素。有什么想法吗?谢谢!
import numpy as np
def get_tuples(length, total):
if length == 1:
yield (total,)
return
for i in range(total + 1):
for t in get_tuples(length - 1, total - i):
yield (i,) + t
#example
s = np.array(list(get_tuples(4, 20)))
# array s
In [1]: s
Out[1]:
array([[ 0, 0, 0, 20],
[ 0, 0, 1, 19],
[ 0, 0, 2, 18],
...,
[19, 0, 1, 0],
[19, 1, 0, 0],
[20, 0, 0, 0]])
#example of element to find the index for. (Note in reality this is 1000+ elements)
elements_to_find =np.array([[ 0, 0, 0, 20],
[ 0, 0, 7, 13],
[ 0, 5, 5, 10],
[ 0, 0, 5, 15],
[ 0, 2, 4, 14]])
#change array to list
s_list = s.tolist()
#find the indices
indx=[s_list.index(i) for i in elements_to_find.tolist()]
#output
In [2]: indx
Out[2]: [0, 7, 100, 5, 45]
这是一个仅基于元组来计算索引的公式,即它不需要看到完整的数组。要计算N元组的索引,需要评估N-1个二项式系数。以下实现是(部分)矢量化的,它接受ND数组,但元组必须在最后一维。
import numpy as np
from scipy.special import comb
# unfortunately, comb with option exact=True is not vectorized
def bc(N,k):
return np.round(comb(N,k)).astype(int)
def get_idx(s):
N = s.shape[-1] - 1
R = np.arange(1,N)
ps = s[...,::-1].cumsum(-1)
B = bc(ps[...,1:-1]+R,1+R)
return bc(ps[...,-1]+N,N) - ps[...,0] - 1 - B.sum(-1)
# OP's generator
def get_tuples(length, total):
if length == 1:
yield (total,)
return
for i in range(total + 1):
for t in get_tuples(length - 1, total - i):
yield (i,) + t
#example
s = np.array(list(get_tuples(4, 20)))
# compute each index
r = get_idx(s)
# expected: 0,1,2,3,...
assert (r == np.arange(len(r))).all()
print("all ok")
#example of element to find the index for. (Note in reality this is 1000+ elements)
elements_to_find =np.array([[ 0, 0, 0, 20],
[ 0, 0, 7, 13],
[ 0, 5, 5, 10],
[ 0, 0, 5, 15],
[ 0, 2, 4, 14]])
print(get_idx(elements_to_find))
样品运行:
all ok
[ 0 7 100 5 45]
如何推导公式:
用星号和条形表示完整的分区数#part(N,k)
(N为总数,k为长度)作为单个二项式系数(N + k - 1) choose (k - 1)
。
从头开始计数:不难验证OP生成器的外循环的第i次完整迭代之后#part(N-i,k)
是否还没有被枚举。确实,剩下的就是所有分区p1 + p2 + ... = N,其中p1> = i; 我们可以这样写p1 = q1 + i,使得q1 + p2 + ... = Ni,后一个分区不受约束,因此我们可以使用1.进行计数。
本文收集自互联网,转载请注明来源。
如有侵权,请联系[email protected] 删除。
我来说两句