在序列元素只能与相邻元素交换的要求下,如何计算两个序列的数字距离?不允许插入和删除.距离函数必须确定从一个字符串到达另一个字符串所需的交换操作数量.此外,距离函数不会为不同长度的序列定义,或者如果序列不共享相同的符号.最后,您可以假设序列中没有重复项.
根据我的研究,我需要像Damerau–Levenshtein distance这样的东西,但我不知道如何正确修改距离函数.
Example
对于序列ABC
,距离为1
的仅有两个有效变换是BAC
或ACB
.
Code
use std::collections::HashSet;
use std::hash::Hash;
fn dist<T: PartialEq + Eq + Hash>(lhs: &[T], rhs: &[T]) -> Option<usize> {
// Distance function is not defined for differing lengths
if lhs.len() != rhs.len() {
return None;
}
let lhs_c: HashSet<_> = lhs.iter().collect();
let rhs_c: HashSet<_> = rhs.iter().collect();
// Distance function is not defined if an element occurs more than once in each sequence
if lhs.len() != lhs_c.len() || rhs.len() != rhs_c.len() {
return None;
}
// Distance function is not defined if the sequences don't share all elements
if lhs_c != rhs_c {
return None;
}
// Calculate the edit distance of `lhs` and `rhs` with only adjacent transpositions.
todo!()
}
#[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"]));
}