同僚に冪集合作ってみては、と言われたので作った。冪集合はhttp://www.geocities.jp/k27c8_math/math/set_theory/power_set.htmとかに書いてあるとおり、渡された集合の部分集合全体。
考え方
思いついたのは以下の考え方。
- [ 1, 2, 3 ]と渡されたとする
- 冪集合とは、それぞれを含む・含まないを全通り集めたものと考える
- すると、[ 0, 0, 0 ], [ 0, 0, 1 ], [ 0, 1, 0 ], ..., [ 1, 1, 1 ]のようなbit配列を考え、1なら対応する要素をピックアップすると考えたらいい
- ループは2の3乗分行えば良いはず
実装
import java.util.ArrayList; import java.util.List; public class PowerSet1 { public static List<List<Integer>> make(List<Integer> data) { if (data.size() == 0) { List<List<Integer>> empty = new ArrayList<>(); empty.add(new ArrayList<>()); return empty; } List<List<Integer>> result = new ArrayList<>(); for (int i = 0; i < Math.pow(2, data.size()); i++) { List<Integer> set = new ArrayList<>(); int flags = i; for (int j = 0; j < data.size(); j++) { // 2で割った余りが2進数における1桁目 int flag = flags % 2; if (flag == 1) { set.add(data.get(j)); } // 1桁ずらす flags = flags / 2; } result.add(set); } return result; } }
まとめ
bit配列という考え方でピックアップするかしないかを決めるのが面白い。この考え方は重複順列でも利用できて、重複順列ならデータの長さnを使ってn進数で考えれば同じようにできそう。別の問題が同じような考え方で実装できるのは面白いですね。
