找到两个序列的循环置换的移位

Question

我需要找到序列的两个循环排列的移位。

示例：

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

第二个序列是第一个序列的循环置换 6.

我的算法：

如果序列相等return 0 as shift
如果它们不相等，则对它们进行排序，然后检查它们是否具有相同的元素
如果它们没有相同的元素，则它们不是循环排列
如果它们有相同的元素，则第一个向量的第一个元素移动到向量的末尾，然后将第一个向量的前两个元素作为临时向量，找到第二个向量中的临时向量并移位等于b.size() - i + 1;

例如我得到以下错误

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)

如果我尝试其他序列结果不正确。

#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;
}

你能解释一下我的算法和代码哪里出错了吗？如何修改它才能正常工作？

Answer 1

你的设计有误。

您似乎只想旋转 std::vector.

中的元素

异常是因为越界错误：help.push_back(b.at(i + 1));

对“help”和“temp”的处理很奇怪。您首先创建“help”和“temp”，其中包含 n 个 0。然后你推回东西，但只有 2 个元素。因此，例如，如果原始矢量大小为 4，那么您的矢量将为 0,0,0,0,x,y。

这个比较奇怪，或者，我没看懂。

你应该做什么：

检查两个向量的大小是否相等
使用现有的 == 运算符检查向量是否相等
将矢量元素旋转 mx "size" 次。数一数转数
返回 2

您可以使用现有的函数std::rotate（参见here）或自己编写一个简单的函数。

您可以这样修改函数：

#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;
}

编辑：

有效，请参阅：

#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;
}

你输入套路不好那个。你应该知道，ignore 是一个未格式化的输入函数

编辑 2

您的输入有效，具有原始功能：

找到两个序列的循环置换的移位

Find shift of cyclic permutation of two sequences

c++

stdvector