Перемешивание массива

[Макс]

Задача
Есть массив(двухмерный). Нужно переставить в нем элементы случайным образом.
Подскажите алгоритм плиз.
(реализация будет на pascal/delphi)


PS
желательно попроще (можно даже в ущерб случайности - это для курсовой надо

[Stas]

blin, mne samomu interesno stalo..
КшЫуфксрук chio skazhesh\' ?

program shuffle_array;

uses
    crt;

const
     SIZE=4;

var
   massiv:array[0..SIZE-1,0..SIZE-1] of integer;
   i,j,newi,newj,temp: integer;

begin
     clrscr;
     for i:=0 to SIZE-1 do
         for j:=0 to SIZE-1 do
         begin
              write(\'Enter number for matrix position [\',i+1,\'] [\',j+1,\']:\');
              readln(massiv[j]);
         end;

     randomize;
     for i:=0 to SIZE-1 do
         for j:=0 to SIZE-1 do
         begin
              temp:=massiv[j];
              newi:=i+random(SIZE-i);
              newj:=j+random(SIZE-j);
              massiv[j]:=massiv[newi][newj];
              massiv[newi][newj]:=temp;
         end;
     writeln(\'\');
     for i:=0 to SIZE-1 do
         for j:=0 to SIZE-1 do
         begin
              write(\'   \',massiv[j]);
              if ((j+1) mod SIZE = 0) then writeln(\'\');
         end;
    readln;
end.

[КшЫуфксрук]

Stas, строго говоря, твой код не обеспечивает равновероятность перестановок. Ты просто идешь по массиву и на каждом шаге текущий элемент переставляешь с произвольным. Допустим, у нас массив 2*2, то есть 4 элемента. Всего может быть 24 (4!) перестановки. А твоя программа выдаст 256 комбинаций (4*4*4*4). 256 не делится на 24 без остатка, а значит, некоторые комбинации будут появляться чаще, чем остальные.

А тот алгоритм, что я привел, даст ровно 24 комбинации: на первом шаге мы вибираем один элемент из 4, на втором произвольный и трех оставшихся, затем один из двух. И достаточно легко показать, что все варианты равновероятны.

На самом деле, если число элеметов массива больше 3, то практически разница будет несущественна. Но зачем использовать плохой алгоритм, если есть хороший с такой же сложностью.

[ThE0ReTiC]

Как вариант:
Кнут. Том 2. стр 171. Алгоритм Р

[Yukko]

ThE0ReTiC rulezzzz!!!!

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

[ThE0ReTiC]

Yukko
Мда...
Ты вообще Кнута открывал?
Там разве идет упор на какой-то определенный язык?
Потом любой алгоритм есть сугубо математическая задача, которая не зависит от языка реализации.
Точнее зависит только от одного - математики.
Все остальное есть практическое развертывание алгоритма с использованием того или иного языка.

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

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

[off]Кстати, существуют сборники стандартных алгоритмов для работы с векторами, афинными преобразованиями и пр., что используется при программировании графики. в Инете полно [/off]

[Макс]

Курсовой пишу не себе а  четверым студентам с IQ = - 200.
И им нужно этот алгоритм понять

Кнута я пока не читал, поэтому воспользуюсь советом КшЫуфксрук-а

[КшЫуфксрук]

> Кнут. Том 2. стр 171. Алгоритм Р

Если это Algorithm P (Shuffling) (в электронной версии он на странице 139), то я именно его и описал. Просто запрограммировать его можно гораздо короче, чем рассказать словами, поэтому у Кнута он поместился всего на 4 строках.

[ThE0ReTiC]

Макс
Алгоритм Р (Перемешивание)
Пусть X1,X2,...,Xt - множество t чисел для перемешивания
P1 [Инициализация] Присвоить j <- t
P2 [Генерирование U] Генерировать случайное число U, равномерно распределенное между 0 b 1
P3 [Замена] Присвоить k <- floor(jU) + 1. (Сейчас k - случайное целое число между 1 и j ...) Заменим Xk <-> Xj
P4 [Уменьшение j] Уменьшить j на 1. Если j>1, возвратиться к шагу P2.

[ThE0ReTiC]

КшЫуфксрук
Ну в общем да.
See sources, как говорится