C++で最初のN個の数値の順列をソートするためのプレフィックス反転の最小数

説明

最初のN個の数の順列を持つN個の数の配列が与えられます。 1回の操作で、任意のプレフィックスを逆にすることができます。タスクは、配列内の番号が昇順で並べ替えられるように、そのような操作の最小数を見つけることです。

例

配列が{1、2、4、3}の場合、配列を昇順で並べ替えるには、最低3つの手順が必要です-

• 配列全体を逆にする{3、4、2、1}
• 最初の2つの要素を逆にします{4、3、2、1}
• 配列全体を反転する{1、2、3、4}

アルゴリズム

• 指定された数値を文字列にエンコードします。配列を並べ替えて、文字列の宛先にエンコードします。
• 次に、最初の順列からBFSを実行します。毎回、現在の順列の接頭辞を逆にすることによって引き起こされるすべての順列を確認してください。
• 訪問されていない場合は、取り消しのカウントが行われた状態でキューに入れます。
• エンコードされた文字列の順列が宛先文字列と同じである場合、ここに到達するために必要な反転の数を返します
• つまり、文字列のすべての順列が実行され、それらの最小値が回答として返されます。

例

#include <iostream>
#include <algorithm>
#include <queue>
using namespace std;
int minimumPrefixReversals(int *a, int n) {
   string start = "";
   string destination = "", t, r;
   for (int i = 0; i < n; i++) {
      start += to_string(a[i]);
   }
   sort(a, a + n);
   for (int i = 0; i < n; i++) { destination += to_string(a[i]);
}
queue<pair<string, int> > qu;
pair<string, int> p;
qu.push(make_pair(start, 0));
   if (start == destination) {
      return 0;
   }
   while (!qu.empty()) {
      p = qu.front();
      t = p.first;
      qu.pop();
      for (int j = 2; j <= n; j++) {
         r = t;
         reverse(r.begin(), r.begin() + j);
         if (r == destination) {
            return p.second + 1;
         }
         qu.push(make_pair(r, p.second + 1));
      }
   }
}
int main() {
   int a[] = { 1, 2, 4, 3 };
   int n = sizeof(a) / sizeof(a[0]);
   cout << "Minimum reversal: " << minimumPrefixReversals(a, n) << endl;
   return 0;
}

出力

上記のプログラムをコンパイルして実行する場合。次の出力を生成します-

Minimum reversal: 3