文字列生成を総当りで行う場合

質問

初めての質問で分かりにくいところもあるかと思いますが宜しくお願いします。

あ,い/うえ/おか,き,くけこ/さ/しす
という文字列から、

あ/うえ/おか/さ/しす
あ/うえ/き/さ/しす
あ/うえ/くけこ/さ/しす
い/うえ/おか/さ/しす
い/うえ/き/さ/しす
い/うえ/くけこ/さ/しす

このような文章を作りたいのです。
言葉で説明しにくいのですが、"/"と"/"の間にある文字列を必ず１つ使い、","があるところを総当りで文字列を生成します。
私の作ったプログラムでは、この例のように6文で済む場合なら対応できるのですが、実際に使う文章はもっと長く、"/"の区切りも多く、更に"."が10個以上あることも多いので、文が億単位で生成されることも多々あります。intで表せない(今のプログラムでは、あらかじめ何個の文ができるか計算してから文を生成しています。)場合や、文字列を格納する場所が多くなりすぎてメモリが足りなくなり、生成できません。
この文字列生成は、上記の6個ように総当りで文字列が生成できれば、どの文が最初に生成されても構いません。できれば１文出来るごとにそれを使った違う処理に移り、返ってきたらその文を捨ててまた新たな文を生成できると嬉しいです。

どうぞ宜しくお願いします。

回答No.1

Bonjin · ベストアンサー

アルゴリズムなどがわからないわけではなさそうなのでアドバイスだけ・・・

＞今のプログラムでは、あらかじめ何個の文ができるか計算してから文を生成しています。
億単位の文字列を生成してから処理するのではメモリが足りなくなるのも無理はありません。使う時に生成すればよいのです。
一応サンプルを書いてみました。

public class Parser
{
private String[][] elements = null;
private int[] index = null;

public Parser(String str){
String[] buf = str.split("/");
elements = new String[buf.length][];
for(int i = 0; i < buf.length; i++){elements[i] = buf[i].split(",");}

index = new int[buf.length];
for(int i = 0; i < index.length; i++){index[i] = 0;}
}

public boolean hasNext(){
if(index[0] >= elements[0].length){
return false;
}
return true;
}

public String next(){
StringBuffer sb = new StringBuffer();
for(int i = 0; i < index.length; i++){
sb.append(elements[i][index[i]]);
if(i < index.length - 1){sb.append("/");}
}
addIndex();
return sb.toString();
}

private void addIndex(){
index[index.length - 1]++;
for(int i = index.length - 1; i > 0; i--){
if(index[i] >= elements[i].length){
index[i] = 0;
index[i - 1]++;
}
}
}

public static void main(String[] args){
Parser p = new Parser("あ,い/うえ/おか,き,くけこ/さ/しす");

while(p.hasNext()){
// ここを任意の処理に置き換える
System.out.println(p.next());
}
}
}

このParserというクラスは文字列を生成するための情報だけ持ち、next()というメソッドを呼び出したときに文字列を生成します。
これにより無駄なメモリの消費を押さえることができます。

※文字列生成のアルゴリズムは条件を満たしてますが適当です。

お礼

素早いお返事ありがとうございます。こちらのプログラムをテストプログラムに載せて走らせましたら、希望通りの動きを得る事ができました。
今から実際の処理に使っている本プログラムに載せて走らせてみます。また何か異常が見つかったら(これが解決されることで新たな問題が浮かび上がるかも…？)宜しくお願いします。