根据同一 Vec 的其他元素删除 Vec 元素的最佳方法 [英] Best way to remove elements of Vec depending on other elements of the same Vec

问题描述

我有一个集合向量，我想删除向量中其他集合的子集的所有集合.示例:

I have a vector of sets and I want to remove all sets that are subsets of other sets in the vector. Example:

a = {0, 3, 5}
b = {0, 5}
c = {0, 2, 3}

在这种情况下，我想删除 b，因为它是 a 的子集.我可以使用愚蠢的"n² 算法.

In this case I would like to remove b, because it's a subset of a. I'm fine with using a "dumb" n² algorithm.

遗憾的是，让它与借用检查器一起工作非常棘手.我想出的最好的是 (Playground):

Sadly, it's pretty tricky to get it working with the borrow checker. The best I've come up with is (Playground):

let mut v: Vec<HashSet<u8>> = vec![];

let mut to_delete = Vec::new();
for (i, set_a) in v.iter().enumerate().rev() {
    for set_b in &v[..i] {
        if set_a.is_subset(&set_b) {
            to_delete.push(i);
            break;
        }
    }
}

for i in to_delete {
    v.swap_remove(i);
}

(注意:上面的代码不正确！更多细节见评论)

(note: the code above is not correct! See comments for further details)

我看到了一些缺点:

• 我需要一个带有额外分配的额外向量
• 也许有比经常调用 swap_remove 更有效的方法
• 如果我需要保留顺序，我不能使用swap_remove，而必须使用remove，这很慢

• I need an additional vector with additional allocations
• Maybe there are more efficient ways than calling swap_remove often
• If I need to preserve order, I can't use swap_remove, but have to use remove which is slow

有没有更好的方法来做到这一点?我不只是问我的用例，而是标题中描述的一般情况.

Is there a better way to do this? I'm not just asking about my use case, but about the general case as it's described in the title.

推荐答案

这里有一个不做额外分配并保留顺序的解决方案:

Here is a solution that does not make additional allocations and preserves the order:

fn product_retain<T, F>(v: &mut Vec<T>, mut pred: F)
    where F: FnMut(&T, &T) -> bool
{
    let mut j = 0;
    for i in 0..v.len() {
        // invariants:
        // items v[0..j] will be kept
        // items v[j..i] will be removed
        if (0..j).chain(i + 1..v.len()).all(|a| pred(&v[i], &v[a])) {
            v.swap(i, j);
            j += 1;
        }
    }
    v.truncate(j);
}

fn main() {
    // test with a simpler example
    // unique elements
    let mut v = vec![1, 2, 3];
    product_retain(&mut v, |a, b| a != b);
    assert_eq!(vec![1, 2, 3], v);

    let mut v = vec![1, 3, 2, 4, 5, 1, 2, 4];
    product_retain(&mut v, |a, b| a != b);
    assert_eq!(vec![3, 5, 1, 2, 4], v);
}

这是一种分区算法.第一个分区中的元素将被保留，第二个分区中的元素将被删除.

This is a kind of partition algorithm. The elements in the first partition will be kept and in the second partition will be removed.

这篇关于根据同一 Vec 的其他元素删除 Vec 元素的最佳方法的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！