Rust最长递增子序列算法库longest-increasing-subsequence的使用，高效求解序列中最长递增子序列问题

Rust最长递增子序列算法库longest-increasing-subsequence的使用，高效求解序列中最长递增子序列问题

最长递增子序列

最长递增子序列问题是在给定序列中找到一个子序列，其中子序列的元素按排序顺序从最低到最高排列，并且子序列尽可能长。这个子序列不一定是连续的，也不一定是唯一的。

例如，考虑这个整数序列：

2, 9, 4, 7, 3, 4, 5

这个序列的最长递增子序列（LIS）是 2, 3, 4, 5。

注意，并不总是存在单一的LIS。考虑这个序列：

2, 6, 5

在这个序列中，2, 5 和 2, 6 都是LIS。

API

这个crate提供了两个函数来在切片中查找最长递增子序列：

  1. 高级、易用的 lis 函数接受任何 T: Ord 的切片，并返回LIS作为指向该切片的索引向量。

  2. 低级的 lis_with 函数接受自定义比较器，并允许您自带分配（这使您可以选择重用分配或使用自定义分配器）。

两个函数都使用相同的基础算法。它们在 O(n log n) 时间内执行，并使用 O(n) 内存。

示例

use longest_increasing_subsequence::lis;

let xs = vec![9, 2, 8, 3, 5];
for i in lis(&xs) {
    println!("{} at index {}", xs[i], i);
}

// 打印:
// 2 at index 1
// 3 at index 3
// 5 at index 4

完整示例代码

// 添加依赖到Cargo.toml: longest-increasing-subsequence = "0.1.0"

use longest_increasing_subsequence::lis;

fn main() {
    // 示例1: 基本使用
    let numbers = vec![2, 9, 4, 7, 3, 4, 5];
    let lis_indices = lis(&numbers);
    
    println!("原始序列: {:?}", numbers);
    println!("LIS索引: {:?}", lis_indices);
    println!("LIS值: {:?}", lis_indices.iter().map(|&i| numbers[i]).collect::<Vec<_>>());
    
    // 示例2: 处理可能有多个LIS的情况
    let another_sequence = vec![2, 6, 5];
    let another_lis = lis(&another_sequence);
    
    println!("\n另一个序列: {:?}", another_sequence);
    println!("LIS索引: {:?}", another_lis);
    println!("LIS值: {:?}", another_lis.iter().map(|&i| another_sequence[i]).collect::<Vec<_>>());
    
    // 示例3: 字符串序列
    let words = vec!["apple", "banana", "cherry", "date", "elderberry"];
    let word_lis = lis(&words);
    
    println!("\n字符串序列: {:?}", words);
    println!("LIS索引: {:?}", word_lis);
    println!("LIS值: {:?}", word_lis.iter().map(|&i| words[i]).collect::<Vec<_>>());
}

1 回复

Rust最长递增子序列算法库：longest-increasing-subsequence

介绍

longest-increasing-subsequence是一个专门用于求解最长递增子序列（Longest Increasing Subsequence, LIS）问题的Rust算法库。该库提供了高效的实现，能够快速找到给定序列中的最长递增子序列，支持返回子序列长度或具体的子序列元素。

安装方法

在Cargo.toml中添加依赖：

[dependencies]
longest-increasing-subsequence = "0.2.0"

使用方法

基础用法：获取最长递增子序列长度

use longest_increasing_subsequence::lis;

fn main() {
    let nums = vec![10, 9, 2, 5, 3, 7, 101, 18];
    let length = lis::length(&nums);
    println!("最长递增子序列长度: {}", length); // 输出: 4
}

获取具体的最长递增子序列

use longest_increasing_subsequence::lis;

fn main() {
    let nums = vec![10, 9, 2, 5, 3, 7, 101, 18];
    let subsequence = lis::sequence(&nums);
    println!("最长递增子序列: {:?}", subsequence); // 输出: [2, 3, 7, 101]
}

处理自定义类型

use longest_increasing_subsequence::lis;
use std::cmp::Ordering;

#[derive(Debug, Clone)]
struct Person {
    name: String,
    age: u32,
}

impl PartialOrd for Person {
    fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
        self.age.partial_cmp(&other.age)
    }
}

impl PartialEq for Person {
    fn eq(&self, other: &Self) -> bool {
        self.age == other.age
    }
}

fn main() {
    let people = vec![
        Person { name: "Alice".to_string(), age: 25 },
        Person { name: "Bob".to_string(), age: 20 },
        Person { name: "Charlie".to_string(), age: 30 },
        Person { name: "David".to_string(), age: 22 },
    ];
    
    let lis_people = lis::sequence(&people);
    println!("按年龄的最长递增子序列: {:?}", lis_people);
}

使用自定义比较函数

use longest_increasing_subsequence::lis_with_cmp;

fn main() {
    let nums = vec![10, 9, 2, 5, 3, 7, 101, 18];
    
    let subsequence = lis_with_cmp(&nums, |a, b| a < b);
    println!("自定义比较的最长递增子序列: {:?}", subsequence);
}

性能特点

  • 时间复杂度：O(n log n)
  • 空间复杂度：O(n)
  • 支持泛型，可处理任何实现了PartialOrd trait的类型
  • 提供长度计算和具体序列获取两种接口

注意事项

  1. 输入序列中的元素必须实现PartialOrd trait
  2. 对于相等元素，默认情况下不会被视为递增关系
  3. 库提供了lis::length()和lis::sequence()两个主要函数

这个库为处理最长递增子序列问题提供了简单易用且高效的解决方案，适合在需要此类算法的各种场景中使用。

完整示例demo

// 引入最长递增子序列库
use longest_increasing_subsequence::{lis, lis_with_cmp};
use std::cmp::Ordering;

// 自定义Person结构体
#[derive(Debug, Clone)]
struct Person {
    name: String,
    age: u32,
}

// 为Person实现PartialOrd trait，按年龄比较
impl PartialOrd for Person {
    fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
        self.age.partial_cmp(&other.age)
    }
}

// 为Person实现PartialEq trait，按年龄判断相等
impl PartialEq for Person {
    fn eq(&self, other: &Self) -> bool {
        self.age == other.age
    }
}

fn main() {
    println!("=== 基础用法示例 ===");
    
    // 示例1：获取最长递增子序列长度
    let nums = vec![10, 9, 2, 5, 3, 7, 101, 18];
    let length = lis::length(&nums);
    println!("序列: {:?}", nums);
    println!("最长递增子序列长度: {}", length); // 输出: 4
    
    // 示例2：获取具体的最长递增子序列
    let subsequence = lis::sequence(&nums);
    println!("最长递增子序列: {:?}", subsequence); // 输出: [2, 3, 7, 101]
    
    println!("\n=== 处理自定义类型示例 ===");
    
    // 示例3：处理自定义Person类型
    let people = vec![
        Person { name: "Alice".to_string(), age: 25 },
        Person { name: "Bob".to_string(), age: 20 },
        Person { name: "Charlie".to_string(), age: 30 },
        Person { name: "David".to_string(), age: 22 },
    ];
    
    let lis_people = lis::sequence(&people);
    println!("人员列表:");
    for person in &people {
        println!("  {}: {}岁", person.name, person.age);
    }
    println!("按年龄的最长递增子序列:");
    for person in lis_people {
        println!("  {}: {}岁", person.name, person.age);
    }
    
    println!("\n=== 使用自定义比较函数示例 ===");
    
    // 示例4：使用自定义比较函数（降序）
    let nums2 = vec![10, 9, 2, 5, 3, 7, 101, 18];
    let subsequence_desc = lis_with_cmp(&nums2, |a, b| a > b);
    println!("序列: {:?}", nums2);
    println!("自定义比较（降序）的最长递增子序列: {:?}", subsequence_desc);
}
回到顶部