如何计算仅允许相邻交换的同构无重复序列间编辑距离

你要的这种距离本质上是排列的逆序数——当两个序列是同一元素集合的无重复排列时，将一个序列通过相邻交换转换为另一个序列的最小交换次数，等于把原序列映射为目标序列的索引序列后的逆序数。

核心思路 #

1. 验证序列合法性：长度相同、元素集合一致、无重复（这部分你已实现）。
2. 建立目标序列的元素到索引的映射：比如目标序列["a","b","c"]对应映射a→0, b→1, c→2。
3. 将原序列转换为基于该映射的索引序列：比如原序列["b","a","c"]会被转换成[1,0,2]。
4. 计算该索引序列的逆序数，这个数值就是所需的最小相邻交换次数。

完整实现代码 #

use std::collections::{HashMap, HashSet};
use std::hash::Hash;

fn dist<T: PartialEq + Eq + Hash + Clone>(lhs: &[T], rhs: &[T]) -> Option<usize> {
    // 长度不同则距离无定义
    if lhs.len() != rhs.len() {
        return None;
    }

    let lhs_c: HashSet<_> = lhs.iter().collect();
    let rhs_c: HashSet<_> = rhs.iter().collect();

    // 存在重复元素则距离无定义
    if lhs.len() != lhs_c.len() || rhs.len() != rhs_c.len() {
        return None;
    }

    // 元素集合不同则距离无定义
    if lhs_c != rhs_c {
        return None;
    } 

    // 建立目标序列元素到索引的映射
    let elem_to_idx: HashMap<_, _> = rhs.iter().enumerate().map(|(i, elem)| (elem, i)).collect();
    
    // 将原序列转换为索引序列
    let mut idx_sequence: Vec<usize> = lhs.iter().map(|elem| elem_to_idx[elem]).collect();
    
    // 用归并排序法计算逆序数，时间复杂度O(n log n)
    count_inversions(&mut idx_sequence)
}

// 归并排序法计算逆序数
fn count_inversions(arr: &mut [usize]) -> Option<usize> {
    let n = arr.len();
    if n <= 1 {
        return Some(0);
    }

    let mid = n / 2;
    let mut left = arr[0..mid].to_vec();
    let mut right = arr[mid..n].to_vec();

    let mut inv_count = count_inversions(&mut left)? + count_inversions(&mut right)?;

    let mut i = 0;
    let mut j = 0;
    let mut k = 0;

    while i < left.len() && j < right.len() {
        if left[i] <= right[j] {
            arr[k] = left[i];
            i += 1;
        } else {
            arr[k] = right[j];
            inv_count += left.len() - i;
            j += 1;
        }
        k += 1;
    }

    while i < left.len() {
        arr[k] = left[i];
        i += 1;
        k += 1;
    }

    while j < right.len() {
        arr[k] = right[j];
        j += 1;
        k += 1;
    }

    Some(inv_count)
}

#[test]
fn dist_is_none_for_differing_lengths() {
    assert_eq!(None, dist(&["b", "a", "c"], &["a", "b", "c", "d"]));
}

#[test]
fn dist_is_none_with_duplicates() {
    assert_eq!(None, dist(&["b", "a", "c", "a"], &["a", "b", "c", "d"]));
    assert_eq!(None, dist(&["a", "b", "c", "d"], &["a", "b", "c", "c"]));
}

#[test]
fn dist_is_none_with_non_empty_difference() {
    assert_eq!(None, dist(&["a", "b", "c"], &["d", "e", "f"]));
}

#[test]
fn dist_bac_to_abc_is_one() {
    assert_eq!(Some(1), dist(&["b", "a", "c"], &["a", "b", "c"]));
}

#[test]
fn dist_bca_to_bac_is_one() {
    assert_eq!(Some(1), dist(&["b", "c", "a"], &["b", "a", "c"]));
}

#[test]
fn dist_cab_to_abc_is_two() {
    assert_eq!(Some(2), dist(&["c", "a", "b"], &["a", "b", "c"]));
}

#[test]
fn dist_cdab_to_abcd_is_four() {
    assert_eq!(Some(4), dist(&["c", "d", "a", "b"], &["a", "b", "c", "d"]));
}

正确性说明 #

每次相邻交换只能消除一个逆序对，而将一个排列转换为目标排列对应的索引序列的最小交换次数，恰好等于该序列的逆序数——逆序数代表了序列中所有“位置颠倒”的元素对数量，每一次相邻交换最多修正一个这样的对。

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