Javaでnext_permutationメソッドを作ってみる

next_permutation は c++ の関数で、与えられた順列の次の順列を戻します（1234 → 1243）。

AtCoder のある問題を解くにあたってこの関数が必要になったので、Java には用意されてないのかな～と探してみましたが、私が探してみた限りでは存在していませんでした。他の方が書いたものをお借りしてもよかったのですが、ここは一つ、勉強のために、自分で自分好みのものを作ってみることにしました。

今回作成する Java のメソッド nextPermutation は以下のように動作させます。

・文字列を引数として受け取る。
・次の順列を生成する。
・生成した順列を戻り値として返す。もし次の順列が見つからない（引数の順列が辞書順で最も大きい順列）の場合は、"Final" を戻り値として返す。

ではさっそく作っていきましょう。今回の記事を作成するにあたっては、以下のサイトを参考にさせていただきました。

qiita.com

メソッドの外枠を作ります。競プロで使っているコードに埋め込む予定なので、static にしておきます。また、1文字ずつ大小を比較する必要があるので、ArrayList にあらかじめ変換しておきます。List を使う理由は後述。

static String nextPermutation (String s) {
		
	ArrayList<Character> list = new ArrayList<>();
	for (int i=0; i<s.length(); i++) list.add(s.charAt(i));
		
}

後方から見ていったときに昇順が終わる地点の値（pivot）を求めます。
2文字ずつ比較していって、初めて c(i) < c(i+1) となるような c を発見した地点が pivot です。

int pivotPos = -1;
char pivot = 0;
		
for (int i=list.size()-2; i>=0; i--) {
	if (list.get(i) < list.get(i+1)) {
		pivotPos = i;
		pivot = list.get(i);
		break;
	}
}

もし pivot が見つからないなら、引数の順列は辞書順で最も大きい順列です。
したがって、"Final" を返します。

if (pivotPos==-1 && pivot==0) return "Final";

pivot が求まれば、その後方の区間である suffix も求まります。
suffix 内にある、pivot より大きい最小の値を求めます。

int L = pivotPos+1, R = list.size()-1;

int minPos = -1;
char min = Character.MAX_VALUE;

for (int i=R; i>=L; i--) {
	if (pivot < list.get(i)) {
		if (list.get(i) < min) {
			min = list.get(i);
			minPos = i;
		}
	}
}

pivot と min を交換し、その後、suffix を昇順にソートします。
一部分をソートするのが配列だと面倒くさそうだったので、今回は List を使いました。

Collections.swap(list, pivotPos, minPos);
Collections.sort(list.subList(L, R+1));

最後に、List を文字列にしてから返します。

StringBuilder sb = new StringBuilder();
for (int i=0; i<list.size(); i++) sb.append(list.get(i));
		
return sb.toString();

これにて処理は終了です。では実際に動かしてみましょう。

System.out.println(nextPermutation("abcde"));
// 出力：abced
		
System.out.println(nextPermutation("110011"));
// 出力：110101
		
System.out.println(nextPermutation("9876"));
// 出力：Final

うまく動作しているみたいでよかったです。

また、このメソッドを辞書順最小の文字列に対して再帰的に適応することで、いわゆる「順列の全列挙」が可能になります。

String s = "ABC";
		
while (true) {
	System.out.println(s);
	s = nextPermutation(s);
	if (s.equals("Final")) break;
}

ABC
ACB
BAC
BCA
CAB
CBA

いや～、欲しかったんですよ、この機能。以前は、順列を全て手動で書き出してましたからね。

最後に、今回作成した nextPermutation メソッドの全体を公開したいと思います。
競プロの問題を解く手助けになれば幸いです。

static String nextPermutation (String s) {

	ArrayList<Character> list = new ArrayList<>();
	for (int i=0; i<s.length(); i++) list.add(s.charAt(i));

	int pivotPos = -1;
	char pivot = 0;
	for (int i=list.size()-2; i>=0; i--) {
		if (list.get(i) < list.get(i+1)) {
			pivotPos = i;
			pivot = list.get(i);
			break;
		}
	}

	if (pivotPos==-1 && pivot==0) return "Final";

	int L = pivotPos+1, R = list.size()-1;
	int minPos = -1;
	char min = Character.MAX_VALUE;
	for (int i=R; i>=L; i--) {
		if (pivot < list.get(i)) {
			if (list.get(i) < min) {
				min = list.get(i);
				minPos = i;
			}
		}
	}

	Collections.swap(list, pivotPos, minPos);
	Collections.sort(list.subList(L, R+1));

	StringBuilder sb = new StringBuilder();
	for (int i=0; i<list.size(); i++) sb.append(list.get(i));

	return sb.toString();

}