λ Fisher-Yates shuffle

======= Algorithm ======= <syntax js> function shuffle(a) { for (var i=a.length-1; i>0; i--) { // j is a random integer [0-i] var j = Math.floor(Math.random()*(i+1)); swap(a, j, i); } return a; } </syntax> ======= Support ======= <syntax js> function swap(a, i, j) { var t = a[i]; a[i] = a[j]; a[j] = t; } function run(a) { return shuffle(a); } </syntax> ======= Tests ======= <syntax js> </syntax> ======= Options ======= <syntax js> { "title":"Fisher-Yates shuffle", "height":"270px" } </syntax> ======= Visualisation ======= <syntax html> <html> <head> <style type='text/css'> .chart rect { fill: steelblue; notstroke: white; } .chart rect.index { fill: red; } .chart rect.index2 { fill: green; } </style> <script src="http://d3js.org/d3.v2.js"></script> <script type="text/javascript"> var chart; var width = 300; window.onload = function() { // Setup the chart chart = d3.select("#chart").append("svg") .attr("class", "chart") .attr("width", width) .attr("height", 256); } var a = []; var hashIndex = 0; function n(d) { this.data = d; // Save a 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<c; i++) { a2.push(a[i].data); } return a2; } else { return a; } } 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> </syntax>