組み合わせのパターンを作成する関数

質問

組み合わせのパターンを作成する関数を作成したいと思っています。
仕様は以下のような感じです。

引数
・list：材料となる文字の配列
・len：作成する文字列の数(2以上)

戻り値
・組合わせた文字列の配列

例
(["a", "b", "c"], 2)→["aa", "ab", "ac", "ba", "bb", "bc", "ca", "cb", "cc"]
(["a", "b"], 3)→["aaa", "aab", "aba", "abb", "baa", "bab", "bba", "bbb"]

私はとりあえず作成する総パターン数(Math.pow(list.length, len))回ループでまわし、indexをtoStrungでn進数にし(ゼロパディングし)、最後に数字と対応する文字を置換するという方法で実装しました。とりあえず動いています。

しかし他にもいろいろなアルゴリズムが考えられそうなので、他の実装・よりよい方法を知りたいと思いまして質問させていただくことにしました。

できれば具体的なコードを教えていただきたいです。
よろしくお願いします。

回答No.3

babu_baboo · ベストアンサー

ひょうじゅんとは？

var result = [];
var x = ['a', 'b', 'c'];
var len = x.length;

for (var i = 0, I = len; i < I; i++)
　for (var j = 0, J = len; j < J; j++)
　　result.push (x[i] + x[j]);

alert (result.join ('\n'));

--

var result = [];
var x = ['a', 'b'];
var len = x.length;

for (var i = 0, I = len; i < I; i++)
　for (var j = 0, J = len; j < J; j++)
　　for (var k = 0, K = len; k < K; k++)
　　　result.push (x[i] + x[j] + x[k]);

alert (result.join ('\n'));

--

if(!Array.prototype.reduce)Array.prototype.reduce=function(d){var c=this.length;if(typeof d!="function")throw new TypeError;if(c==0&&arguments.length==1)throw new TypeError;var a=0;if(arguments.length>=2)var b=arguments[1];else{do{if(a in this){b=this[a++];break}if(++a>=c)throw new TypeError;}while(1)}for(;a<c;a++)a in this&&(b=d.call(null,b,this[a],a,this));return b};

var rcombination =
　function (memo, count) {
　 return function (r, m, _, a) {
　　 return (count > 1)
　　　 ? a.reduce (rcombination (memo.concat (m), count - 1), r)
　　　 : r.concat ([ memo.concat (m) ]);
　 };
};

alert (['a', 'b', 'c'].reduce (rcombination ([ ], 2), [ ]).join("\n"));
alert (['a', 'b'].reduce (rcombination ([ ], 3), [ ]).join("\n"));

お礼

saisyonofutatsuwa hikisuugahenkasurutabini kodowokakikaenakerebanaranai
nodesuyone? tatoeba kumiawasenomojiga juudattararupumojuuni hyakudattarahyakunorupuwo kakunodesuyone. moushiwakearimasenga watashinokonomidewaarimasen.

...koremo... wakarinikukattadesu.
shikashi sankouninarimashita.
arigatougozaimashita.

回答No.13

babu_baboo

ついき2！

もうひとつみっけ！
list.length が10をこえると、おきかえがへんになる
Nshinnsuu にへんかんしないと

お礼

naruhodo. korehaookinamondaidesune...
sankouninarimashita.
goshiteki arigatougozaimashita.

回答No.12

babu_baboo

ついき
0でうめるときに tmp にくわえるのは、list[0] でそくどあっぷ。
ひごろ、ひりきなましんでうごかす「身」としては、きになる。

お礼

arigatougozaimashita.

回答No.11

babu_baboo

#Array.push を、つかっているじてんで、そくどのことをとやかくいえるものでもないのですが、るーぷのなかにせいきひょうげんでおきかえですか？
list のなかにすうじがあったらそれがおきかえされてしまいませんか？(ためしていませんが)

お礼

watashino tousyonosouteideha mondainakattanodesuga
hannyouseiwo kouryosurutodamedesune.
arigatougozaimashita.

回答No.10

babu_baboo

しつもんしゃのあるごりずむをさんこうにしてかいてみる。こんなかんじ？

function RepeatedCombination (ary, n) {
　var len = ary.length;
　var max = Math.pow (len, n);
　var index = 0;
　var i;
　var j, J;
　var result = [];
　var zero = Array (n).join ('0');
　var hash = {};
　var str;
　var chs;

　if (36 < len)
　　throw new Error;

　for (i = 0; i < len; i++)
　　hash[i.toString (len)] = ary[i];

　for (i = 0; i < max; i++) {
　　chs = (zero + i.toString (len)).slice (-n).split ('');
　　for (j = 0, str = []; J = chs[j++]; )
　　　str.push (hash[J]);
　　result.push (str.join (''));
　}

　return result;
}

var result = RepeatedCombination (['a', 'b', 'c'], 2);
alert (result.join ('\n'));

var result = RepeatedCombination (['a', 'b'], 3);
alert (result.join ('\n'));

お礼

# var zero = Array (n).join ('0');

kore, omoshiroidesune.
sankouninarimashita.
arigatougozaimashita.

補足

watashigakakuto, konnnakanjidesu.

function createCcombinations(list, len) {
var max = Math.pow(list.length, len);
var results = [];
for (var i = 0; max > i; i++) {
for (var tmp = i.toString(list.length); tmp.length < len; tmp = "0" + tmp);
for (var j = 0; list.length > j; j++) tmp = tmp.replace(new RegExp(j, "g"), list[j]);
results[i] = tmp;
}
return results;
}

alert (createCcombinations(['a', 'b'], 3));
alert (createCcombinations(['a', 'b', 'c'], 2));

回答No.9

babu_baboo

ていせいです。もうしわけない。

function RepeatedCombination (ary, n) {
　var len = ary.length;
　var count = 0;
　var max = Math.pow (len, n);
　var i, o, r;

　for (; count < max; count += 1) {
　　r = [];
　　o = count;

　　for (i = 0; i < n; i++) {
　　　r.push (ary[o % len]);
　　　o = Math.floor (o / len);
　　}
　　yield r.reverse ().join ('');
　}
}

お礼

arigatougozaimashita.

回答No.8

babu_baboo

れんとうでもうしわけないね。
しょしん(No1)にかえって、ふぁいあーふぉっくすならば、yield がつかえるので、いちいち return もふようで、るーぷがすっきりになりました！

<!DOCTYPE html>
<title></title>
<body>
<script type="application/javascript; version=1.8">

function RepeatedCombination (ary, n) {
　var len = ary.length;
　var count = 0;
　var max = Math.pow (len, n);
　var m, o, r;

　for (var count = 0; count < max; count += 1) {
　　r = [];
　　o = count;
　　m = o % len;

　　for (var i = 0; i < n; i++) {
　　　m = o % len;
　　　r.push (ary[m]);
　　　o = Math.floor (o / len);
　　}
　　yield r.reverse ().join ('');
　}
}

var result = [];
var next = RepeatedCombination (['a', 'b', 'c'], 2);
for (var i in next)
　result.push (i);

alert (result.join ('\n'));

// １ぎょうなら！
alert ([i for (i in RepeatedCombination (['a', 'b'], 3))].join ('\n'));

</script>

お礼

arigatougozaimashita.

回答No.7

babu_baboo

あっ！いわゆるくろーじゃーにすれば、かんそにかけますね

function RepeatedCombination (ary, n) {
　var len = ary.length;
　var count = 0;
　var max = Math.pow (len, n);

　return function () {
　　var m;
　　var o = count;
　　var r = [];

　　for (var i = 0; i < n; i++) {
　　　m = o % len;
　　　r.push (ary[m]);
　　　o = Math.floor (o / len);
　　}
　　count += 1;
　　return (max < count) ? null: r.reverse ().join ('');
　};
}

var next = RepeatedCombination (['a', 'b', 'c'], 2);
for (var result = [], tmp; tmp = next (); result.push (tmp));
alert (result.join ('\n'));

var next = RepeatedCombination (['a', 'b'], 3);
for (var result = [], tmp; tmp = next (); result.push (tmp));
alert (result.join ('\n'));

お礼

sukoshikireini narimashitane.
arigatougozaimashita.

回答No.6

babu_baboo

さらにやっぱりおきにめさなかったのか・・・ざんねん。
たしかにこれまでのこーどは、はいれつがおおきくて、れつすうがおおいと、すくりぷとがとちゅうでとめられてしまうときがありますね。
こんどは、そこをくふうしました。

くみあわせは、なんとおりかをけいさんでもとめることができます。
そのはんいでばんごうをしていすれば、ならびをけいさんできました！

function RepeatedCombination (ary, n) {
　var len = ary.length;
　return function (count) {
　　var m;
　　var r = [];

　　for (var i = 0; i < n; i++) {
　　　m = count % len;
　　　r.push (ary[m]);
　　　count = Math.floor (count / len);
　　}
　　return r.reverse ().join ('');
　};
}

var x = 2;
var ary = ['a', 'b', 'c'];
var len = ary.length;
var max = Math.pow (len, x);
var result = [];
var getter = RepeatedCombination (ary, x);

for (var i = 0; i < max; i++)
　result.push (getter (i));

alert (result.join ('\n'));

//--

var x = 3;
var ary = ['a', 'b'];
var len = ary.length;
var max = Math.pow (len, x);
var result = [];
var getter = RepeatedCombination (ary, x);

for (var i = 0; i < max; i++)
　result.push (getter (i));

alert (result.join ('\n'));

お礼

Nshinsuuto toraerukangaekatadesune.
watashiga shitsumonnno boutounikaita kangaekatato houkouseiga onajidesune.
arigatougozaimashita.

回答No.5

babu_baboo

おきにめさなかったのか・・・ざんねん。
ほんのごくいちぶには、うける？

<!DOCTYPE html>
<title></title>
<body>
<script>

function rcombination (ary, n) {
　var s1 = [
　　　'var r = []',
　　　'var len = ary.length',
　　];
　var s2 = [];
　var code;
　var i, I;

　while (n--) {
　　i = 'i' + n;
　　I = 'I' + n;
　　s1.push ('for (var ' + i + ' = 0, I'+ n + ' = len; ' + i + ' < ' + I + '; ' + i + '++)');
　　s2.push ('ary[' + i + ']');
　}
　code = '{' + s1.join ('\n') + ' r.push (' + s2.join ('+') + ');' + 'return r;}';

　return (new Function ('ary', 'n', code))(ary, n);
}

alert(rcombination(['a', 'b'], 3).join("\n"));
alert(rcombination(['a', 'b', 'c'], 2).join("\n"));

</script>

お礼

rupuwofuyashiteiku rojikkuno hattenbandesukane.
kangaekataga omoshiroidesune.
arigatougozaimashita.

回答No.4

babu_baboo

なんとなく、おもいだしてきた。

<!DOCTYPE html>
<title></title>
<body>
<script>

function rcombination (a, n, m) {
　var r = [];
　var l = a.length;
　var i;

　if (1 < n)
　　for (i = 0; i < l; i++)
　　　r = r.concat (rcombination (a, n -1, m.concat (a[i])));

　else
　　for (i = 0; i < l; i++)
　　　r.push (m.concat (a[i]));

　return r;
}

alert(rcombination(['a', 'b', 'c'], 2, []).join("\n"));
alert(rcombination(['a', 'b'], 3, []).join("\n"));

//--

// もし、#Array.map がつかえないのなら
if(!Array.prototype.map)Array.prototype.map=function(b,e){var c=this.length;if(typeof b!="function")throw new TypeError;for(var d=Array(c),a=0;a<c;a++)a in this&&(d[a]=b.call(e,this[a],a,this));return d};

alert(rcombination(['a', 'b', 'c'], 2, []).map (function (a) { return a.join(''); }).join("\n"));
alert(rcombination(['a', 'b'], 3, []).map (function (a) { return a.join(''); }).join("\n"));

</script>

お礼

iroirogoteijishite itadakimasitaga, koregaichiban wakariyasukattadesu.
toiuka #3wo kaisekishinagara watashigakaitakodoga koretohoboonajininarimashita.

(saikinanode else noatonorupuha iranaitoomoimasuga...)
arigatougozaimashita.