forked from: １行でArrayをシャッフルする

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

// forked from nemu90kWw's １行でArrayをシャッフルする
package {

	import flash.display.*;
	import flash.text.*;

	public class Shuffle extends Sprite
	{
		private var textfield:TextField;
		
		function Shuffle()
		{
			var i:int, array:Array, text:String = "";
			
			//text += "Array.sort(function():int{return int(Math.random()*3)-1});\nで、配列をシャッフルできる。\n\n";
			
			//text += "◆シャッフルのテスト\n";
			array = new Array();
			for(i = 1; i <= 10; i++) {array.push(i);}
			/*text += "array = ["+array+"]\n\n";
			text += shuffle(array.slice())+"\n";
			text += shuffle(array.slice())+"\n";
			text += shuffle(array.slice())+"\n";
			text += shuffle(array.slice())+"\n";
			text += shuffle(array.slice())+"\n";
                        text += '\nたった5回の試行だがなんとなく偏っている気がしないだろうか。\n';
                        */
                        text += '10個の要素にシャッフルを1000回試行して各要素がシャッフルされた配列のどの位置にいるかを平均するメソッドを追加し、理論的にテストしてみた。\n';
                        text += '10個要素があるので、indexの平均が4.5に近いほど均等に分布していることになる。\n';
			
			text += "\n◆sortを使用したシャッフルの分布のテスト\n";
                        text += JSON.stringify(trial(shuffle, array.slice()), null, 4);
			
                        text += "\nこれがどのくらい偏ってるのかわかりづらいかと思う。下のFisher-Yatesアルゴリズムでのシャッフルの結果と比較して頂きたい。\n";
                        
			text += "\n◆Fisher-Yatesアルゴリズムのシャッフルの分布のテスト\n";
                        text += JSON.stringify(trial(goodShuffle, array.slice()), null, 2);
			
			textfield = new TextField();
                        textfield.defaultTextFormat = new TextFormat('monospace', 10);
			textfield.x = textfield.y = 20;
                        textfield.wordWrap = true;
			textfield.width = textfield.height = 400;
			textfield.text = text;
			addChild(textfield);
		}
		
		public function shuffle(array:Array):Array
		{
			return array.sort(function():int{return int(Math.random()*3)-1});
		}

                public function goodShuffle(array:Array):Array
                {
                        var i:int = array.length;
                        if (i === 0) {
                            return array;
                        }
                        var j:int, temp:*;
                        while (--i) {
                            j = Math.floor(Math.random() * (i + 1));
                            temp = array[i];
                            array[i] = array[j];
                            array[j] = temp;
                        }
                        return array;
                }

                public function trial(func:Function, array:Array):Object
                {
                        var average:Object = {};
                        array.forEach(function (elem:*, i:int, arr:Array):void {
                            average[elem] = 0;
                        });
                        const TRIALS:int = 1000;
                        var i:int = TRIALS;
                        while (i--) {
                            var arr:Array = func(array.slice());
                            for (var elem:* in average) {
                                average[elem] += arr.indexOf(elem);
                            }
                        }
                        var totalIndex:int = 0;
                        for (elem in average) {
                            average[elem] /= TRIALS;
                        }
                        return average;
                }
	}
}