組み合わせを爆発させる簡単な方法。
追記:qiitaにある再帰版の方がよい。
やりたいことは、[A,B,C,D]という配列があったら、順にA, B, C, D, AB, AC, AD, BC, BD, CD, ABC, ABD, ACD, BCD,ABCDという出力をするようなプログラムを作ること。もちろん配列の長さはあらかじめ決まっていない。(とはいえ、せいぜい31まで(javascript の場合)。 64ビット整数の使える言語なら64までの長さの配列の組み合わせを求められると思うかも知れないが、残念ながら2の64乗をすべてカウントするのは今のCPUではまだ力が足りない感じである。ただし33,34くらいはイケる気がする)。 すべての組み合わせを出力するということは、配列を集合と見てすべての部分集合を出力するということである(空集合はあえて出力していないわけだが)。 だが、実力不足でこの通りのプログラムはちょっと思いつかなかった。 仕方がないので配列とnを入力としてちょうどn個の組み合わせを出力するプログラムを考えた。[A, B, C, D], 2 ならAB, AC, AD, BC, BD, CDと出力する訳である。もちろん、このプログラムを使ってあるいは内部でnを変えてループすれば最初の目的は達成できる。 javascript にはgenerator という仕組みがあるのでそれを利用して書いてみた。簡単なテストは済んでいる。(今、思ったけど、入力のarray はコピーしておいた方がいいかも)。
function* combgenerator(array, num) { var idx = 0; const maxidx = 2**array.length; while (idx < maxidx) { if (ones32(idx) == num) { const result = []; var tmp = idx; var p = 0; while (tmp > 0) { if (tmp & 1) { result.push(array[p]); } tmp = tmp >> 1; p++; } yield result; } idx++ } }
ここで ones32 というのは
The Aggregate Magic Algorithms
に書かれているプログラムである。ただし、javascriptの場合符号なし32ビット整数はないので、0x7fffffff とANDを取って31ビット整数にしておいた方がよい。(31ビット以下しか使わないなら必要ないけど)
使い方というか、jestのテストプログラムの一部だが
test('combgenerator', () => { var a = ['A','B','C','D']; var comb = combgenerator(a, 1); var b = []; for (const val of comb) { b.push(val); } expect(b.join(',')).toBe('A,B,C,D'); var comb = combgenerator(a, 2); var b = []; for (const val of comb) { b.push(val.join('')); } expect(b.sort().join(',')).toBe('AB,AC,AD,BC,BD,CD'); var comb = combgenerator(a, 3); var b = []; for (const val of comb) { b.push(val.join('')); } expect(b.sort().join(',')).toBe('ABC,ABD,ACD,BCD'); });
nを指定しないで、無駄なくn=1から順に組み合わせを出力するには、32ビット(または64ビットでもいいが)の数を1のビットの数の少ない方から順番に(無駄なく)全部出力するプログラムがあればよい。これが思いつかないのだ。たぶん、やさしくないのだろう。 なお、n=1や2と決まっている場合は、先のプログラムは多いに効率が悪いので単純ループや2重ループの方がよい。