記事の概要
自分の勉強兼メモでまとめている記事シリーズです。第七弾。
今までの記事はこちら。
| # | 記事 |
|---|---|
| 6 | javaでアルゴリズム入門 - しゃくとり法 |
| 5 | javaでアルゴリズム入門 - 累積和 |
| 4 | javaでアルゴリズム入門 - 探索編（bit全探索） |
| 3 | javaでアルゴリズム入門 - 探索編（幅優先探索） |
| 2 | javaでアルゴリズム入門 - 探索編（深さ優先探索） |
| 1 | javaでアルゴリズム入門 - 探索編（全探索、二分探索） |
今回の記事では
- 辞書式順序・組み合わせなど
について勉強します。辞書式順序・組み合わせは良く出てくるのでこの機会にマスターしておきましょう。順列全探索とか呼ばれることもあるみたいです。
数学的な辞書式順序だったり、permutationとか、combinationの説明は面倒臭いもう理解できているので、省いていきましょう.
今回は問題を解きながらいろいろ考えていきますよ〜〜。
過去問を探してそれっぽい問題を雑に解いていきますね。
例題
例：AtCoder - abc150-c「Count Order」
問題文・入力例などはここをクリックして表示
※できるだけ問題リンクを参照してください
（セクション開始）
【問題文】
大きさ N の順列 ((1, 2, ..., N) を並び替えてできる数列) P, Q があります。
大きさ N の順列は N! 通り考えられます。このうち、P が辞書順で a 番目に小さく、Q が辞書順で b 番目に小さいとして、|a−b| を求めてください。
【注記】
2 つの数列 X, Y について、ある整数 k が存在して Xi=Yi (1≤i<k) かつ Xk<Yk が成り立つとき、X は Y より辞書順で小さいと定義されます。
【制約】
- 2≤N≤8
- P, Q は大きさ N の順列である。
- 入力は全て整数である。
【入力】
入力は以下の形式で標準入力から与えられる。
N
P1 P2 ... PN
Q1 Q2 ... QN
【出力】
|a−b| を出力せよ。
（セクション終了）
こんな問題がありました。the・辞書式順序といった問題ですね。
C問題で、制約もそんな多くないので単純にいけばそんなちゃんと考えなくても解けそうなきもしますが、ちょっとちゃんと考えてみましょうね。
入力例・出力例を一つみてみましょう。
＜入力例＞
3
1 3 2
3 1 2
＜出力例＞
3
解説みたいなものを読むと、
大きさ 3 の順列は、(1, 2, 3)、(1, 3, 2)、(2, 1, 3)、(2, 3, 1)、(3, 1, 2)、(3, 2, 1) の 6 個あります。このうち (1, 3, 2) は辞書順で 2 番目、(3, 1, 2) は辞書順で 5 番目なので、答えは |2−5|=3 です。
と書いてありました。順列の中での大きさ（何番目か）が求められれば良さそうですね。
c++言語とかだと、next_permutationみたいな関数があるんですが、javaだと順列の次の要素みたいな物はないので、ちょっと実装に迷うやつですかね。こういう時は迷わず答えを参照しようと思います。解説と他の人の回答例を参考にしてきますので少々お待ちを。。
・・・くそむずい。。。
C++勢はみんなnext_permutationでやってるみたい。ちなみにDFSでも順列の列挙はできそうなのでDFSの勉強がてらに一回やってみてもいいなぁと思いました。
なんとか見つけたのがこちらのリンク。リンク先に貼られているリンクが元々のもののようですが、javaで順列の要素をすべてlistに入れる処理をしてくれているようですね。これを用いさせていただきましょう。
public static void permutation(String q, String ans){
// Base Case
if(q.length() <= 1) {
System.out.println(ans + q);
}
// General Case
else {
for (int i = 0; i < q.length(); i++) {
permutation(q.substring(0, i) + q.substring(i + 1),
ans + q.charAt(i));
}
}
}
ちょびっとわかりづらいかも知れませんが、順列の最初の文字列を入れると、その文字列の辞書式順序順に、出力してくれるようです。
permutation("abc","");
を実行すると、
abc
acb
bac
bca
cab
cba
と、表示してくれました。すごいですね。これを使ってこの問題を解こうと思います。
【回答例】
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Scanner;
public class Main {
static ArrayList<String> list;
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
// 文字数
int n = sc.nextInt();
// 順列のリストを格納する変数
list = new ArrayList<>();
// p,qの入力受け取り
String p = "";
String q = "";
String[] p_sort = new String[n]; // 順列の最初の要素を格納したい
for (int i = 0; i < n; i++) {
String tmp = sc.next();
p += tmp;
p_sort[i] = tmp;
}
for (int i = 0; i < n; i++) {
q += sc.next();
}
Arrays.parallelSort(p_sort); // p_sortを順列の最初の要素にした
String p_sort_str = "";
for (String p_sort_tmp : p_sort) {
p_sort_str += p_sort_tmp;
}
// listに値を詰めていく
permutation(p_sort_str, "");
// indexの絶対値を出力
System.out.println(Math.abs(list.indexOf(q) - list.indexOf(p)));
}
public static void permutation(String q, String ans) {
// Base Case
if (q.length() <= 1) {
list.add(ans + q);
}
// General Case
else {
for (int i = 0; i < q.length(); i++) {
permutation(q.substring(0, i) + q.substring(i + 1),
ans + q.charAt(i));
}
}
}
}
割とシンプルに書けましたかね。
こんなふうに順列が計算できるのはすごいですね。
応用もできそうなので、これを使って他の問題もたくさん解いていきましょう。
c++やpythonとかだとそういうクラスとか、ライブラリみたいのがあっていいですね。。
他の問題も解いてみたいのでこの記事はpart1ということで、他の辞書式順序、組み合わせの問題も解いていきましょう。
では、また今度！