要素の数が n の集合のべき集合（に相当する配列）を得る

はじめに

• 要素の数が n の集合のべき集合 を得るコードを書きました。
• 使用したプログラミング言語はJavaScriptです。
• 数学の集合の代替として、コードでは配列を使っています。
• 要素数が n の集合を表す配列としては、[0, 1, 2 ... n-1] を使います。

仕様

非負の整数 n を受け取り、べき集合に相当する配列を返す関数 powerSet を作成しました。

powerSet(n)

powerSet(n) の仕様は以下です。

• 引数の n として非負の整数を受け取る。それ以外の場合は、Error をスローする。
• 以下は、n が 0以上2以下の場合の、powerSet(n) が返す配列の例になります。
  • powerSet(0)： 空集合Φのべき集合を表す配列 [ [] ] を返す。
  • powerSet(1)： 要素が1個の集合 { 0 } のべき集合を表す配列 [ [], [0] ] を返す。
  • powerSet(2)： 要素が2個の集合 { 0, 1 } のべき集合を表す配列 [ [], [0], [1], [0, 1] ] を返す。
  • powerSet(3)： 要素が3個の集合 { 0, 1, 2 } のべき集合を表す配列 [ [], [0], [1], [2], [0, 1], [0, 2], [1, 2], [0, 1, 2] ] を返す。
• また、powerSet(n).length は、要素数nの集合のべき集合の要素数なので、2のn乗になります。

コード

再帰を使って以下のように実装しました。

const powerSet = (n = 0, sorting = false) => {
  if (!Number.isInteger(n) || n < 0) {
    throw new Error('parameter must be non-negative integer');
  }
  if (n === 0) {
    return [[]];
  }
  const prev1 = powerSet(n-1),
        prev2 = prev1.map(a => [...a, n-1]);
  return sorting ? [...prev1, ...prev2].sort(arrayCompare) : [...prev1, ...prev2];
}

• 上記のコード内で、ソートの比較関数として使っているarrayCompare　は以下です。

const arrayCompare = (a1, a2) => {
  const lenDiff = a1.length - a2.length;
  if (lenDiff) {
    return lenDiff;
  }
  const i =  a1.findIndex((e, j) => e - a2[j] !== 0);
  return i >= 0 ? a1[i] - a2[i] : 0;
}

arrayCompareを使って、powerSet のほうで、

return sorting ? [...prev1, ...prev2].sort(arrayCompare) : [...prev1, ...prev2];

と、引数の sorting が true のときにソートをした結果を返しているのは、結果として得られる配列を、要素数の少ない配列要素から順に、要素数が同じならば、要素の配列が、より小さい数が先にくるものが、先頭に近いほうにくるように並べたいためです。

実行例

for (let n=0; n <=4; ++ n) {
  console.log(JSON.stringify(powerSet(n, true)));
}

上記にて、以下のように出力されます。

[[]]
[[],[0]]
[[],[0],[1],[0,1]]
[[],[0],[1],[2],[0,1],[0,2],[1,2],[0,1,2]]
[[],[0],[1],[2],[3],[0,1],[0,2],[0,3],[1,2],[1,3],[2,3],[0,1,2],[0,1,3],[0,2,3],[1,2,3],[0,1,2,3]]

• 上記を確認するためのCodePen

応用例

6個の数値、100, １20, 170, 240, 330, 430 から、少なくとも3個以上、最大で6個すべての数字を取り出して合計値を作る。

• 100,170, 330　の３つを選ぶと、合計は 600(=100+170+330)
• 6個すべてを選ぶと、合計は 1390(=100+120+170+240+330+430)
• 100と １20 の２つだけ選ぶということはできない。最低3つ選ぶ。

このとき、すべての選び方について、選んだ値の合計値を小さい順に並べた配列は、先述のpowerSet を使って以下で得られる。

const values = [100, 120, 170, 240, 330, 430];
const choices = powerSet(values.length, true).filter(ary => ary.length >= 3).map(a => a.map(i => values[i]));
const totals = [...new Set(choices.map(ary => ary.reduce((s,v) => s + v)))].sort((v1, v2) => v1 - v2);

console.log(totals)

• 上記を確認するためのCodePen

上記により、以下が表示されます。

[
   390,  460,  510,  530,  550,  600,  620,
   630,  650,  670,  690,  700,  720,  740,
   770,  790,  820,  840,  860,  880,  890,
   930,  940,  960,  980, 1000, 1030, 1050,
  1060, 1100, 1120, 1150, 1170, 1220, 1270,
  1290, 1390
]

以上