Array Comparison

help
#1

How to compare two array if the two arrays are equal, first array is the sub array of the second or vice versa

#2

What do or don't you consider a "sub-array"?

1 Like
#3

If you mean (unordered) "sets" rather than (ordered) arrays, you might like HashSet::is_subset.

2 Likes
#4

If you care about "order", then you may use "string" match algorithm(eg. KMP). Here is brute force(O(mn)) solution:

fn sub_array(s: &[i32], t: &[i32]) {
    let (m, n) = (s.len(), t.len());
    if m < n {
        return sub_array(t, s);  // swap(t, s)
    } else {
        for i in 0..m {
            let mut j = 0;
            while j < n && s[i+j] == t[j] {
                j += 1;
            }
            if j == n {
                if n == m {
                    println!("{:?} = {:?}", s, t);
                } else {  // m>n
                    println!("{:?} ∈ {:?}", t, s);
                }
                return ();
            }
        }
    }
    println!("{:?} not in {:?}", t, s);
}

fn main() {
    sub_array(&[1, 2, 3, 4, 5], &[2, 3]);
    sub_array(&[2, 3], &[1, 2, 3, 4, 5]);
    sub_array(&[1], &[5]);
    sub_array(&[2, 3], &[2, 3]);
}

If you do not care about "order", then you may use HashMap to count each element, and check s in t :

fn sub_array(s: &[i32], t: &[i32]) {
    let (m, n) = (s.len(), t.len());
    if m < n {
        return sub_array(t, s);  // swap(t, s)
    } else {
        use std::collections::{HashMap, hash_map::Entry};
        let mut cnt_s = HashMap::new();
        for &x in s {
            cnt_s.entry(x).and_modify(|v| *v += 1).or_insert(1);
        }
        for &x in t {
            match cnt_s.entry(x) {
                Entry::Occupied(mut entry) => {
                    *entry.get_mut() -= 1;
                    if *entry.get_mut() == 0 {  // drop
                        cnt_s.remove(&x);
                    }
                }
                Entry::Vacant(_) => {
                    println!("{:?} not in  {:?}", t, s);
                    return ();
                }
            }
        }
        // t∈s or t=s
        if cnt_s.len() == 0 {
            println!("{:?} = {:?}", t, s);
        } else {
            println!("{:?} ∈ {:?}", t, s);
        }
    }
}

fn main() {
    sub_array(&[1, 2, 2, 3, 4, 5], &[2, 2]);
    sub_array(&[2, 2, 2], &[1, 2, 2, 3, 4, 5]);
    sub_array(&[3, 4], &[1, 2, 3, 4, 5]);
    sub_array(&[1], &[5]);
    sub_array(&[2, 3, 3], &[2, 3, 3]);
}
1 Like
#5

Thanks for the detailed reply. Let me check if it serve the purpose.

#6
  • A = [1, 2, 3], B = [1, 2, 3, 4, 5], A is a sublist of B
  • A = [3, 4, 5], B = [1, 2, 3, 4, 5], A is a sublist of B
  • A = [3, 4], B = [1, 2, 3, 4, 5], A is a sublist of B
  • A = [1, 2, 3], B = [1, 2, 3], A is equal to B
  • A = [1, 2, 3, 4, 5], B = [2, 3, 4], A is a superlist of B
  • A = [1, 2, 4], B = [1, 2, 3, 4, 5], A is not a superlist of, sublist of or equal to B
1 Like
#7

Searching for existing crates with a general (i.e. supporting all kinds of item types) efficient sub-string search algorithm, I came across e.g. this one: https://crates.io/crates/galil-seiferas

For string-search on str or [u8] in particular, there seems to be a lot more options.

1 Like