Search code examples
c++stdvector

Find shift of cyclic permutation of two sequences

I need to find shift of two cyclic permutations of sequences.

EXAMPLE:

3 5 1 2 4 3 5 7 8 1 2 5 9 4 7

5 7 8 1 2 5 9 4 7 3 5 1 2 4 3

Second sequence is cyclic permutaion of first with shift 6.

My algorithm:

  • if sequences are equal return 0 as shift
  • if they are not equal, sort them and then check if they have same elements
  • if they don't have same elements they are not cyclic permutation
  • if they have same elements, first element of first vector move to the end of vector and then make temp vector of first two elements of first vector, find that temp vector in second vector and shift is equal to b.size() - i + 1;

For example I get following error

terminate called after throwing an instance of 'std::out_of_range'
what(): vector::_M_range_check: __n (which is 15) >= this->size() (which is 15)

and if I try other sequences result is not correct.

#include <iostream>
#include <algorithm>
#include <vector>
#include <cstdlib>
int sequences_are_equal = 0;
bool sequences_have_same_elements(std::vector < int > a, std::vector < int > b) {
  sequences_are_equal = 0;
  if (a.size() != b.size())
    return false;
  for (int i = 0; i < a.size(); i++)
    if (a.at(i) == b.at(i))
      sequences_are_equal++;
  if (sequences_are_equal == a.size()) return true;
  sort(a.begin(), a.end());
  sort(b.begin(), b.end());
  for (int i = 0; i < a.size(); i++)
    if (a.at(i) != b.at(i))
      return false;
  return true;
}

int CyclicPermutation(std::vector < int > a, std::vector < int > b) {
  int shift = -1;
  std::vector < int > temp(a.size(), 0);
  std::vector < int > help(a.size(), 0);
  if (sequences_have_same_elements(a, b)) {
    int x = a.at(0);
    a.erase(a.begin());
    a.push_back(x);
    temp.push_back(a.at(0));
    temp.push_back(a.at(1));
    for (int i = 0; i < b.size(); i++) {
      help.push_back(b.at(i));
      help.push_back(b.at(i + 1));
      if (temp == help) {
        shift = b.size() - i + 1;
        break;
      }
      help.clear();
    }
  }
  if (sequences_are_equal == a.size()) return 0;
  return shift;
}

int main() {
  int x;
  std::vector < int > a, b;
  std::cout << "First sequence: ";
  while (std::cin >> x)
    a.push_back(x);
  std::cin.clear();
  std::cin.ignore(1000, '\n');
  std::cout << "Second sequence: ";
  while (std::cin >> x)
    b.push_back(x);
  if (CyclicPermutation(a, b) == -1)
    std::cout << "Second sequence is not cyclic permutaion of first.";
  else
    std::cout << "Second sequence is cyclic permutaion of first with shift " << CyclicPermutation(a, b) << ".";

  return 0;
}

Could you explain me where did I make mistake in my algorithm and code? How to modify this to work correct?

Solution

  • Your design is wrong.

    It seems that you simply want to rotate elements in a std::vector.

    The exception is because of an out of bounds error: help.push_back(b.at(i + 1));

    There is a strange handling with "help" and "temp". You first create "help" and "temp" with n 0es in it. Then you push back stuff, but only 2 elements. So, if for example the original vector size is 4, then your vectors will be 0,0,0,0,x,y.

    That is rather strange, or, I do not understand it.

    What you should do:

    1. Check, if the size of the 2 vectors is equal
    2. Check, if the vectors are equal using the existing == operator
    3. Rotate the vectors elements for mx "size" times. Count the number of rotations
    4. Go back to 2

    You can either use the existing function std::rotate(see here) or write a simple function by yourself.

    You could modify your function like this:

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

void rotateLeft(std::vector<int>& a) {
    if (a.size() > 0) {
        int tmp = a[0];
        for (size_t k{}; k < a.size() - 1; ++k)
            a[k] = a[k + 1];
        a.back() = tmp;
    }
}

int CyclicPermutation(std::vector<int>& a, std::vector<int>& b) {

    // Set result to invalid
    int result{ -1 };

    int shiftCounter{};
    // Only do something if the sizes are different
    if (a.size() == b.size()) {

        // Rotate until numbers are equal
        while ((a != b) and (shiftCounter++ < a.size())) {
            //std::rotate(a.begin(), a.begin() + 1, a.end());
            rotateLeft(a);
        }
        if (shiftCounter < a.size())
            result = shiftCounter;
    }
    return result;
}
int main() {
    int x;
    std::vector < int > a, b;
    std::cout << "First sequence: ";
    while (std::cin >> x)
        a.push_back(x);
    std::cin.clear();
    std::cin.ignore(1000, '\n');
    std::cout << "Second sequence: ";
    while (std::cin >> x)
        b.push_back(x);
    int result = CyclicPermutation(a, b);
    if (result < 0)
        std::cout << "Second sequence is not cyclic permutaion of first.";
    else
        std::cout << "Second sequence is cyclic permutaion of first with shift " << result << ".";

    return 0;
}

    Edit:

    It works, see:

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

void rotateLeft(std::vector<int>& a) {
    if (a.size() > 0) {
        int tmp = a[0];
        for (size_t k{}; k < a.size() - 1; ++k)
            a[k] = a[k + 1];
        a.back() = tmp;
    }
}

int CyclicPermutation(std::vector<int>& a, std::vector<int>& b) {

    // Set result to invalid
    int result{ -1 };

    int shiftCounter{};
    // Only do something if the sizes are different
    if (a.size() == b.size()) {

        // Rotate until numbers are equal
        while ((a != b) and (shiftCounter++ < a.size())) {
            //std::rotate(a.begin(), a.begin() + 1, a.end());
            rotateLeft(a);
        }
        if (shiftCounter < a.size())
            result = shiftCounter;
    }
    return result;
}
int main() {
    int x;
    std::vector a{ 3, 5, 1, 2, 4, 3, 5, 7, 8, 1, 2, 5, 9, 4, 7 };
    std::vector b{ 5, 7, 8, 1, 2, 5, 9, 4, 7, 3, 5, 1, 2, 4, 3 };

    int result = CyclicPermutation(a, b);
    if (result < 0)
        std::cout << "Second sequence is not cyclic permutaion of first.";
    else
        std::cout << "Second sequence is cyclic permutaion of first with shift " << result << ".";

    return 0;
}

    enter image description here

    You input routine is not good that. You should know, that ignore is a unformatted input function

    Edit 2

    Your input works, with the original function:

    enter image description here