power setの計算

javaでpower set（べき集合）を計算するプログラムを考えています。が、どうやったらいいのかアイディアが浮かびません。どんな些細な事でも結構ですので、ヒントを頂けないでしょうか？

よろしくお願い致します。

No.1 ベストアンサー 回答者： liar_adan 回答日時： 2003/11/01 16:20

若干トリッキーですが、

元の数があまり多くなければ、2進法を応用することで可能です。

char num = 0;
として、これを++していくと、2進法では
0000 0000 0000 0000
から
1111 1111 1111 1111
まで変化します。
n番目のバイトが1になっていたらn番目の元を含む集合を作る…としていくと、
べき集合ができてきます。
n番目のバイトを調べるのは、シフト演算子>>や、ビット論理積演算子&などを使います。

同様な方法で、intを使えば32個まで、
longを使えば64個までのべき集合が作れます。
とはいっても実用的には20数個の元が限界でしょう。

この回答へのお礼

liar_adan さん、

早速のご回答ありがとうございました。
2進法を使ってべき集合を考えるとは思いもつきませんでした。素晴らしいヒント、どうもありがとうございました。

お礼日時：2003/11/01 16:31

No.2 回答者： Harry_ 回答日時： 2003/11/02 13:24

たとえば {l,m,n} のべき集合は、

{l,m} のべき集合に加えて、そのそれぞれの部分集合にそれぞれ n を追加した集合を含む、

という再帰アルゴリズムが使えないでしょうか。
わかりにくい日本語で申し訳ないですが。

この回答へのお礼

Harry_さん、

ご回答どうもありがとうございました。
再帰を使うんですね。この方法もうかびませんでした。
参考にさせていただきます。
ありがとうございました。

お礼日時：2003/11/02 17:29