CODEWITHSUNDEEP
c++algorithm
milesma
milesma

Reputation: 1591

How to test if a sequence is conform to another sequence in a given pattern?

What's name of the following described algorithm?

description:

How to test if a sequence is a conform to another in a given pattern?

For example:

The pattern: the number appears in the same order.


bool isOrderValid(vector<int>& mainVec, vector<int>& subVec) {
    // how to implement this function?
}

test#1: isOrderValid({1, 2, 3, 4}, {2, 4}); // should return true
test#2: isOrderValid({1, 2, 3, 4}, {4, 2}); // should return false

Explanation:

test #1: the sub sequence is 2, 4; in the main sequence, 2 appear ahead of 4, so the order is correct.

test #2: the sub sequence is 4, 2; in the main sequence, however, 4 appear after 2, so the order is incorrect.

Note: there might be duplicate entry in both array. For example:

isOrderValid({3, 6, 3, 1, 2, 3}, {3, 1, 3}); // should return true

Upvotes: 1

Views: 84

Answers (2)

Blastfurnace
Blastfurnace

Reputation: 18652

You could write a standard library style algorithm for this. This example takes two iterator pairs and returns a bool:

#include <iostream>
#include <vector>

template <typename InIt1, typename InIt2>
bool is_subsequence(InIt1 first1, InIt1 last1, InIt2 first2, InIt2 last2)
{
    if (first2 == last2) {
        return false; // sub empty (should this return true?)
    }
    for (; first1 != last1; ++first1) {
        if (*first1 == *first2) {
            if (++first2 == last2) {
                return true; // sub exhausted
            }
        }
    }
    return false; // seq exhausted
}

int main()
{
    std::vector<int> a = { 1, 2, 3, 4 }, b = { 2, 4 }, c = { 4, 2 };
    std::vector<int> d = { 3, 6, 3, 1, 2, 3 }, e = { 3, 1, 3 };

    std::cout << is_subsequence(a.begin(), a.end(), b.begin(), b.end()) << '\n';
    std::cout << is_subsequence(a.begin(), a.end(), c.begin(), c.end()) << '\n';
    std::cout << is_subsequence(d.begin(), d.end(), e.begin(), e.end()) << '\n';
}

Executed on ideone.com

If you like writing generic functions you can make this more flexible and easier to use:

#include <iostream>
#include <list>
#include <vector>

template <typename InIt1, typename InIt2, typename Compare = std::equal_to<>>
bool is_subsequence(InIt1 first1, InIt1 last1, InIt2 first2, InIt2 last2, Compare cmp = Compare{})
{
    if (first2 == last2) {
        return false; // sub empty (should this return true?)
    }
    for (; first1 != last1; ++first1) {
        if (cmp(*first1, *first2)) {
            if (++first2 == last2) {
                return true; // sub exhausted
            }
        }
    }
    return false; // seq exhausted
}

template <typename Seq, typename Sub, typename Compare = std::equal_to<>>
bool is_subsequence(const Seq &seq, const Sub &sub, Compare cmp = Compare{})
{
    return is_subsequence(std::begin(seq), std::end(seq), std::begin(sub), std::end(sub), cmp);
}

int main()
{
    std::vector<int> a = { 1, 2, 3, 4 }, b = { 2, 4 };
    std::list<int> c = { 4, 2 };
    std::vector<int> d = { 3, 6, 3, 1, 2, 3 };
    int e[] = { 3, 1, 3 };

    std::cout << is_subsequence(a, b) << '\n';
    std::cout << is_subsequence(a, b, [](int lhs, int rhs) { return lhs == rhs; }) << '\n';
    std::cout << is_subsequence(a, c) << '\n';
    std::cout << is_subsequence(d, e) << '\n';
}

Executed on ideone.com

Upvotes: 1

user4668606
user4668606

Reputation:

This can be implemented pretty simple (i use function-objects here):

class base_pattern_matcher{
    public:
        virtual bool operator()(const vector<int>& a , const vector<int>& b) = 0;
}

class in_order_pattern_matcher : public base_pattern_matcher{
    public:
        bool operator()(const vector<int>& a , const vector<int>& b){
            vector<int>::iterator iter_a = a.begin() , iter_b = b.begin();

            while(iter_b != b.end() && iter_a != a.end()){
                if(*iter_b == *iter_a)
                    //we found an occurence in a that matches the searched element in b
                    //--> search for the next element
                    iter_b++;

                 //check if the next element matches the searched element
                 iter_a++;
            }

            //we have found all elements of b in the given order
            return iter_b == b.end();
        };
}

isOrderValid(const vector<int>& a , const vector<int>& b , const base_pattern_matcher& matcher){
    return matcher(a , b);
}

Upvotes: 2

Related Questions