C++で最大k回のスワップ後に得られる最大の順列

はじめに

このチュートリアルでは、配列に対して最大k回のスワップ（要素の交換）を行ったときに実現できる最大の順列を求めるプログラムを、C++で作成していきます。

この問題は貪欲法（グリーディ法）を使うことで効率的に解けます。左から順に「その位置に置くべき最大の数」を1回のスワップで移動させていく、というのが基本的な考え方です。

解き方の手順

1. 配列を初期化します。
2. 各要素のインデックスを格納するための、サイズ n + 1 の位置情報配列を用意します。
3. 配列を走査し、各要素が現在どこにあるのかを位置情報配列に記録します。
4. i が n 未満かつ k が 0 より大きい間、以下の処理を繰り返します。
   • arr[i] がすでにその位置に来るべき値「n - i」と一致していれば、スワップは不要なのでスキップします。
   • 値「n - i」が現在ある位置を一時変数 temp に保存します。
   • 現在の要素 arr[i] の位置情報を position[n - i] の値で更新します。
   • position[n - i] に現在のインデックス i を設定します。
   • arr[temp] と arr[i] をスワップします。
   • k を 1 減らします。
5. 最終的な配列の要素を出力します。

サンプルコード

それでは、実際のコードを見てみましょう。

#include <bits/stdc++.h>
using namespace std;

void getLargestPermutation(int arr[], int n, int k) {
    int position[n + 1];
    // 各要素のインデックスを記録
    for (int i = 0; i < n; ++i) {
        position[arr[i]] = i;
    }
    for (int i = 0; i < n && k; ++i) {
        // すでに最大の値が配置済みならスキップ
        if (arr[i] == n - i) {
            continue;
        }
        int temp = position[n - i];
        position[arr[i]] = position[n - i];
        position[n - i] = i;
        swap(arr[temp], arr[i]);
        --k;
    }
}

int main() {
    int arr[] = { 5, 3, 2, 6, 7, 1, 4 };
    int n = 7, k = 3;
    getLargestPermutation(arr, n, k);
    for (int i = 0; i < n; ++i) {
        cout << arr[i];
    }
    cout << endl;
    return 0;
}

実行結果

上記のコードを実行すると、次のような出力が得られます。

7653214

コードのポイント

このアルゴリズムでは、位置情報配列のおかげで「目的の値が今どこにあるか」を毎回線形探索する必要がなく、任意の要素の位置をO(1)で参照できます。そのため、全体の計算量はO(n)となり、非常に効率的です。

また、スワップは必要な場面でのみ行われるため、回数を無駄に消費しません。k回以内で必ず最大の順列に到達でき、仮にkが余っていても、配列がすでに降順に並んでいる状態ならそれ以上の改善は不可能なので、そこで処理が終了します。

まとめ

本記事では、最大k回のスワップで得られる最大の順列を求める方法を解説しました。貪欲法と位置情報配列を組み合わせることで、線形時間で解けるシンプルかつ強力なアプローチです。チュートリアルについてご不明な点があれば、コメント欄でお気軽にお知らせください。