在 Python 中从排列索引到排列矩阵

Question

我有两个索引列表。我想生成相关的置换矩阵。这两个列表具有相等的大小 n 并且具有从 0 到 n-1 的所有整数。

简单示例:

给定初始和最终索引（按照两行约定 https://en.wikipedia.org/wiki/Permutation_matrix）：

initial_index = [3,0,2,1] and final_index = [0,1,3,2]

换句话说，最后一个条目 (3) 必须转到第一个 (0)，第一个 (0) 必须转到第二个 (1) 等等。您还可以想象压缩这两个列出以获得排列规则：[(3,0),(0,1),(2,3),(1,2)]，读作 (3 -> 0),(0 -> 1 ) 等等。这是列表的右移，或列向量的下移。生成的置换矩阵应如下所示：

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

将此矩阵乘以列向量确实会根据需要将条目向下移动 1。

有没有什么相关的操作可以高效的做到这一点？

Answer 1

您需要一个 n×n 矩阵，其中对于从 0 到 n-1 的每个 i，行 final_index[i] 和列 initial_index[i] 的单元格设置为 1，并且每隔一个单元格设置为 0。

NumPy 高级索引可用于轻松设置这些单元格：

permutation_matrix = numpy.zeros((n, n), dtype=int)

permutation_matrix[final_index, initial_index] = 1

Answer 2

替代@user2357112 的好答案，您可以使用稀疏矩阵来提高内存效率：

from scipy.sparse import csr_matrix

permutation_matrix = csr_matrix((np.ones(n, dtype=int), (final_index, initial_index)), shape=(n,n))

# Use permutation_matrix.todense() to convert the matrix if needed

构建此稀疏矩阵的复杂度在时间和 space 上均为 O(n)，而对于密集矩阵，则为 O(n^2)。所以它们更适合大向量 (>1000)。

在 Python 中从排列索引到排列矩阵

Go from Permutation Indices to Permutation Matrix in Python

python

numpy

permutation