Random 1-5 5x5 Array

Question

I am trying to make a 5x5 table that will have the numbers 1-5 random put in the rows/columns. But they need to have all different numbers for each row and column.

ex: 12345 54123 41532 35214 23451

The code I currently have is very long so I will give a pastebin link to it. http://pastebin.com/ex1bcLxh

Any and all help will be appreciated.

Answer 1

There are 56 reduced Latin squares of order 5, enumerated here. "Reduced" means that each of them has the top row and the leftmost column in sorted order.

You can apply any permutation to the rows, or to the columns, of a Latin square, and the result will also be a Latin square. It also follows that any Latin square can be converted to a reduced Latin square by:

1. permuting all n columns to put the top row in sorted order
2. permuting the bottom (n-1) rows to put the left column in sorted order.

(The top left element is already in its correct position after the first permutation, so there are only n-1 rather than n rows to sort in the second step.)

So by reversing this operation, we can start with one of the 56 reduced Latin squares, and generate any of the 56*(5!)*(4!) = 161280 squares representing the complete set.

So:

1. Choose one of the 56 reduced order-5 Latin squares at random.
2. Choose one of the 4!=24 permutations of the bottom four rows at random, and apply it.
3. Choose one of the 5!=120 permutations of all five columns at random, and apply it.

Assuming uniformly distributed samples in steps 1-3, this process should yield uniformly distributed samples from the complete set of 161280 order-5 Latin squares.

Answer 2

Here's what I came up with off the top of my head - I haven't bothered with optimisation because for the grid size of 5x5 mentioned in the question it feels instantaneous. (Testing in IE7 even 7x7 grids only take a couple of seconds. 8x8 is noticeably slower, sometimes slow enough to trigger the long-running script error.)

function createGrid(size) {
   var grid = [],
       row = [],
       x,y,t;

   for (x=size; x>0; x--)
      row.push(x);

   addRows:
   while (grid.length < size) {
      t = row.slice();
      row = [];
      while (t.length > 0)
         row.push(t.splice(Math.floor(Math.random() * t.length), 1)[0]);

      for (y=0; y<grid.length; y++)
         for (x=0; x<size; x++)
            if (row[x] === grid[y][x])
               continue addRows;

      grid.push(row);
   }

   return grid;   
}

var test = createGrid(5);
alert(test.join("\n"));

In case it's not obvious, the basic idea is to start off with a row [5,4,3,2,1]; shuffle the row and check if it can be added; repeat until done.

(I thought about starting by generating all potential rows and then randomly choosing from them, but that seemed like too much hassle given that I'm not very good with permutation algorithms - just doing a random shuffle each time seemed a lot less trouble.)