根据同一Vec的其他元素删除Vec元素的最佳方法

Question

我有一组集合,我想删除所有集合,这些集合是向量中其他集合的子集.例:

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

在这种情况下,我想删除b,因为它是一个子集a.我使用"哑"n²算法很好.

可悲的是,让它与借用检查器一起工作是非常棘手的.我想出的最好的是(游乐场):

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);
}

(注意:上面的代码不正确!有关详细信息,请参阅注释)

我看到一些缺点:

• 我需要一个额外的分配矢量
• 也许有比swap_remove经常打电话更有效的方式
• 如果我需要保留订单,我不能使用swap_remove,但必须使用remove哪个很慢

有一个更好的方法吗？我不只是询问我的用例,而是关于标题中描述的一般情况.

Answer 1

这是一个不进行额外分配并保留订单的解决方案:

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);
}

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