プリキュア冪集合(DX3)

#!/usr/bin/ruby

precure_set = %w[
  キュアブラック
  キュアホワイト
  シャイニールミナス

  キュアブルーム
  キュアイーグレット

  キュアドリーム
  キュアルージュ
  キュアレモネード
  キュアミント
  キュアアクア
  ミルキィローズ

  キュアピーチ
  キュアベリー
  キュアパイン
  キュアパッション

  キュアブロッサム
  キュアマリン
  キュアサンシャイン
  キュアムーンライト

  キュアメロディ
  キュアリズム
]

for bits in 0..(2 ** precure_set.size - 1)
  subset = []
  precure_set.each { |element|
    if (bits & 1) == 1
      subset.push(element)
    end
    bits >>= 1
  }
  puts subset.join("")
end

解説1

映画プリキュアオールスターズの主題歌「キラキラkawaii! プリキュア大集合」にちなんでプリキュアの冪集合を出力するスクリプトを作成した。プリキュアオールスターズDX3出演プリキュア21名の全組み合わせ2097152組(空集合を含む)を出力する。

解説2

冪集合の計算アルゴリズムは以下を参考にした。

0から(2^要素数)-1(ここでは2097151)までの数の二進数表現のビットパターンを元の集合から組み合わせとして抜き出す要素のパターンと見て部分集合を順に作っていくもの。

最初、再帰と集合の組み合わせ演算子を使って冪集合の配列を作ってたけど重すぎなのでぐぐってカンニングしました。。。

追記

ファイルに出力したら512MBになった(エンコーディングUTF-8)。実行時間は real で2分弱(Athlon64 3500+ 2.2GHz)。