Minimizing Permutations

 Minimizing Permutations

In this problem, you are given an integer N, and a permutation, P of the integers from 1 to N, denoted as (a_1, a_2, ..., a_N). You want to rearrange the elements of the permutation into increasing order, repeatedly making the following operation:

Select a sub-portion of the permutation, (a_i, ..., a_j), and reverse its order.

Your goal is to compute the minimum number of such operations required to return the permutation to increasing order.

Signature int minOperations(int[] arr)

Input Array arr is a permutation of all integers from 1 to N, N is between 1 and 8

Output An integer denoting the minimum number of operations required to arrange the permutation in increasing order

Example

If N = 3, and P = (3, 1, 2), we can do the following operations:

1. Select (1, 2) and reverse it: P = (3, 2, 1).
2. Select (3, 2, 1) and reverse it: P = (1, 2, 3).

output = 2

#include <bits/stdc++.h>
// Add any extra import statements you may need here
using namespace std;

vector<string> GetAllNeighbors(string str) {
  vector<string> output;
  for (int i = 0; i < str.size(); i++) {
    for (int j = 2; j <= str.size() - i; j++) {
       string tmp = str;
       reverse(tmp.begin() + i, tmp.begin() + i + j);
       output.push_back(tmp);
    }
  }
  return output;
}
// Add any helper functions you may need here
int bfs(string source, string dest) {
  queue<pair<string, int>> q;
  unordered_set<string> visited;
  q.push({source, 0});
  visited.insert(source);
  
  while (!q.empty()) {
    int size = q.size();
    for (int i = 0; i < size; i++) {
      pair<string, int> node = q.front(); q.pop();
      if (node.first == dest) {
        return node.second;
      }
      for (auto neighbor : GetAllNeighbors(node.first)) {
        // Better to check here about destination before putting it into queue.
        if (visited.count(neighbor) == 0) {
          visited.insert(neighbor);
          q.push({neighbor, node.second + 1});
        }
      }
    }
  }
  return -1;
  
}
int minOperations(vector <int> arr) {
  // Write your code here
  if (arr.size() == 0) {
    return 0;
  }
  vector<int> dest(arr.begin(), arr.end());
  sort(dest.begin(), dest.end());
  
  string dest_str;
  for (auto num : dest) {
    dest_str += to_string(num);
  }
  
  string start_str;
  for (auto num : arr) {
    start_str += to_string(num);
  }
  
  return bfs(start_str, dest_str);
}


// These are the tests we use to determine if the solution is correct.
// You can add your own at the bottom, but they are otherwise not editable!
void printInteger(int n) {
  cout << "[" << n << "]";
}
int test_case_number = 1;
void check(int expected, int output) {
  bool result = (expected == output);
  const char* rightTick = u8"\u2713";
  const char* wrongTick = u8"\u2717";
  if (result) {
    cout << rightTick << "Test #" << test_case_number << "\n";
  }
  else {
    cout << wrongTick << "Test #" << test_case_number << ": Expected ";
    printInteger(expected); 
    cout << " Your output: ";
    printInteger(output);
    cout << endl; 
  }
  test_case_number++;
}
int main() {
  int n_1 = 5;
  vector <int> arr_1{1, 2, 5, 4, 3};
  int expected_1 = 1;
  int output_1 = minOperations(arr_1);
  check(expected_1, output_1);
  int n_2 = 3;
  vector <int> arr_2{3, 1, 2};
  int expected_2 = 2;
  int output_2 = minOperations(arr_2);
  check(expected_2, output_2);
  // Add your own test cases here
  
}

In this problem, you are given an integer N, and a permutation, P of the integers from 1 to N, denoted as (a_1, a_2, ..., a_N). You want to rearrange the elements of the permutation into increasing order, repeatedly making the following operation:

Select a sub-portion of the permutation, (a_i, ..., a_j), and reverse its order.

Your goal is to compute the minimum number of such operations required to return the permutation to increasing order.

Signature int minOperations(int[] arr)

Input Array arr is a permutation of all integers from 1 to N, N is between 1 and 8

Output An integer denoting the minimum number of operations required to arrange the permutation in increasing order

Example

If N = 3, and P = (3, 1, 2), we can do the following operations:

1. Select (1, 2) and reverse it: P = (3, 2, 1).
2. Select (3, 2, 1) and reverse it: P = (1, 2, 3).

output = 2