取決於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這是慢

我從Vec<usize>改變to_delete到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具有哪些不能正常條件下發生的特殊值，可以使用它將hashmap標記爲「要刪除」，然後在retain中檢查該條件（它需要將外部循環從基於迭代器的變爲基於範圍的）。

---

阿里納斯（如果HashSet<u8>不僅僅是一個玩具爲例）：存儲和比較套小整數更多eficient方法是使用bitset。