Forked from:: nemu90kWw's forked from: forked from: １行でArrayをシャッフルする

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

Array.sortが元Arrayを変更することを忘れてた。
sliceでクローンを作ってからシャッフルしたら偏りが顕著に。
sortを使うのは凄く良いアイディアかと一瞬思いましたが、
このアプローチで分布を一様にすることは数学的に不可能です
なので良くアルゴリズム辞典にあるようなソートを1ライナーにしてみました。

9re

forked:1
favorite:5
lines:104
license : MIT License
modified : 2009-10-08 14:23:28

Embed: Tweet

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

// Array.sortが元Arrayを変更することを忘れてた。
// sliceでクローンを作ってからシャッフルしたら偏りが顕著に。

// sortを使うのは凄く良いアイディアかと一瞬思いましたが、
// このアプローチで分布を一様にすることは数学的に不可能です
// なので良くアルゴリズム辞典にあるようなソートを1ライナーにしてみました。

package
{
	import flash.display.*;
	import flash.text.*;
	import flash.events.*;

public class Shuffle extends Sprite
	{
		private var textfield:TextField = new TextField();
		private var textfield2:TextField = new TextField();
		private var button:Sprite = new Sprite();
		private var buttontext:TextField = new TextField();
		
		function Shuffle()
		{
			textfield.x = 10;
			textfield.y = 40;
			textfield.width = 465/2-10;
			textfield.height = 465-50;
			textfield2.x = 465/2;
			textfield2.y = 40;
			textfield2.width = 465/2-10;
			textfield2.height = 465-50;
			
			addChild(textfield);
			addChild(textfield2);
			
			button.x = 10;
			button.y = 10;
			button.mouseChildren = false;
			button.buttonMode = true;
			button.graphics.lineStyle(1, 0xBBBBBB);
			button.graphics.beginFill(0xEEEEEE);
			button.graphics.drawRoundRect(0, 0, 100, 20, 5, 5);
			button.graphics.endFill();
			addChild(button);
			
			buttontext = new TextField();
			buttontext.width = 100;
			buttontext.height = 20;
			buttontext.htmlText = "<p align='center'><font face='_sans'>再計算</span></p>";
			button.addChild(buttontext);
			
			button.addEventListener(MouseEvent.CLICK, function(e:Event):void{test();});
			test();
		}
		
		private function test():void
		{
			var i:int, array:Array, text:String = "", text2:String = "";
			var N : int = 10000;
			
			text += "return Math.random() > 0.5 ? 1 : -1;\n\n";
			text += "◆シャッフルのテスト\n";
			array = new Array();
			for(i = 1; i <= 10; i++) {array.push(i);}
			text += "array = ["+array+"]\n\n";
			
			text += shuffle(array)+"\n";
			text += shuffle(array)+"\n";
			text += shuffle(array)+"\n";
			text += shuffle(array)+"\n";
			text += shuffle(array)+"\n";
			
			text += "\n◆分布のテスト\n";
			array = new Array();
			for(i = 1; i <= 3; i++) {array.push(i);}
			
			var result:Object = {"1,2,3":0,"1,3,2":0,"2,1,3":0,"2,3,1":0,"3,1,2":0,"3,2,1":0};
			
			for(i = 0; i < N; i++) {result[shuffle(array)]++;}
			
			var xi2 : Number = 0.0;
			for(var str:String in result) {
				text += "["+str+"] = "+result[str]+"\n";
				xi2 += (result[str] - N/6) * (result[str] - N/6) / (N/6);
			}
			text += "χ^2=" + xi2 + "\n";
			
			text2 += "よくあるアルゴリズム\n\n";
			text2 += "◆シャッフルのテスト\n";
			array = new Array();
			for(i = 1; i <= 10; i++) {array.push(i);}
			text2 += "array = ["+array+"]\n\n";
			
			text2 += shuffle_new(array)+"\n";
			text2 += shuffle_new(array)+"\n";
			text2 += shuffle_new(array)+"\n";
			text2 += shuffle_new(array)+"\n";
			text2 += shuffle_new(array)+"\n";
			
			text2 += "\n◆分布のテスト\n";
			array = new Array();
			for(i = 1; i <= 3; i++) {array.push(i);}
			
			result = {"1,2,3":0,"1,3,2":0,"2,1,3":0,"2,3,1":0,"3,1,2":0,"3,2,1":0};
			
			for(i = 0; i < N; i++) {result[shuffle_new(array)]++;}
			
			xi2 = 0.0;
			for(str in result) {
				text2 += "["+str+"] = "+result[str]+"\n";
				xi2 += (result[str] - N/6) * (result[str] - N/6) / (N/6);
			} 
			text2 += "χ^2=" + xi2 + "\n";
			
			textfield.text = text;
			textfield2.text = text2;
			return;
		}
		
		public function shuffle_new(array:Array):Array
		{
			for(var j:int, t:Number, i:int = array.length, a:Array = array.slice();i; j = Math.random() * i, t = a[--i], a[i] = a[j], a[j] = t);return a;
		}
		
		public function shuffle_original(array:Array):Array
		{
			return array.slice().sort(function():int{return int(Math.random() * 3) - 1;});
		}
		
		public function shuffle(array:Array):Array
		{
			return array.slice().sort(function():int{return Math.random() > 0.5 ? 1 : -1;});
		}
	}
}

Code Fullscreen

Preview Fullscreen