如何根据数组a的大小顺序获取数组b的排列索引？

给定两个数组：

julia> a = [30, 14, 10, 21] 
julia> b = [2, 8, 24, 1]

需要获取数组b的排列索引perm_ixs，使得b的元素大小顺序与a的元素大小顺序对应。

示例说明 #

比如目标排列索引perm_ixs = [3, 1, 4, 2]，此时：

julia> b[perm_ixs]
4-element Vector{Int64}:
 24
  2
  1
  8

逻辑对应：b中的元素2是第三大元素，对应a中第三大的元素是索引2的14，因此排列后的b第二个元素应为2。

现有初级实现 #

当前的实现代码如下：

julia> function get_size_based_permutation(a, b)
    @assert length(a) == length(b)

    # 获取元素相对大小的排名向量，1表示最大，n表示最小
    @show sizes_a = invperm(sortperm(a; rev=true))
    @show sizes_b = invperm(sortperm(b; rev=true))

    # 将b中元素的排名对应到a的排名位置，生成排列索引
    p = collect(1:length(sizes_a))
    for (ix, size_of_ele_in_b) in enumerate(sizes_b)
        matching_size_ix = findfirst(ele -> ele == size_of_ele_in_b, sizes_a)
        p[matching_size_ix] = ix 
    end

    return p
end
julia> a = [30, 14, 10, 21] 
julia> b = [2, 8, 24, 1]
julia> perm_ixs = get_size_based_permutation(a, b)
sizes_a = invperm(sortperm(a; rev = true)) = [1, 3, 4, 2]
sizes_b = invperm(sortperm(b; rev = true)) = [3, 2, 1, 4]
4-element Vector{Int64}:
 3
 1
 4
 2

julia> b[perm_ixs]
4-element Vector{Int64}:
 24
  2
  1
  8

更高效的实现方式 #

现有实现中循环内的findfirst会导致时间复杂度达到O(n²)，数组规模较大时效率低下。可以利用排列的性质直接构建映射，将时间复杂度优化到O(n log n)：

function get_size_based_permutation_opt(a, b)
    @assert length(a) == length(b)
    # 获取a降序排列的索引
    perm_a = sortperm(a; rev=true)
    # 获取b降序排列的索引，perm_b[i]对应b中第i大元素的位置
    perm_b = sortperm(b; rev=true)
    # 通过逆排列将a的原位置映射到排名，再对应到b的同排名元素索引
    return perm_b[invperm(perm_a)]
end

测试验证：

julia> a = [30, 14, 10, 21] 
julia> b = [2, 8, 24, 1]
julia> perm_ixs = get_size_based_permutation_opt(a, b)
4-element Vector{Int64}:
 3
 1
 4
 2

julia> b[perm_ixs]
4-element Vector{Int64}:
 24
  2
  1
  8

原理说明 #

1. sortperm(a; rev=true)得到a降序排列的索引perm_a，比如示例中perm_a = [1,4,2,3]，表示a中第1大元素在索引1，第2大在索引4，以此类推。
2. invperm(perm_a)生成每个原索引对应的排名，结果和之前的sizes_a完全一致：[1,3,4,2]。
3. sortperm(b; rev=true)得到b降序排列的索引perm_b = [3,2,1,4]，表示b中第1大元素在索引3，第2大在索引2等。
4. perm_b[invperm(perm_a)]直接将a原位置的排名对应到b中同排名元素的索引，一步生成目标排列，效率远高于原实现。

内容的提问来源于stack exchange，提问作者Jared