chibitamiお兄ちゃんの問題

/**
 * Copyright uwi ( http://wonderfl.net/user/uwi )
 * MIT License ( http://www.opensource.org/licenses/mit-license.php )
 * Downloaded from: http://wonderfl.net/c/e67h
 */

package {
    import flash.display.Sprite;
    import flash.text.TextField;
    import flash.utils.getTimer;
    // @see http://twitter.com/chibitami/status/19325878442
    public class Nya extends Sprite {
        private var _tf : TextField;
  
        public function Nya() {
            _tf = new TextField();
            _tf.width = 465;
            _tf.height = 465;
            addChild(_tf);
            
            var s : int = getTimer();
            solve(5, 3, [0.1, 0.3, 0.2, 0.25, 0.15]);
            var g : int = getTimer();
            tr((g - s) + " ms");
        }

        private function solve(n : uint, m : uint, p : Array) : void
        {
            rec(n, m, 0, p);
        }
        
        private var _sub : Array = [];
        
        // 再帰で部分集合をげっと
        private function rec(n : uint, m : uint, pos : uint, p : Array) : void
        {
            if(_sub.length == m){
                dp(m, p, _sub);
                return;
            }
            for(var i : uint = pos;i < n;i++){
                _sub.push(i);
                rec(n, m, i + 1, p);
                _sub.pop();
            }
        }

        // sub[0], sub[1], ...の順番でとるとき、確率は
        // p[sub[0]]*(p[sub[1]]/(1-p[sub[0]])
        //          *(p[sub[2]]/(1-p[sub[0]]-p[sub[1]])
        //          *...
        // と表されるので、分子はただ掛ければよくて、
        // 分母は、sub[0]とsub[1]を既にとったーみたいな情報を持つ構造をつくって割っていけばよい。
        // 1<<mのテーブルを用意する。
        // 2進数tに対し、1になっているところは既にボールを取り出したとすると、
        // map[t]は、これまでtになるように取り出してきたボールすべての分母の和となる。
        // m回繰り返して、map[1<<m-1]が答え。
        private function dp(m : uint, p : Array, sub : Array) : void
        {
            var lim : uint = 1 << m;
            var map : Vector.<Number> = new Vector.<Number>(lim);
            var i : uint;
            for(i = 0;i < lim;i++)map[i] = 0;
            map[0] = 1;
            
            var filled : Object = {0:0};
            var f : uint;
            for(i = 0;i < m;i++){
                for each(f in filled){
                    var div : Number = 1.0;
                    for(var b : uint = 1, c : uint = 0;c < m;b <<= 1, c++){
                        if(f & b)div -= p[sub[c]];
                    }
                    map[f] /= div;
                }
                
                var nfilled : Object = {};
                for each(f in filled){
                    for(var k : uint = 1;k < lim;k<<=1){
                        if(!(f & k)){
                            map[f | k] += map[f];
                            nfilled[f|k] = f|k;
                        }
                    }
                }
                filled = nfilled;
            }
            
            var mul : Number = 1.0;
            for each(var s : uint in sub){
                mul *= p[s];
            }
            
            tr(sub, " p=" + mul * map[lim - 1]);
        }

        private function tr(...o : Array) : void
        {
            _tf.appendText(o + "\n");
            _tf.scrollV = _tf.maxScrollV;
        }
    }
}