Лучший способ удалить элементы Vec в зависимости от других элементов того же Vec

Question

У меня есть вектор множеств, и я хочу удалить все наборы, которые являются подмножествами других множеств в векторе. Пример:

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

В этом случае я хотел бы удалить b, потому что это подмножество a. Я в порядке с использованием «немого» алгоритма n².

К сожалению, довольно сложно заставить его работать с заемщиком. Лучшее, что я придумал это (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); 
} 

(примечание: приведенный выше код не исправить Смотрите комментарии для получения более подробной информации!)

Я вижу несколько недостатков:

• мне нужен дополнительный вектор с дополнительными ассигнованиями
• Может быть, есть более эффективные способы, чем вызов 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); 
} 

Это является своего рода алгоритм разбиения. Элементы в первом разделе будут сохранены, а во втором разделе будут удалены.

Answer 2

Вы можете использовать while петлю вместо for:

use std::collections::HashSet; 

fn main() { 
    let arr: &[&[u8]] = &[ 
     &[3], 
     &[1,2,3], 
     &[1,3], 
     &[1,4], 
     &[2,3] 
    ]; 

    let mut v:Vec<HashSet<u8>> = arr.iter() 
     .map(|x| x.iter().cloned().collect()) 
     .collect(); 

    let mut pos = 0; 
    while pos < v.len() { 
     let is_sub = v[pos+1..].iter().any(|x| v[pos].is_subset(x)) 
      || v[..pos].iter().any(|x| v[pos].is_subset(x)); 

     if is_sub { 
      v.swap_remove(pos); 
     } else { 
      pos+=1; 
     } 
    } 
    println!("{:?}", v); 
} 

Там нет никаких дополнительных ассигнований.

---

Чтобы избежать использования remove и swap_remove, вы можете изменить тип вектора к Vec<Option<HashSet<u8>>>:

use std::collections::HashSet; 

fn main() { 
    let arr: &[&[u8]] = &[ 
     &[3], 
     &[1,2,3], 
     &[1,3], 
     &[1,4], 
     &[2,3] 
    ]; 

    let mut v:Vec<Option<HashSet<u8>>> = arr.iter() 
     .map(|x| Some(x.iter().cloned().collect())) 
     .collect(); 

    for pos in 0..v.len(){ 
     let is_sub = match v[pos].as_ref() { 
      Some(chk) => 
       v[..pos].iter().flat_map(|x| x).any(|x| chk.is_subset(x)) 
       || v[pos+1..].iter().flat_map(|x| x).any(|x| chk.is_subset(x)), 
      None => false, 
     }; 

     if is_sub { v[pos]=None };//Replace with None instead remove 

    } 
    println!("{:?}", v);//[None, Some({3, 2, 1}), None, Some({1, 4}), None] 
} 

Answer 3

• Мне нужно еще один вектор с дополнительными ассигнованиями

Я бы не волновался это распределение, так как память и время выполнения этого распределения будут очень малы по сравнению с остальной частью вашего алгоритма.

• Может быть, есть более эффективные способы, чем вызов swap_remove часто.
• Если мне нужно сохранить порядок, я не могу использовать swap_remove, но должны использовать remove, который медленно

Я изменил бы to_delete от Vec<usize> до Vec<bool> и просто отметьте, должен ли конкретный HashMap быть удален.Затем вы можете использовать Vec::retain, который условно удаляет элементы при сохранении порядка. К сожалению, эта функция не проходит индекс к закрытию, поэтому мы должны создать обходной путь (playground):

let mut to_delete = vec![false; v.len()]; 
for (i, set_a) in v.iter().enumerate().rev() { 
    for set_b in &v[..i] { 
     if set_a.is_subset(&set_b) { 
      to_delete[i] = true; 
     } 
    } 
} 

{ 
    // This assumes that retain checks the elements in the order. 
    let mut i = 0; 
    v.retain(|_| { 
     let ret = !to_delete[i]; 
     i += 1; 
     ret 
    }); 
} 

Если HashMap имеет особое значение, которое никогда не может произойти в нормальных условиях, вы можете использовать он должен помечать хэш-карту как «удалить», а затем проверить это условие в retain (для этого потребуется изменить внешний цикл с итератора на основе диапазона).

---

Sidenote (если это HashSet<u8> не просто игрушка пример): Более eficient способ хранения и сравнения множества малых чисел будет использовать bitset.