k回のスワップで作れる最大の数を求める方法（C++実装例付き）

この問題では、正の整数を表す数字列が1つ与えられ、桁の入れ替え（スワップ）をちょうどk回行うことで、値が最大になる並び替えを求めます。

解き方の基本は、ある桁を選び、その後ろにある桁と1つずつ入れ替えながら最大値を探索することです。この操作をk回繰り返します。ここではバックトラッキング（探索の巻き戻し）が有効に機能します。前の値より大きくならない並びを見つけたときは、元の状態に戻して別の組み合わせを試すことで、取りこぼしのない探索が可能になるからです。

入力と出力

入力:
複数桁の数字列
入力例: 129814999

出力:
桁を入れ替えて得られる最大値
出力例: 999984211

アルゴリズム

maxNum(number, swaps, maxNumber)

入力 − 数字列（文字列として扱う）、スワップ回数、最大値を保持する文字列。

出力 − maxNumber を更新しながら最大値を求めます。

開始
    もし swaps = 0 なら
        return
    n := 数字列の桁数
    for i := 0 to n-2, do
        for j := i+1 to n-1, do
            もし number[i] < number[j] なら
                number[i] と number[j] を入れ替える
                もし number が maxNumber より大きければ
                    maxNumber := number
                maxNum(number, swaps-1, maxNumber) を再帰呼び出し
                バックトラックのため、再度 number[i] と number[j] を入れ替える
        done
    done
終了

実装例（C++）

#include <iostream>
using namespace std;

void maxNum(string str, int swaps, string &max) {
    if(swaps == 0)          // スワップが残っていない場合
        return;
    int n = str.length();

    for (int i = 0; i < n - 1; i++) {       // 数字列の各桁について
        for (int j = i + 1; j < n; j++) {
            if (str[i] < str[j]) {           // i番目がj番目より小さい場合
                swap(str[i], str[j]);
                if (str.compare(max) > 0)    // 現在の数が大きければ最大値を更新
                    max = str;
                maxNum(str, swaps - 1, max); // 残りのスワップへ進む
                swap(str[i], str[j]);        // 失敗したら入れ替えを元に戻す
            }
        }
    }
}

int main() {
    string str = "129814999";
    int swapNumber = 4;
    string max = str;
    maxNum(str, swapNumber, max);
    cout << "The given number is: " << str << endl;
    cout << "The maximum number is: " << max << endl;
}

実行結果

The given number is: 129814999
The maximum number is: 999984211

動作のポイント

再帰呼び出しのたびにスワップの残り回数を1ずつ減らし、残りが0になった時点で探索を打ち切ります。二重ループですべての桁のペア (i, j) を試し、入れ替えた結果が現在の最大値より大きければ max を更新します。再帰から戻った後に入れ替えを元に戻す（バックトラックする）ことで、他の組み合わせも正しく探索できます。

入力例の「129814999」は、4回のスワップで降順に並べ替えた「999984211」に到達できます。探索の組み合わせ数はスワップ回数に応じて指数的に増える可能性がありますが、桁数が少なければ十分実用的な手法です。