Найти сдвиг циклической перестановки двух последовательностей

Мне нужно найти сдвиг двух циклических перестановок последовательностей.

ПРИМЕР:

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

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

Вторая последовательность является циклической перестановкой первой со сдвигом 6.

Мой алгоритм:

  • если последовательности равны вернуть 0 как сдвиг
  • если они не равны, отсортируйте их, а затем проверьте, имеют ли они одинаковые элементы
  • если они не имеют одинаковых элементов, они не являются циклической перестановкой
  • если они имеют одинаковые элементы, первый элемент первого вектора перемещается в конец вектора, а затем создает временный вектор из первых двух элементов первого вектора, находит этот временный вектор во втором векторе, а сдвиг равен 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;
}

Не могли бы вы объяснить мне, где я допустил ошибку в своем алгоритме и коде? Как изменить это, чтобы работать правильно?

Что вы заметили, проходя код за строкой с помощью отладчика? Такие вещи, как help.push_back(b.at(i + 1));, скорее всего, вызовут такие исключения.

πάντα ῥεῖ 09.04.2022 12:57

для последовательностей (1,2) и (2,1) он не дает исключения, он печатает просто неправильный результат

Rocket Procd 09.04.2022 14:30
Формы c голосовым вводом в React с помощью Speechly
Формы c голосовым вводом в React с помощью Speechly
Пытались ли вы когда-нибудь заполнить веб-форму в области электронной коммерции, которая требует много кликов и выбора? Вас попросят заполнить дату,...
Стилизация и валидация html-формы без использования JavaScript (только HTML/CSS)
Стилизация и валидация html-формы без использования JavaScript (только HTML/CSS)
Будучи разработчиком веб-приложений, легко впасть в заблуждение, считая, что приложение без JavaScript не имеет права на жизнь. Нам становится удобно...
Flatpickr: простой модуль календаря для вашего приложения на React
Flatpickr: простой модуль календаря для вашего приложения на React
Если вы ищете пакет для быстрой интеграции календаря с выбором даты в ваше приложения, то библиотека Flatpickr отлично справится с этой задачей....
В чем разница между Promise и Observable?
В чем разница между Promise и Observable?
Разберитесь в этом вопросе, и вы значительно повысите уровень своей компетенции.
Что такое cURL в PHP? Встроенные функции и пример GET запроса
Что такое cURL в PHP? Встроенные функции и пример GET запроса
Клиент для URL-адресов, cURL, позволяет взаимодействовать с множеством различных серверов по множеству различных протоколов с синтаксисом URL.
Четыре эффективных способа центрирования блочных элементов в CSS
Четыре эффективных способа центрирования блочных элементов в CSS
У каждого из нас бывали случаи, когда нам нужно отцентрировать блочный элемент, но мы не знаем, как это сделать. Даже если мы реализуем какой-то...
0
2
33
1
Перейти к ответу Данный вопрос помечен как решенный

Ответы 1

Ответ принят как подходящий

Ваш дизайн неправильный.

Кажется, вы просто хотите повернуть элементы в std::vector.

Исключением является ошибка выхода за пределы: help.push_back(b.at(i + 1));

Странная обработка с "help" и "temp". Сначала вы создаете «help» и «temp» с n 0es в нем. Затем вы отталкиваете вещи, но только 2 элемента. Итак, если, например, исходный размер вектора равен 4, то ваши векторы будут 0,0,0,0,x,y.

Это довольно странно, или я этого не понимаю.

Что ты должен делать:

  1. Проверьте, равен ли размер двух векторов
  2. Проверьте, равны ли векторы, используя существующий оператор ==
  3. Поверните элементы векторов на mx "размер" раз. Подсчитайте количество оборотов
  4. Вернуться к 2

Вы можете либо использовать существующую функцию std::rotate(см. здесь), либо написать простую функцию самостоятельно.

Вы можете изменить свою функцию следующим образом:

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

enter image description here

Вы вводите рутину не хорошо, что. Вы должны знать, что ignore — это функция неформатированного ввода.


Редактировать 2

Ваш ввод работает с исходной функцией:

enter image description here


например, он возвращает сдвиг как равный 0, что неверно

Rocket Procd 09.04.2022 15:00

Это работает, пожалуйста, смотрите мое редактирование.

Armin Montigny 09.04.2022 15:57

программа должна вводить элементы вектора до тех пор, пока не будет введено что-то, что не является числом, например first: 1 2 1 2 . введите second: 2 1 2 1 abcde не могли бы вы включить это в своем коде?

Rocket Procd 09.04.2022 16:06

Ваш исходный код также работает с данным вводом. Можете ли вы сказать мне, с какой проблемой вы столкнулись?

Armin Montigny 09.04.2022 16:28

Я не использовал result = CyclicPermutation(a, b);, и из-за этого я получил 0 как сдвиг в (1,2,1,2), (2,1,2,1)... большое спасибо... это сработало...

Rocket Procd 09.04.2022 17:04

просто правильное объявление вектора, оно должно быть std::vector<int>a{.....}

Rocket Procd 09.04.2022 17:05

Я использую С++17. Здесь у нас есть CTAD. Затем вы можете опустить <int>

Armin Montigny 09.04.2022 17:07

извините, я не знал, мы используем C++14

Rocket Procd 09.04.2022 17:08

Другие вопросы по теме