Python中是否存在R语言get_rank_distance('ulam')的等效实现？

Hey there! Great question—let's break down how to get that Ulam distance functionality in Python, since there's no direct drop-in library equivalent to R's get_rank_distance with the 'ulam' parameter right now.

First, let's recap the Ulam distance definition you shared to make sure we're aligned:

相同元素数的两个排列p1和p2之间的Ulam距离，是将p1转换为p2所需的最少操作集数量，每个操作集包含1次删除、任意次数的移位以及1次插入刚删除的元素。

Key Insight: Ulam Distance and Longest Common Subsequence (LCS) #

The Ulam distance between two permutations of length n equals n minus the length of their longest common subsequence. This is because each Ulam operation removes one element that's not part of the shared "core" subsequence between the two permutations. We can leverage this relationship to build our own function easily.

Implementation Option: Custom Function #

Since there's no pre-built library function for this exact use case, here's a straightforward Python implementation based on the LCS relationship:

def longest_common_subsequence_length(a, b):
    n, m = len(a), len(b)
    # Initialize a DP table to store LCS lengths for subproblems
    dp = [[0] * (m + 1) for _ in range(n + 1)]
    
    for i in range(1, n + 1):
        for j in range(1, m + 1):
            if a[i-1] == b[j-1]:
                dp[i][j] = dp[i-1][j-1] + 1
            else:
                dp[i][j] = max(dp[i-1][j], dp[i][j-1])
    return dp[n][m]

def get_ulam_distance(perm1, perm2):
    if len(perm1) != len(perm2):
        raise ValueError("Both permutations must have the same length")
    lcs_length = longest_common_subsequence_length(perm1, perm2)
    return len(perm1) - lcs_length

Test It Out #

Let's verify with a quick example to ensure it works as expected:

# Example permutations
perm1 = [3, 1, 2, 4]
perm2 = [1, 2, 3, 4]

# Calculate Ulam distance
print(get_ulam_distance(perm1, perm2))  # Output: 1

This makes sense—we only need one Ulam operation (remove 3, shift the rest left, insert 3 at the end) to turn perm1 into perm2.

Alternative: Using Existing Libraries #

If you prefer to use established libraries, you could adapt functions from scipy or networkx, but they don't have a direct Ulam distance method. The custom function above is lightweight and aligns perfectly with the logic of R's get_rank_distance for the 'ulam' case.

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