如何创建索引组合(n 中的 k 个)作为 numpy 的稀疏位掩码

Question

对于 numpy 如何有效地创建

1. 一个数组/矩阵，表示所有组合的列表(N 个中的 k(作为 k 个索引的列表。形状将是(二项式(n，k(，k(。

2. 一个稀疏数组/矩阵，将此组合表示为长度为 n 的位掩码。 (因此将上面的索引扩展到位掩码。形状将是(二项式(n，k(，n(。

我需要用大的 n(也许还有小 k(来做到这一点。所以算法应该是

1. 节省时间(例如，在填充之前可以立即分配完整的结果空间？

2. 节省空间(例如稀疏位掩码(

非常感谢您的帮助。

Answer 1

假设爆炸不是那么糟糕(如上面的评论所述(，您可以尝试此操作。它非常矢量化，应该很快(对于可以处理的情况(。

编辑：我有点假设你对基于scipy.sparse的输出感兴趣。也许你不是。

法典

import itertools
import numpy as np
import scipy.sparse as sp
def combs(a, r):
    """
    Return successive r-length combinations of elements in the array a.
    Should produce the same output as array(list(combinations(a, r))), but
    faster.
    """
    a = np.asarray(a)
    dt = np.dtype([('', a.dtype)]*r)
    b = np.fromiter(itertools.combinations(a, r), dt)
    b_ = b.view(a.dtype).reshape(-1, r)
    return b_
def sparse_combs(k, n):
    combs_ = combs(np.arange(n), k)
    n_bin = combs_.shape[0]
    spmat = sp.coo_matrix(( np.ones(n_bin*k),
                            (np.repeat(np.arange(n_bin), k),
                             combs_.ravel()) ),
                            shape=(n_bin, n))
    return spmat

print('dense')
print(combs(range(4), 3))
print('sparse (dense for print)')
print(sparse_combs(3, 4).todense())

输出

dense
[[0 1 2]
 [0 1 3]
 [0 2 3]
 [1 2 3]]
sparse (dense for print)
[[ 1.  1.  1.  0.]
 [ 1.  1.  0.  1.]
 [ 1.  0.  1.  1.]
 [ 0.  1.  1.  1.]]

我(可能(从这个问题(过去的某个时候(中获取的帮助程序功能combs。

小(不科学(时间：

from time import perf_counter as pc
start = pc()
spmat = sparse_combs(5, 50)
time_used = pc() - start
print('secs: ', time_used)
print('nnzs: ', spmat.nnz)
#secs:  0.5770790778094155
#nnzs:  10593800
(3, 500)
#secs:  3.4843752405405497
#nnzs:  62125500