Случайный 1-5 5x5 Array

Question

Я пытаюсь создать таблицу 5х5, в которой в строки / столбцы будут вставлены случайные числа 1-5.Но они должны иметь все разные номера для каждой строки и столбца.

Например: 12345 54123 41532 35214 23451

Код, который у меня есть в настоящее время, очень длинный, поэтому я дам ссылку на него в виде вставки,http://pastebin.com/ex1bcLxh

Любая помощь будет оценена.

Answer 1

Есть 56 сокращенных латинских квадратов порядка 5, нумерованных здесь .«Уменьшенный» означает, что у каждого из них есть верхний ряд и самый левый столбец в отсортированном порядке.

Вы можете применить любую перестановку к строкам или столбцам латинского квадрата, и результатом также будет латинский квадрат.Из этого также следует, что любой латинский квадрат может быть преобразован в уменьшенный латинский квадрат:1) строки для размещения левого столбца в отсортированном порядке.

(Верхний левый элемент уже находится в правильном положении после первой перестановки, поэтому для сортировки существует только n-1, а не n строкна втором шаге.)

Итак, изменив эту операцию, мы можем начать с одного из 56 сокращенных латинских квадратов и сгенерировать любой из 56 * (5!) * (4!) = 161280 квадратовполный набор.

Итак:

1. Выберите один из 56 латинских квадратов уменьшенного порядка-5 в случайном порядке.
2. Выберите одну из 4! = 24 перестановок нижних четырех строк случайным образом и примените ее.
3. Выберите одну из 5! = 120 перестановок всех пяти столбцов случайным образом и примените ее.

При условии равномерно распределенных выборок на этапах 1-3, этот процесс должен дать равномерно распределенные выборки из полного набора 161280 латинских квадратов порядка 5.

Answer 2

Вот то, что я придумала с головы до головы - я не потрудился на оптимизации, потому что для размера сетки 5х5, упомянутого в вопросе, это чувствуется мгновенно.(Тестирование в IE7 даже на сетках 7x7 занимает всего пару секунд. 8x8 заметно медленнее, иногда достаточно медленное, чтобы вызвать длительную ошибку сценария.)

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"));

В случае, если это не очевидно, основная идеяначинать со строки [5,4,3,2,1];перемешайте строку и проверьте, можно ли ее добавить;повторяйте, пока не закончите.

(Я думал о том, чтобы начать с генерации всех потенциальных строк и затем случайного выбора из них, но это казалось слишком сложным, учитывая, что я не очень хорош с алгоритмами перестановки - просто делаю случайныетасовать каждый раз казалось гораздо меньше проблем.)

Answer 3

Как указал Тед Хопп , это также известно как Латинский квадрат .

Латинские квадраты - это класс точное покрытие проблема, следовательно, решение может быть найдено с использованием Алгоритма Кнута X .

Представление Dancing Links не должно быть слишком сложным для кодирования в Javascript.Я реализовал нечто подобное в Lua.

Терминология может сбивать с толку, поскольку описание алгоритма относится к «матрице», «строкам» и «столбцам», однако это не то же самое, что строки истолбцы вашей (выходной) матрицы.Вместо этого «строки» - это записи-кандидаты в вашем массиве (a[1][2]=3 и т. Д.), А «столбцы» - шаблоны, в которых либо одна координата, либо значение является подстановочным знаком, например, a[Y][2]=3, a[1][X]=3, a[1][2]=V.

Чтобы выбрать случайное решение, вы можете случайным образом перемешать список записей, прежде чем присваивать их «строкам» алгоритма.(В случае представления «Танцующие ссылки» строки образуют круговой список, и вы можете вставлять записи в этот список в произвольном порядке.)

Answer 4

В общем, это сложная задача, особенно если вы беспокоитесь о равномерном распределении по всем латинским квадратам. (По крайней мере, одна книга полностью посвящена этой теме.) Вот псевдокод для одного алгоритма (не самый эффективный, но выполнит работу):

for each row {
   make an array of the integers 1..N
   repeat {
       make a random permutation of the array
   } while (array conficts with any previously assigned row)
   set row to array
}

(Массив a "конфликтует" со строкой r, если a[i] == r[i] для некоторого i в строке.) Это предполагает, что у вас есть код для случайного перемешивания массива. Поищите в Интернете, если у вас нет удобного алгоритма перемешивания.