Программирование > Теория, алгоритмы и стандарты

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

(1/2) > >>

Макс:
Задача
Есть массив(двухмерный). Нужно переставить в нем элементы случайным образом.
Подскажите алгоритм плиз.
(реализация будет на 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!!!!

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

Навигация

[0] Главная страница сообщений

[#] Следующая страница