Forum Webscript.Ru
Программирование => Теория, алгоритмы и стандарты => Тема начата: Макс от 23 Января 2003, 00:57:18
-
Задача
Есть массив(двухмерный). Нужно переставить в нем элементы случайным образом.
Подскажите алгоритм плиз.
(реализация будет на pascal/delphi)
PS
желательно попроще (можно даже в ущерб случайности - это для курсовой надо :))
-
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, то практически разница будет несущественна. Но зачем использовать плохой алгоритм, если есть хороший с такой же сложностью.
-
Как вариант:
Кнут. Том 2. стр 171. Алгоритм Р
-
ThE0ReTiC rulezzzz!!!!
Для сугубо математических задач есть сборники алгоритмов их реализации без ориентации на конкретный язык программирования. Либо читай учебники и либо пиши такие алгоритмы сам, я с таким столкнулся, когда писал трехмерный движок, пришлось векторную алгебру поворошить...
-
Yukko
Мда...
Ты вообще Кнута открывал?
Там разве идет упор на какой-то определенный язык?
Потом любой алгоритм есть сугубо математическая задача, которая не зависит от языка реализации.
Точнее зависит только от одного - математики.
Все остальное есть практическое развертывание алгоритма с использованием того или иного языка.
Я потому Кнута и порекоммендовал, что там дается абстрактный (вураженный в математических выражениях) алгоритм перемешивания массива..
Так что я рад, конечно, за тебя, что тебе пришлось изучить векторную алгебру (которую вообще-то на первом курсе любого нормального вуза дают), однако писать подобные алгоритмы смысла не вижу, так как все уже придумано за нас.
[off]Кстати, существуют сборники стандартных алгоритмов для работы с векторами, афинными преобразованиями и пр., что используется при программировании графики. в Инете полно :)[/off]
-
Курсовой пишу не себе а четверым студентам с IQ = - 200.
И им нужно этот алгоритм понять :)
Кнута я пока не читал, поэтому воспользуюсь советом КшЫуфксрук-а
-
> Кнут. Том 2. стр 171. Алгоритм Р
Если это Algorithm P (Shuffling) (в электронной версии он на странице 139), то я именно его и описал. Просто запрограммировать его можно гораздо короче, чем рассказать словами, поэтому у Кнута он поместился всего на 4 строках.
-
Макс
Алгоритм Р (Перемешивание)
Пусть 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.
-
КшЫуфксрук
Ну в общем да.
See sources, как говорится :)