C++で指定された数字の最小順列を求める方法

この記事では、大きな整数 N が与えられたときに、その数字を並べ替えて作れる最小の数（最小順列）を求めるアルゴリズムを解説します。

問題の概要

与えられた数値の各桁を自由に入れ替え、その中で最も小さい数値を作ることが目的です。ただし、先頭にゼロが来てしまうと桁数が変わってしまうため、その点への対処が必要になります。

具体例で理解しよう

まず、例を使って問題を確認しましょう。

入力

N = 4529016

出力

1024569

入力された「4529016」の各桁を並べ替えると、「1024569」が最小の数となります。

解法アプローチ

この問題に対するシンプルかつ効果的な解決策は、以下の手順で行います。

1. 大きな整数値を文字列として扱う
2. 文字列全体を昇順にソートする
3. 先頭に「0」が連続している場合は、最初の非ゼロの数字と入れ替える

数値を最小化するには、小さい数字ほど上位の桁に置くのが基本ですが、先頭が「0」になってしまうと意味がありません。そこで、ソート後に先頭のゼロを、最初に出現する非ゼロの数字とスワップすることで、正しい最小値を得られます。

実装プログラム

上記のアプローチを実装したC++のコードは以下の通りです。

#include <bits/stdc++.h>
using namespace std;
string smallestNumPer(string s) {
    int len = s.length();
    sort(s.begin(), s.end());
    int i = 0;
    while (s[i] == '0')
        i++;
    swap(s[0], s[i]);
    return s;
}
int main() {
    string s = "4529016";
    cout<<"The number is "<<s<<endl;
    cout<<"The smallest permutation of the number is "<<smallestNumPer(s);
    return 0;
}

出力結果

The number is 4529016
The smallest permutation of the number is 1024569

計算量について

• 時間計算量： O(n log n) — 文字列のソートに要する時間が支配的です
• 空間計算量： O(1) — 入力文字列以外に追加のメモリはほぼ不要です

まとめ

数値を文字列としてソートし、先頭のゼロだけを適切に処理するだけで、大きな数でも簡単に最小順列を求められます。桁数の多い数値を扱う際にも有効なテクニックなので、ぜひ覚えておきましょう。