перемешивание стека

← →
race1 (2004-11-07 14:45) [0]

есть данные, хранящиеся в виде стека, т.е. каждый эл-т имеет указатель на пред. и след. эл-ты. как теперь можно эти эл-ты случайным образом переставить местами? т.е. была цепочка с данными 1->2->3->4, а сделать цепочку, например, такую: 3->1->2->4

← →
Anatoly Podgoretsky © (2004-11-07 15:03) [1]

Вообще то это не стек.

← →
palva © (2004-11-07 15:05) [2]

А двунаправленный список

← →
KilkennyCat © (2004-11-07 15:07) [3]

очень легко: записываем в него данные в нужном порядке.

← →
palva © (2004-11-07 15:10) [4]

А переставить можно следующим образом:
Берем первый элемент, порождаем целое случайное число s из диапазона 0..n и двигаем этот элемент вправо на s шагов. Потом берем следующий элемент, порождаем случайное число s из диапазона 0..n-1 и т.д. Если s = 0, то двигать, конечно, не надо.

← →
KilkennyCat © (2004-11-07 15:25) [5]

> palva © (07.11.04 15:10) [4]

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

← →
Anatoly Podgoretsky © (2004-11-07 15:31) [6]

Не проще, надо выполнять учебное задание.

← →
KilkennyCat © (2004-11-07 15:33) [7]

> Anatoly Podgoretsky © (07.11.04 15:31) [6]

тогда я - пас :) не люблю делать учебные задания.

← →
race1 (2004-11-07 17:08) [8]

это не учебное задание :) учебные задания я обычно сам делаю

> palva
можно доработать: создать доп. массив уже используемых значений, и генерировать не смещение, а индекс, кугда переместить текущий эл-т. при генерации числа для след. эл-та смотрим массив, если сгенерированное число уже занято - генерируем другое число

правда, в этом случае диапозон генерирования всегда будет n для каждого эл-та и может потребовать значительного времени пока сгенерятся все числа из диапозона 0..n :)

как этот момент доработать?

Вы правы в своих расчетах. Причем для последних чисел потребуется много обращений к датчику, прежде чем они будут выбраны. Доработать можно тем способом, что хранить все НЕВЫБРАННЫЕ числа одним куском в памяти и генерировать индекс числа внутри этого куска. При этом отрезок генерации будет все время уменьшаться, сначала от 1 до n, затем от 1 до n-1 и т. д. В Delphi есть даже специальная функция для выбора случайного целого числа из диапазона. Правда, реализовать это без большого числа перестановок - не знаю как.

Возможен такой алгоритм, который я недавно предлагал на другом форуме.
http://www.relib.com/forums/topic.asp?id=842829
Там бейсик, но не думаю, что трудно разобраться. Это перемешивание последовательности 1..n. Идея такая: Сначала массив содержит последовательность от 1 до n. Основной цикл проходит с последнего элемента до второго (i := n downto 2) На каждом шаге цикла i-й элемент меняется местами с одним из предыдущих. Кандидат на перестановку выбирается случайным образом из диапазона 1..i, причем если получилось i, то перестановку, естественно, не делаем. Получается ровно n-1 обращений к случайному датчику.

race1 (07.11.04 17:08) [8]
Тогда все просто

это тебе учебное задание, сделай сам

← →
race1 (2004-11-08 13:17) [11]

>palva
спасибо

вот и я тут ещё придумал - берём 1-ый эл-т нащего списка, генерим число i = 0..n, и делаем i шагов вправо. если список закончился, переходим в начало и продолжаем смещаться. если текущий эл-т уже добавлен в новый список, смещаемся вправо пока не найдём первый недобавленный эл-т. при нахождении нового эл-та добавляем его в конец нового списка. т.е. новый список формируется по-порядку, но эл-ты для него берутся случайным образом из исходного списка. в теории тоже достаточно быстрый метод

главное что не нужно промежуточных массивов - мы работаем со списком и формируем список "на лету"

> race1 (08.11.04 13:17) [11]

что-то меня тут смущает...

перемешивание стека Найти похожие ветки