ストレイテナーと確率１０続々（トリビュート12曲12アーティスト全組み合わせをつくろう）
「ストレイテナーと確率１０」の関連。
正確に言うと本項は「確率」についてはほとんど語らないが、
関連する話題としてタイトルを付けさせていただいた。
12の曲に12のアーティストが参加するという、ストレイテナートリビュートアルバム「ＰＡＵＳＥ」。
このとき、どの曲をどのアーティストが担当するかという、
その組み合わせの総パターン数は12!＝479001600である。
”この「4億7千9百万とんで1600」のパターンを全て用意できないか？”というのに
少し挑戦してみたくなったので、その挑戦の記録である。
可能であれば4億7千9百万とんで1600の全パターンを、全てファイルにでも出力したいところだが、
仮に1行1バイト（有り得ないが）・改行コードLF（1バイト）だとしても、
479001600×2＝958003200≒0.892[GByte]ほどの容量にもなり
フラットテキストファイルとして扱うには少し現実的ではない。
この時点で残念ながらファイル出力は諦めざるを得まい。
興味本位で計算してみたが、トリビュート全12曲と参加アーティスト全12組について、
それぞれの文字のバイト数は以下の通りとなる。(SJIS換算)
| ■曲名 No曲名バイト数
|
■アーティスト名 Noアーティスト名バイト数
|
これを、
- 曲名とアーティスト名を"-"（半角ハイフン；1バイト）で連結
- 各組合せ間を","（半角カンマ；1バイト）で連結
- 改行コードをLF（1バイト）
というルールで1行に1つの組み合わせを出力していくことを想定した場合、
1行に要する容量は353[byte]となり、これが479001600行続く計算なので、
353×479001600＝1.69×1011≒157.48[GByte]という
とんでもなくバカでかいテキストファイルになることがわかった。
(手持ちのエロ動画全部集めたってこの容量には届かない)
ちなみに、これらの組み合わせは、フル桁である必要はなく、
先頭2文字を切り出せば（少なくともこの範囲内では）一意に特定できる。
たとえばACIDMAN→「AC」、TRAVELING GARGOYLE→「TR」等である（元素記号のようだ）
これにより上に挙げたものより大幅に容量削減できる、のだが、
結局計算上約30.78[Gbyte]ほどは容量を必要とするため、
やはりフラットなテキストファイルに出力することを前提とするのは無理がありそうである。。。（無念）
確率議論をしたときには深堀しなかったが、
単一の配列を並び替えるときと異なり、
このケースは「12の曲」と「12のアーティスト」という
2つの配列を組み合わせて並び替える考慮が必要だ。
n個の要素をもつ単一の配列を並び替えるパターンは全部でn!だが、
2つの配列だった場合にはどうなるのか？単純にn!2とか？
と、最初は考えていた。
（まあ結局、こと今回に関して言えば答えはn!でよかったんだが）
こういうのは小さい母数でシミュレーションしてみるとわかりやすのだが
たとえば「A」「B」「C」という3つの曲と「1」「2」「3」という3組のアーティストが
今回と同じようにそれぞれ担当する曲を決めてトリビュートすると仮定すると、
[A-1][B-2][C-3]、[A-1][B-3][C-2]、[A-2][B-1][C-3]、
[A-2][B-3][C-1]、[A-3][B-1][C-2]、[A-3][B-2][C-1]
の6通りになる。
これは母数3に対して3!と同値である。
冷静になって考えてみれば、
「A」「B」「C」という曲に付くアーティストを並び替えているだけであり、
「A」「B」「C」という曲の位置は固定化して考えてもよい。
このため「曲」「アーティスト」というように配列要素は2つあるものの、
考えるべきパターン数はそのどちらかの総パターン数に過ぎない、
というのが、今回のケースの考え方である。
（固定化するのは「曲」「アーティスト」どっちでもいい）
ただこれは「順番」という観点を無視しており、
もし仮に「曲順（トリビュートアルバムの収録順）」まで含めて考えなくてはならない場合、
この考え方では足りなくなってくる。
というのも、この考え方では、
[A-1][B-2][C-3]、[B-2][A-1][C-3]
という組み合わせは”同じもの”として捉えるようにしているからだ。
どの曲を誰が担当するかだけが重要なのであって、
その担当する組み合わせが順番でどこに位置するかまで議論していないのである。
もし順番まで考慮するとなると「曲」「アーティスト」
それぞれの並び替えパターン数の直積分（つまり二乗）のパターン数が必要になるため、
このケースにおいても3!2＝36通りも必要になる。
実際のケース（12曲12アーティスト）で同じことを当てはめると、4億7千万の二乗なので、
なんかもう計算するのも途方にくれるぐらい馬鹿でかい数字になる。
まだクイズに参加してないのでなんともいえないが
おそらく「組み合わせ」だけを問うているはずなので
この考え方は不要（だと信じている）のである。
ためしにこの組み合わせを総当りで求めるプログラムを作ってみることにしよう。
上で述べたとおり、「曲」か「アーティスト」かどっちかを総当りするようにして、
並び替えなかったほうの配列と同一要素位置同士を連結して組み合わせにすればいい。
上の簡単な例（A、B、C、1、2、3）でいけば、ABCを固定化して
123→132→213→231→312→321
と、小さいほうから順に辿っていってくれればそれでいい。
これは要するに
String[] artists = new String[3]{"","",""};
for (int i=1; i <= 3; i++) {
artists[0] = String.vallueOf(i);
for (int j=1; j <= 3; j++) {
if (isAvailable(j,1,artists)) {
artists[1] = String.vallueOf(j);
} else {
continue;
}
for (int k=1; k <= 3; k++) {
if (isAvailable(k,2,artists)) {
artists[2] = String.vallueOf(k); //←ここで「そろった」
} else {
continue;
}
}
}
}
boolean isAvailable(int num,int idx,String[] array) {
String numStr = String.valueOf(num);
for (int i=0; i < idx; i++) {
if !array[i].equals(numStr)) {
return false;
}
}
return true;
}
という感じの実装で実現ができる。
「isAvailable」ってのが少し邪魔だが要するに
for (int i=1; i <= 3; i++) {
…
for (int j=1; j <= 3; j++) {
…
for (int k=1; k <= 3; k++) {
…
}
}
}
と、forを3回書いているだけなのである。
→このとき、「今決めようとしている位置の要素より手前で、これから使おうとしている値が使われていたら」
という判定をしないと、
[A-1][B-1][C-1]みたいな組み合わせ（別の曲に同じアーティストが付く）ができてしまう。
1曲1アーティストが担当する前提ならば、「すでにそのアーティストは何かの曲を担当しているか」という
判定を入れなくてはならない。
isAvailableはそのための簡易メソッドである。
同様のことは例え母数が12になろうが可能だが、
for (int i=1; i <= 12; i++) {
…
for (int j=1; j <= 12; j++) {
…
for (int k=1; k <= 12; k++) {
…
for (int l=1; l <= 12; l++) {
…
for (int m=1; m <= 12; m++) {
…
for (int n=1; n <= 12; n++) {
…
for (int o=1; o <= 12; o++) {
…
for (int p=1; p <= 12; p++) {
…
for (int q=1; q <= 12; q++) {
…
for (int r=1; r <= 12; r++) {
…
for (int s=1; s <= 12; s++) {
…
for (int t=1; t <= 12; t++) {
…
}
}
}
}
}
}
}
}
}
}
}
}
という実装になる。
確かにこれでもできるのだがforのネストが深すぎて実装としてはイマイチだ。
そしてどうでもいいがforの言い過ぎで昔流行ったハードゲ○氏を思い出してしまう。
なので、多少なりともスマートにやるため、再帰によるプログラミングを行う。
public class StraightenerTributeAllListMake {
private static long COUNT = 0L;
private static final String[] ARRAY_SONGS = new String[] {
"Farewell Dear Deadman"
,"KILLER TUNE"
,"Melodic Storm"
,"REMINDER"
,"ROCKSTEADY"
,"SAD AND BEAUTIFUL WORLD"
,"SENSELESS STORY TELLER SONY"
,"SIX DAY WONDER"
,"TRAVELING GARGOYLE"
,"シーグラス"
,"シンクロ"
,"冬の太陽"
};
private static final String[] ARRAY_ARTISTS = new String[] {
"ACIDMAN"
,"ASIAN KUNG-FU GENERATION"
,"9mm Parabellum Bullet"
,"go!go!vanillas"
,"THE BACK HORN"
,"the pillows"
,"SPECIAL OTHERS"
,"back number"
,"My Hair is Bad"
,"MONOEYES"
,"majiko"
,"ストレイテナー"
};
public static void main(String[] args) throws Throwable {
String[] allSongsArr = ARRAY_SONGS;
String[] allArtistsArr = ARRAY_ARTISTS;
int listLength = allSongsArr.length;
recursiveRoot(allSongsArr,allArtistsArr,listLength);
System.out.println("総パターン数＝" + COUNT);
}
private static void recursiveRoot(String[] allSongsArr,String[] allArtistsArr,int listLength) throws Throwable {
String[] currentArtistsArr = new String[listLength];
for (int i=0; i < listLength; i++) {
currentArtistsArr[i] = "";
}
recursiveExec(0,listLength,currentArtistsArr,allArtistsArr,allSongsArr);
}
private static void recursiveExec(int targetIdx,int listLength,String[] currentArtistsArr,String[] allArtistsArr,String[] allSongsArr) {
int targetIdxWk = targetIdx;
for (int n=0; n < listLength; n++) {
if (canUseValue(allArtistsArr[n],targetIdxWk,currentArtistsArr)) {
currentArtistsArr[targetIdxWk] = allArtistsArr[n];
if (targetIdxWk + 1 >= listLength) {
//揃え終わった
COUNT++; // ←①
} else {
// ↓ここで「再帰」（自分をもう一度呼び出す）
recursiveExec(targetIdxWk + 1,listLength , currentArtistsArr,allArtistsArr,allSongsArr); // ←②
currentArtistsArr[targetIdxWk] = "";
}
} else {
continue;
}
}
}
private static boolean canUseValue(String targetVal , int targetIdx , String[] targetArr) {
for (int i=0; i < targetIdx; i++) {
if (targetArr[i].equals(targetVal) && targetVal.length() > 0) {
return false;
}
}
return true;
}
}
といった感じである。
②の「recursiveExec」が再帰で、自分で自分を何度も呼び出すようになっている。
①のタイミングが「12組全部そろった」ことをあらわしており、
このとき12の曲のどれをどのアーティストが担当するかが内部的に配列で決まっている。
冒頭述べた「ファイル出力」をするならこのタイミングになる（※）のだが、
ファイル出力は容量的に無理ということがわかっているので
せめてもの救済手段として「パターン数カウント」だけ行うようにしている（赤太字のCOUNT++ってのがそれ）。
12もの総並び替えを行わせると結果が出るまでに20～30分を要したが、
結果見事479001600という値を得ることができた。
（※）4億7千万にも及ぶデータを1行ごとにファイル出力するようにしていては、
ディスクIOだけで莫大な時間のロスになることは、常識的に考えてまず間違いない。
このため、たとえば「Listに溜め込んであとで一気に出力」などの考え方をするのが、
ファイル出力を目指す場合においては処理効率がよい。
しかしファイル出力想定で157Gにも及ぶ大容量を
一時的にJavaのメモリに溜め込むほうがもっと現実的ではないので、
「ファイル出力をするならこのタイミング」と書いた。
まあスペックに依存する部分もあるだろうから一概には言えないが…
全パターンを総なめすることはできたので、
やろうと思えば全パターンをファイル出力することも可能だろう。
ファイル容量がやはりネックになるものの、
なんとかして全パターンの出力に臨みたいところだ。
ぶっちゃけ150Gくらいだったら空いてるんだけど（それでも一気に使うには重すぎるとは思うが）、
それが一つのテキストファイルになるというのが問題なのだ（作ったところで開けない）。
曲別アーティスト別とかでフォルダ分けするとか考えないと
出力できても内容を見ることはできないだろう。
その辺の仕組みを考えるのが面倒なので断念しているが、
いつかふと思い立って再開するかもしれない。
そのときまで一旦活動休止だ！
