Non-repeat random for sorting algorithm

Question

I have this code that generates me 12 numbers from 1 to 12, then a sorting algorithm sort it out while printing out each step in a matrix.

It's all nice, but I need the random numbers non-repeated from 1 to 12.

Any idea how can I do that?

var a = new Array(12);
var i,j,k,key;


for (j=0; j<12; j++){
    a[j]=Math.floor(Math.random()*(13-1)+1);


}


document.write("Numbers:");
document.write("<TABLE align=center border=0><TR>");
for (j=0; j<12; j++){
    document.write("<TD align=right  width=20>",a[j],
    "</TD>");
}     
document.write("</TR></TABLE><CENTER><HR></CENTER>")


for (j=1; j<12; j++){
    key = a[j]; i=j-1;
    while (i>=0 && a[i]>key){
            a[i+1] = a[i]; i--
    }
    a[i+1] = key;
    document.write("<TABLE align=center border=0><TR>");
    for (k=0; k<12; k++){
                if (i<k && k<=j){
        document.write("<TD align=right width=20>",
                    "<FONT COLOR=#ff3333>",a[k],"</FONT></TD>");}
                    else{
        document.write("<TD align=right width=20>",
                    a[k],"</TD>");}
    }     
    document.write("</TR></TABLE>")
}

Implement this: http://en.wikipedia.org/wiki/Fisher%E2%80%93Yates_shuffle — Blorgbeard, Mar 10 '14 at 00:05
you generate a list of numbers from 1-12, shuffle the list, and pop() as needed. — dandavis, Mar 10 '14 at 00:08
@dandavis off the top of my head, no idea - it's not a complicated algorithm though. If I was more au fait with JS, I'd post an actual answer instead of just a comment. — Blorgbeard, Mar 10 '14 at 00:14
The FY algorithm comes up in answers a fair bit, here's a js implementation: http://stackoverflow.com/a/2450976/312962 — Darragh Enright, Mar 10 '14 at 00:27

nnnnnn · Answer 1 · 2014-03-10T00:33:53.783

You can create an array of the twelve numbers:

var nums = [1,2,3,4,5,6,7,8,9,10,11,12];
// or
var nums = [],
    max = 12;
for (var i = 1; i <= max; i++)
    nums.push(i);

And then shuffle it randomly:

nums.sort(function(a,b){ return Math.random() - 0.5; });

Returning a random number from the callback you pass to .sort() is kind of a hack, but it works well enough for casual uses where including code for a truly random sort would be overkill.

Demo: http://jsfiddle.net/5hN6t/1/

score 0 · Answer 2 · edited May 23 '17 at 12:28

0

I think all you need is to set up the seed.

Look at David Bau's answer:

Seedable JavaScript random number generator

edited May 23 '17 at 12:28

Community

1
1

answered Mar 10 '14 at 23:31

Mohamed Ennahdi El Idrissi

2,931
2
19
32

Matúš Dúbrava · Answer 3 · 2014-03-10T00:29:53.693

-1

Here is a code which fills an array with values from 1 to 12 and then shuffles them randomly.

var list = [];

for(var i=1; i<=12; i++) {
    list.push(i);   
}

for(var i=0; i<12; i++) {
    var index = Math.floor(Math.random() * 12);
    var tmp = list[i];
    list[i] = list[index];
    list[index] = tmp;
}

And here is a working example: http://jsfiddle.net/k2jh2/

edited Mar 10 '14 at 00:29

answered Mar 10 '14 at 00:23

Matúš Dúbrava

771
5
18

This is not a correct implementation of the Fisher-Yates algorithm. – user515430 Mar 10 '14 at 00:32
1

Sorry but I do not see any statement from my side that this would be a Fisher-Yates algorithm. This is something that came first on my mind and serves the purpose. – Matúš Dúbrava Mar 10 '14 at 00:35
Fisher-Yates algorithm guarantees that all permutations have the same probability. Your algorithm does not have this desired property. n^n is not divisible by n! for n > 2. – user515430 Mar 10 '14 at 00:45
Thanks for explaining the obvious. Again, I do not remember saying anything about perfect randomness. And even if you do the exact implementation of Fisher-Yates algoritm in javascript. Can you really say that the random numer generator you have used produces perfectly random numbers. Guess what? You cannot. Therefore, not even that would produce something with "desired property". And question was not about perfect randomness. Therefore I cannot see how my answer is wrong. – Matúš Dúbrava Mar 10 '14 at 01:02
When there is a mathematically correct algorithm that is easy to implement, same number of lines as your program, I see no reason to be satisfied with a somewhat random algorithm. I think the community deserves better. – user515430 Mar 10 '14 at 01:08

Non-repeat random for sorting algorithm

3 Answers3