如何对一组二进制字符串中无序对的所有乘积进行高效求和

Question

给定一组二进制字符串 S，其中每个二进制字符串的长度为 L，我想找到这些字符串中每个唯一无序元素的所有无序元素对乘积的总和一对。然后我想将它们放置在一个矩阵中，使得位置 i,j 是所有二进制字符串上无序索引对 i,j 的乘积之和。

例如：

让S = {101, 110, 111}

第一个二进制字符串 s∈S = 101 具有无序对 {10, 11, 01}，其索引为 {12, 13, 23}。每个无序对的乘积是 {0, 1, 0}.

第二个二进制字符串 s∈S = 110 具有无序对 {11, 10, 10}，其索引为 {12, 13, 23}。每个无序对的乘积是 {1, 0, 0}.

第三个二进制字符串 s∈S = 111 具有无序对 {11, 11, 11}，其索引为 {12, 13, 23}。每个无序对的乘积是 {1, 1, 1}.

对乘积求和，我们有 {0, 1, 0} + {1, 0, 0} + {1, 1, 1} = {2, 2, 1}。

现在我想根据无序对 {12, 13, 23} 的索引将它们放置在一个数组中，其顺序在上面保持不变。因此：

0, 2, 2
2, 0, 1
2, 1, 0

我已经编写了一些 Python 代码，它们在嵌套的 for 循环中实现了这一点，对于少量的短二进制字符串，它工作得很好。但是，我需要计算长度为 10,000.

的 150 个字符串

import numpy as np

n_strings = 3
len_strings = 3

ordered_sum_matrix = np.zeros((len_strings,len_strings))

for s in range(0, int(n_strings)):
    binary_string = np.random.binomial(1, 0.5, len_strings)
    for i in range(0, len(binary_string)):
        for j in range(0, len(binary_string)):
            if i == j:
                continue
            ordered_sum_matrix[i,j] = ordered_sum_matrix[i,j] + (binary_string[i] * binary_string[j])

是否有一些线性代数、二进制字符串或 Python 魔术的技巧可以帮助加快速度？

Answer 1

感谢 numpy-maestro 朋友提供如下解决方案：

import numpy as np

def sum_of_prods_of_pairs(M):
    # note: this function performs slightly better if given booleans
    # e.g. M = np.random.choice([True, False], (len_strings, n_strings))
    n_strings, len_strings = M.shape
    MT = M.T
    M_sum = np.zeros((len_strings, len_strings))

    for i in range(len_strings):
        M_sum[i, i+1:len_strings] = np.sum(np.multiply(MT[i], MT[i+1:len_strings]), axis=1)
    M_sum += M_sum.T
    return M_sum

# n_strings = 150
# len_strings = 10000

# np.random.seed(91)
# C = np.random.choice([True, False], (n_strings, len_strings))
# C = np.random.binomial(1, 0.1, (n_strings, len_strings))
C = np.array([[1,0,1], [1,1,0], [1,1,1]])

ordered_sum_matrix = sum_of_prods_of_pairs(C)

print(ordered_sum_matrix)

打印

[[0. 2. 2.]
 [2. 0. 1.]
 [2. 1. 0.]]

如何对一组二进制字符串中无序对的所有乘积进行高效求和

How to performantly sum all products of unordered pairs in a set of binary strings

binary

performance

linear-algebra

combinatorics

python-3.x