CODEWITHSUNDEEP
c++loopsrecursion
sparta93
sparta93

Reputation: 3854

How to recursively compare vectors?

I'm trying to write a function which recursively checks if a given vector A is in any contiguous block in vector B. For example, if A={5,6,7} and B={1,2,3,4,5,6,7}, it should return true. If B = {1,2,3,4,5,7,6}, it should return false. Currently, my code keeps outputting true because I don't think my logic is correct. I have not been able to modify it to produce any results yet. Any help will be appreciated!

bool r_app(vector<int>& a1, vector<int> b1, size_t k)
{
    k=0;

    if (a1.size() == 0) {
        cout << "true";
        return true;;
    }

    for (int i=0;i<a1.size();i++){
        for(int j=0;j<b1.size();j++){  
            if (a1.at(i)==b1.at(j)) {
                cout << "true" << endl;
                return true;
            }   
        }
        cout << "false" << endl;
        return false;    

        return r_app(a1,b1,k+1);   
    }
}

EDIT: So this is what I got from Smac89, and I added the cout lines so that when I call the function in main, it outputs either true or false. The function currently outputs true for every true input, but doesnt output false.. I'm not sure why.

bool r_app(std::vector<int>& a1, std::vector<int> &b1, std::size_t start)
{
    std::size_t savedPos = start + 1, k = 0;

    for (; k < a1.size() && start < b1.size() && a1[k] == b1[start]; 
         k++, start++)
    {
            if (k != 0 && a1[0] == b1[start])
                savedPos = start;
    }
    if (k == a1.size())
        cout << "true" << endl;
        return true;
    if (start < b1.size())
        return r_app(a1, b1, savedPos);

    cout << "false" << endl;  
    return false;
}

Upvotes: 1

Views: 1061

Answers (4)

Yue Wang
Yue Wang

Reputation: 1750

My try, using iterator:

#include <iostream>
#include <vector>
#include <algorithm>

template<typename Iter>
bool r_app(Iter first_a, Iter last_a, Iter first_b, Iter last_b)
{
    if(first_a == last_a)   //trivial case
        return true;

    auto found = std::find(first_b, last_b, *first_a);
    if(found == last_b)
        return false;
    else
        return r_app(++first_a, last_a, found, last_b);   //recursion
}

int main()
{
    std::vector<int> a{5,6,7};
    std::vector<int> b{1,2,3,4,5,6,7};
    std::cout << r_app(a.begin(),a.end(),b.begin(),b.end());

    return 0;
}

Upvotes: 0

smac89
smac89

Reputation: 43128

template <typename T>
bool r_app(std::vector<T>& a1, std::vector<T> &b1, std::size_t start) {
    std::size_t savedPos = start + 1, k = 0;

    for (; k < a1.size() && start < b1.size() && a1[k] == b1[start]; 
         k++, start++)
    {
            if (k != 0 && a1[0] == b1[start])
                savedPos = start;
    }
    if (k == a1.size())
        return true;
    if (start < b1.size())
        return r_app(a1, b1, savedPos);

    return false;
}

template <typename T>
bool r_app(std::vector<T>& a1, std::vector<T>& b1) {
    return r_app(a1, b1, 0);
}

Example: http://rextester.com/COR69755

EDIT: V2 Now more efficient searching - start a search either where the last search ended or at a character that matches the start of the search string

You can also print out where the first match occurred by looking at savedPos - 1

Upvotes: 1

cdhowie
cdhowie

Reputation: 169018

You need1 two recursive functions here if you want to do everything recursively.

One to test if the sequence is found at a particular point, and one to use this other function to test for equality at every point. Here is a simple template implementation that will work with any STL container that allows iteration, as well as non-STL sequences (such as raw arrays):

template <typename NeedleIterator, typename HaystackIterator = NeedleIterator>
bool recursive_sequence_equals(
    NeedleIterator needle_begin,
    NeedleIterator needle_end,
    HaystackIterator haystack_begin,
    HaystackIterator haystack_end)
{
    // The sequences are equal because we reached the end of the needle.
    if (needle_begin == needle_end) {
        return true;
    }

    // If we reached the end of the haystack, or the current elements are not equal
    // then the sequences are not equal here.
    if (haystack_begin == haystack_end || *needle_begin != *haystack_begin) {
        return false;
    }

    // We are not at the end of the haystack nor the needle, and the elements were
    // equal.  Move on to the next element.
    return recursive_sequence_equals(
        ++needle_begin, needle_end,
        ++haystack_begin, haystack_end);
}

template <typename NeedleIterator, typename HaystackIterator = NeedleIterator>
HaystackIterator recursive_sequence_find(
    NeedleIterator needle_begin,
    NeedleIterator needle_end,
    HaystackIterator haystack_begin,
    HaystackIterator haystack_end)
{
    // We reached the end with no match.
    if (haystack_begin == haystack_end) {
        return haystack_begin;
    }

    // If the sequences are equal at this point, return the haystack iterator.
    if (recursive_sequence_equals(needle_begin, needle_end,
                                  haystack_begin, haystack_end)) {
        return haystack_begin;
    }

    // Check the next position in the haystack.
    return recursive_sequence_find(
        needle_begin, needle_end,
        ++haystack_begin, haystack_end);
}

Used like this:

std::vector<int> a = { 5, 6, 7 };
std::vector<int> b = { 1, 2, 3, 4, 5, 6, 7 };

auto found = recursive_sequence_find(
    a.begin(), a.end(),
    b.begin(), b.end());

if (found != b.end()) {
    // There was a match, found is an iterator to the beginning of the match in b.
} else {
    // No match.  (Or both containers were empty!)
}

(Demo)

1 Technically you can do this with one function if you use some extra parameters to convey whether or not you are in the middle of an equality test. However this adds a lot of extra complication to the logic for no gain. It's easier and more straightforward to implement using two different recursive functions.

Upvotes: 1

Ashwani
Ashwani

Reputation: 2052

#include <stdio.h>
#include <string.h>
#include <vector>
#include <iostream>
using namespace std;
bool r_app(vector<int> a, vector<int> b, int starta, int startb)
{
    if(a.size() == 0) return 0;
    if(starta == 0) {
        int i=0;
        while(1) {
            while(a[0] != b[i] && i < b.size())
                i++;
            if(i >= b.size()) return 0;
            if(r_app(a, b, starta+1, i+1) == 1)
                return 1;
            else i++;
        }
    }
    else {
        if(starta == a.size())
            return 1;
        else if(startb == b.size())
            return 0;
        else if(a[starta] == b[startb])
            return r_app(a, b, starta+1, startb+1);
        else
            return 0;
    }   
}
int main() {
    vector<int> a;
    vector<int> b;
    b.push_back(1);
    b.push_back(2);
    b.push_back(3);
    b.push_back(4);
    b.push_back(5);
    a.push_back(3);
    a.push_back(4);
    cout << r_app(a,b,0,0);
    return 0;
}

It will be easier if you do not use recursion. Also, KMP algorithm will give you much optimized solution.

Upvotes: 0

Related Questions