将行连接到具有指定列的矩阵的算法 space

Question

假设存在一组 X 行向量，每个行向量的维度为 1 x m，以及一组 Y 列向量，每个向量的维度为 n x 1。

我们 select n 来自集合 X 的行向量，连接成维度为 n x m 的矩阵。我有兴趣找到矩阵，其中也可以通过连接来自 Y.

的 m 列向量来生成串联矩阵

是否有一种算法可以return所有这样的矩阵满足条件，即结果矩阵可以由行的串联 AND 也可以通过列的串联来实现吗？例如：

X = np.array([[1, 0, 1], [1, 0, 0], [0, 0, 1], [1, 1, 1], [0, 1, 1]])
Y = np.array([[1, 1, 0], [1, 0, 0], [0, 0, 0], [1, 0, 0], [1, 0, 1], [1, 1, 1]]).T

那么一个可以由 3 行 3 列串联而成的矩阵是：

M = 
[[1, 0, 1],
 [1, 0, 0],
 [0, 0, 1]]

Answer 1

也许这有帮助：

Select X 和 Y 之间较小的为 1)
从 Xs 个元素创建矩阵（如第 0 点），但为简单起见，我们假设是 X)。所以你有 FromXmatrix 这是一个 n x m 矩阵。
采用 FromXmatrix 并拆分成列。
检查该列是否在 Y 上，如果为 False，则放弃此追踪，如果是，则将该解决方案保存为有效
返回 1)，直到检查 X 的所有可能的有效组合。

您可以执行与上述相同的操作，但使用 Y 中的所有可能组合并检查它们是否产生根据 X 的元素有效的解决方案。

Answer 2

我假设你的 X 和 Y 是数组。如果不是，只需先将它们转换为 numpy 数组即可。

X = np.array([[1, 0, 1], [1, 0, 0], [0, 0, 1], [1, 1, 1], [0, 1, 1]])
Y = np.array([[1, 1, 0], [1, 0, 0], [0, 0, 0], [1, 0, 0], [1, 0, 1], [1, 1, 1]]).T

然后您的问题基本上转化为查找 X 的哪些行与 Y 的哪些列匹配。一旦找到所有匹配的行-列对，您就可以将匹配 rows/columns 的任何子集作为子矩阵（如果您的数组只有 0 和 1，您可以将它们设为二进制并使用按位 and/or):

matching_rows = X[(X[:,None]==Y.T[None,:]).all(-1).any(-1)]

输出：

array([[1, 0, 1],
       [1, 0, 0],
       [1, 1, 1]])

现在，X 中这些行的任意组合在 Y 的列中都有相应的存在。现在，如果您需要保持行在 X 中出现的顺序，请采用与上述顺序相同的所有行组合，否则，从上面获取行子集的所有排列。例如在上面的例子中，对应的子矩阵是：

from itertools import combinations 
n = matching_rows.shape[0]
#all possible combinations of matches
subsets = [list(combinations(np.arange(n), i)) for i in range(1, n)]
#[[(0,), (1,), (2,)], [(0, 1), (0, 2), (1, 2)]]


#all matching submatrices
[matching_rows[list(j)]  for i in subsets for j in i]

输出：

[array([[1, 0, 1]]), array([[1, 0, 0]]), array([[1, 1, 1]]), array([[1, 0, 1],
        [1, 0, 0]]), array([[1, 0, 1],
        [1, 1, 1]]), array([[1, 0, 0],
        [1, 1, 1]])]

Answer 3

将集合转换为数组：

In [290]: X = np.array([[1, 0, 1], [1, 0, 0], [0, 0, 1], [1, 1, 1], [0, 1, 1]])
In [291]: X
Out[291]: 
array([[1, 0, 1],
       [1, 0, 0],
       [0, 0, 1],
       [1, 1, 1],
       [0, 1, 1]])
In [292]: Y = np.array([[1, 1, 0], [1, 0, 0], [0, 0, 0], [1, 0, 0], [1, 0, 1], [1, 1, 1]])
In [293]: Y
Out[293]: 
array([[1, 1, 0],
       [1, 0, 0],
       [0, 0, 0],
       [1, 0, 0],
       [1, 0, 1],
       [1, 1, 1]])
In [294]: Y.T
Out[294]: 
array([[1, 1, 0, 1, 1, 1],
       [1, 0, 0, 0, 0, 1],
       [0, 0, 0, 0, 1, 1]])

由此很容易看出您的 M 示例是行或列的子集：

In [295]: X[[0,1,2],:]
Out[295]: 
array([[1, 0, 1],
       [1, 0, 0],
       [0, 0, 1]])
In [297]: Y.T[:,[0,2,4]]
Out[297]: 
array([[1, 0, 1],
       [1, 0, 0],
       [0, 0, 1]])

所以我可以把这个问题想象成搜索 2 个有效的索引数组的问题之一。蛮力方式将生成所有此类组合并测试哪些有效。从某种意义上说，这是“向量化”numpy 的方式 :) 但是进行某种树搜索可能更快，当部分选择失败时回溯。但是像这样的搜索问题并不是 numpy.

的强项

将行连接到具有指定列的矩阵的算法 space

Algorithm to concatenate rows into matrix with a specified column space

python

algorithm

numpy

matrix

linear-algebra