Javaで重複順列を列挙してみる
こんにちは。mp_hskです。
今日は、なんか転職活動中のコーディングテストでやたらと出題された
重複順列を列挙する問題をJavaで解いてみます。
問題
A,B,C,D,E の5文字から重複を許可した３文字の文字列をすべて列挙する。
例： AAA, AAB, AAC ......
考え方
重複順列の表示の考え方は基本的に、表示桁数のｎ(文字種類)進数を0から順に作って
それぞれの各数値と文字を当てはめて変換すればできる。
今回の問題にあてはめると
- ０ ～ 5の3乗（全パターン数）までの各数値を５進数に変換する
- 0 = A, 1 = B, 2 = C, 3 = D, 4 = E に当てはめて数値を文字に変換する
- 変換した文字列を表示する
でできるはず。
組んでみたコード
こんな感じで組んでみた。(ライブラリをあまり使わず組んでみました)
public class Zyunnretu {
// メイン関数
public static void main(String[] args) {Map<String, String> convertMap = new HashMap<String, String>();
convertMap.put("0", "A");
convertMap.put("1", "B");
convertMap.put("2", "C");
convertMap.put("3", "D");
convertMap.put("4", "E");for(int i = 0; i < Math.pow(5, 3);i++){
String tmp = leftPaddingZero(convert(i,5),3);
StringBuilder sb = new StringBuilder();
for(int j = 0;j < tmp.length();j++){
sb.append(convertMap.get(tmp.substring(j, j+1)));
}
System.out.println(sb.toString());
}
}/**
* targetをn進数の文字列に変換して返す
*/
private static String convert(int target, int n) {
StringBuilder sb = new StringBuilder();
int tmp = target;
while (tmp > 0) {
sb.append(tmp % n);
tmp = (tmp - (tmp % n)) / n;
}
return sb.reverse().toString();
}/**
* Strを左ゼロ埋めする
*/
private static String leftPaddingZero(String str, int length) {
if (str.length() == length) {
return str;
} else {
return leftPaddingZero("0" + str, length);
}
}
}
解説
mainではこんな感じ
- 変換表をMap型で生成
- ループで 0から 5の3乗までを、3桁の５進数(足りない部分は0埋め)に変換する処理を呼び出し
- 取得した5進数を頭から１文字ずつ変換表で変換
n進数変換（convert）ではこんな感じ
- 渡された数値を nで割ったあまりを文字列に足す
- 渡された数値をnで割った商を計算する
- 渡された数値をnで割った商が 0より大きい間上の処理を繰り返す
- 最後に足した文字列を反転して返す
ちょっとわかりずらいけど、たとえば152なら
- 102 ÷ 5 = 20 あまり 2 文字列に2を足す "2"
- 20 ÷ 5 = 4 あまり 0 文字列に0を足す "20"
- 4 ÷ 5 = 0 あまり 4 文字列に4を足す "204"
- 反転する "402"
- 対応表に当てはめる "EAC"
こんな感じの処理を 0 - 125までやれば列挙できっるて寸法です。
応用
これを使った問題でこんなのが出た
・コインを5回投げて2回連続で表がでるパターンを列挙
この問題は上記プログラムにおいてまず
- 文字 H, R (表、裏) で5文字の重複する順列を作る
- その中で、パターン "HH" （２回表）にマッチする文字列だけ表示する
で対応できた。
ほかにも重複を許す樹形図系の問題では威力を発揮するかもしれない。
参考リンク
説明はこれがわかりやすい
重複順列を辞書式順列で求めるアルゴリズムはどういったもの... - Yahoo!知恵袋
進数変換部分は今回は自分でプログラミングしたが、baseエンコードでできそう
ツッコミあればお待ちしてます