User Tools

Site Tools


Differences

This shows you the differences between two versions of the page.

Link to this comparison view

Both sides previous revision Previous revision
Next revision
Previous revision
algorithm:fisher-yates_shuffle [2012/10/02 22:24]
will
algorithm:fisher-yates_shuffle [2015/02/02 08:28] (current)
Line 1: Line 1:
-[algorithm ​Fisher-Yates shuffle]+======= λ Fisher-Yates shuffle ​======
  
-====== Algorithm ======+<​nowiki>​ 
 +======= Algorithm ​=======
 <syntax js> <syntax js>
 function shuffle(a) { function shuffle(a) {
     for (var i=a.length-1;​ i>0; i--) {     for (var i=a.length-1;​ i>0; i--) {
-        var j = Math.floor(Math.random()*(i+1)); ​// j random integer [0-i]+        ​// j is a random integer [0-i] 
 +        ​var j = Math.floor(Math.random()*(i+1));​
         swap(a, j, i);         swap(a, j, i);
     }     }
Line 12: Line 14:
 </​syntax>​ </​syntax>​
  
-====== Support ======+======= Support ​=======
 <syntax js> <syntax js>
 function swap(a, i, j) { function swap(a, i, j) {
     var t = a[i]; a[i] = a[j]; a[j] = t;     var t = a[i]; a[i] = a[j]; a[j] = t;
 } }
-a = [1,​2,​3,​4,​5,​6,​7,​8,​9,​0];​ +function run(a) {
-function run() {+
     return shuffle(a);     return shuffle(a);
 } }
 </​syntax>​ </​syntax>​
  
-====== Visualisation ======+======= Tests ======= 
 +<syntax js> 
 +</​syntax>​ 
 + 
 +======= Options ======= 
 +<syntax js> 
 +
 +    "​title":"​Fisher-Yates shuffle",​ 
 +    "​height":"​270px"​ 
 +
 +</​syntax>​ 
 + 
 +======= Visualisation ​=======
 <syntax html> <syntax html>
 <​html>​ <​html>​
-  ​<​head>​ +<​head>​ 
-    <script type="​text/​javascript">​ +<style type='​text/​css'>​ 
-        function ​update(n, x) { +.chart rect { 
-            var element ​document.getElementById("container")+  fill: steelblue;​ 
-            var i = x.lookupInScope("i"); +  notstroke: white; 
-            var j = x.lookupInScope("j"); +
-            var a = x.lookupInScope("a"); +.chart rect.index { 
-            var xValue = x.lookupInScope("x"); +  fill: red; 
-            if (a) { +
-               ​var arrayString ​"["+.chart rect.index2 { 
-               for (var k=0; k<​a.length;​k++) { +  fill: green; 
-                   arrayString += i===k? "<​span style=\"​color:​red\">"​+a[k]+"</​span>"​ : j===k? "<span style=\"​color:​blue\">​"+a[k]+"</​span>"​ : a[k]+
-                   if (k < a.length-1) arrayString +", "+</​style>​ 
-               ​+<script src="​http://​d3js.org/​d3.v2.js"></​script>​ 
-               arrayString += "​]";​ +<script type="​text/​javascript">​ 
-               ​var html "= " ​arrayString+var chart; 
-               ​if (i) { +var width = 300; 
-                   html +"<​br>"​ + "i = "+i; +window.onload = function() { 
-               } +    // Setup the chart 
-               ​element.innerHTML = html; +    chart d3.select("#chart").append("svg") 
-           }+        .attr("class",​ "chart") 
 +        .attr("width", width
 +        .attr("height", 256); 
 +
 + 
 +var = []
 +var hashIndex ​= 0; 
 +function n(d) { 
 +    ​this.data ​d; 
 +    // Save hash so we can uniquely identify each number. 
 +    this.hash ​= ""​+hashIndex;​ 
 +    hashIndex++; 
 +    this.valueOf ​function() {return this.data;}
 +
 + 
 +for (var j=0; j<20; j++) { 
 +    ​a.push(new n(1+j))
 +
 + 
 +function args(forCloning) { 
 +    ​if (forCloning) { 
 +        var a2 []; 
 +        for (var i=0, c=a.length; ​i<ci++) { 
 +            a2.push(a[i].data);
         }         }
-    ​</​script>​ +        return a2; 
-  </​head>​ +    } 
-  <​body>​ +    else { 
-  <pre id="container"></​pre+        return a; 
-  </​body>​+    } 
 +
 + 
 +function update(n, x, isRunning, duration) { 
 +    if (duration < 0) { 
 +        return; // State-less visualisation. 
 +    } 
 +    if (x) { 
 +        var idx = x.lookupInScope("​i"​);​ 
 +        var idx2 = x.lookupInScope("​j"​);​ 
 +         
 +        drawGraph(a,​ idx, idx2, duration);​ 
 +    } 
 +
 + 
 +function drawGraph(a,​ idx, idx2, duration) { 
 +    var n = a.length; 
 +    var barWidth = Math.floor((width-20-2*(n-1))/​n);​ 
 +    var barSpacing = barWidth+2;​ 
 +     
 +    var bars = chart.selectAll("​rect"​).data(a,​ function(d) {return d.hash;​});​ 
 +     
 +    bars.enter().append("​rect"​) 
 +        .attr("​y",​ function(d) { return 256 - d*10; }) 
 +        .attr("​height",​ function(d) { return d*10; }) 
 +        .attr("​width",​ barWidth);​ 
 +     
 +    bars.transition().duration(duration).attr("​x",​ function(d, i) { return barSpacing*i;​ }); 
 +     
 +    bars.classed("​index",​ function(d, i) {return i===idx || i===idx2});​ 
 +
 +</​script>​ 
 +</​head>​ 
 +<​body>​ 
 +<div id="chart"></​div
 +</​body>​
 </​html>​ </​html>​
 </​syntax>​ </​syntax>​
 +</​nowiki>​
algorithm/fisher-yates_shuffle.1349241859.txt.gz · Last modified: 2015/02/02 08:23 (external edit)