Версия для печати темы Нажмите сюда для просмотра этой темы в оригинальном формате

Форум программистов > Алгоритмы > Перемешивание

Автор: Сый 29.3.2006, 22:49

Как можно перемешать случайным образом элементы некоторого ряда (массива)?

Автор: esperant0 29.3.2006, 23:27

Идеально так: Берешь первый элемент и меняешь его с любым случайно выбранным элементом от первого до последнего берешь 2-йй элемент и меняешь его с любым случайно выбранным элементом от 2-го до последнего. и так до конца. Все. Вот неправильно решение: Берешь первый элемент и меняешь его с любым случайно выбранным элементом от 1-го до последнего берешь 2-йй элемент и меняешь его с любым случайно выбранным элементом от 1-го до последнего. и так до конца. удачи друг

Автор: maxim1000 30.3.2006, 00:16

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

Автор: esperant0 30.3.2006, 00:29

Цитата(maxim1000 @ 30.3.2006, 00:16) ну, если имеется в виду, чтобы любая комбинация имела одинаковую вероятность, то можно такой алгоритм: 1. на первое место ставим элемент со случайным номером от 1 до N 2. (для удобства) перенумеровываем все остальные элементы от 1 до N-1 (чтобы не было дырки, которая останется от предыдущего элемента) 3. на второе место ставим элемент со случайным номером от1 до N-1 ... ну или тот же алгоритм только с другой стороны: 1. первый элемент ставим на случайное место (от 1 до N) 2. второй на случайное место из оставшихся незанятых (от 1 до N-1) ... первый алгоритм имеет квадратичную сложность второй алгоритм надо уточнить.

Автор: maxim1000 30.3.2006, 02:02

Цитата(esperant0 @ 29.3.2006, 23:29 ) второй алгоритм надо уточнить тоже и там, и там квадрат возникает из-за необходимости каким-то образом пропускать использованные элементы/ячейки просто во втором случае вместо перенумерования надо будет проходить по массиву, чтобы пропустить занятые ячейки, не увеличивая индекса... а с заменами, действительно быстрее получается

Автор: Сый 30.3.2006, 17:55

Решил реализовать "неправильное решение", но переделать в "правильное" при помощи сложения и вычитания труда не составит. А переименовывать элементы, думаю, что будет сложновато. Код ОТДЕЛ Мешалка+; ИСПОЛЬЗУЕТ   Матем ИЗ "...\Отделы\Числа\",   Вывод ИЗ "...\Отделы\Обмен\"; ПЕР   Ряд: РЯД 3 ИЗ ЦЕЛ; ЗАДАЧА Перемешать(); ПЕР   ч, б, с: ЦЕЛ; УКАЗ   ОТ ч := 0 ДО РАЗМЕР(Ряд)-1 ВЫП     с := УЗК(ВШИРЦЕЛ(Матем.случ()*(РАЗМЕР(Ряд)-1)));     б := Ряд[с]; Ряд[с] := Ряд[ч]; Ряд[ч] := б   КОН; КОН Перемешать; УКАЗ   Ряд[0] := 1; Ряд[1] := 2; Ряд[2] := 3;   Вывод.ЧЦел("%d, %d, %d^", Ряд[0], Ряд[1], Ряд[2], 0);   Перемешать;   Вывод.ЧЦел("%d, %d, %d", Ряд[0], Ряд[1], Ряд[2], 0) КОН Мешалка. Результат работы: D:\Глагол\Приложения\Свои>Мешалка 1, 2, 3 2, 3, 1 D:\Глагол\Приложения\Свои>Мешалка 1, 2, 3 2, 1, 3 D:\Глагол\Приложения\Свои>Мешалка 1, 2, 3 1, 3, 2

Автор: esperant0 30.3.2006, 21:32

Цитата(Сый @ 30.3.2006, 17:55) Решил реализовать "неправильное решение", но переделать в "правильное" при помощи сложения и вычитания труда не составит. А переименовывать элементы, думаю, что будет сложновато. Код ОТДЕЛ Мешалка+; ИСПОЛЬЗУЕТ   Матем ИЗ "...\Отделы\Числа\",   Вывод ИЗ "...\Отделы\Обмен\"; ПЕР   Ряд: РЯД 3 ИЗ ЦЕЛ; ЗАДАЧА Перемешать(); ПЕР   ч, б, с: ЦЕЛ; УКАЗ   ОТ ч := 0 ДО РАЗМЕР(Ряд)-1 ВЫП     с := УЗК(ВШИРЦЕЛ(Матем.случ()*(РАЗМЕР(Ряд)-1)));     б := Ряд[с]; Ряд[с] := Ряд[ч]; Ряд[ч] := б   КОН; КОН Перемешать; УКАЗ   Ряд[0] := 1; Ряд[1] := 2; Ряд[2] := 3;   Вывод.ЧЦел("%d, %d, %d^", Ряд[0], Ряд[1], Ряд[2], 0);   Перемешать;   Вывод.ЧЦел("%d, %d, %d", Ряд[0], Ряд[1], Ряд[2], 0) КОН Мешалка. Результат работы: D:\Глагол\Приложения\Свои>Мешалка 1, 2, 3 2, 3, 1 D:\Глагол\Приложения\Свои>Мешалка 1, 2, 3 2, 1, 3 D:\Глагол\Приложения\Свои>Мешалка 1, 2, 3 1, 3, 2 Я не уверен, что вы правильно понимаете почему неправильно, неправильное решение.

Автор: Сый 30.3.2006, 21:58

Ну так объясните, в чём, по-вашему, заключается его "неправильность"...

Автор: maxim1000 30.3.2006, 22:07

Цитата(esperant0 @ 30.3.2006, 20:32 ) Я не уверен, что вы правильно понимаете почему неправильно, неправильное решение. я тут подумал... не знаю, как Сый, а я действительно не понимаю, почему он неправильный... на первый взгляд создается ощущение, что и в этом случае позиция каждого элемента тоже будет распределена равномерно...

Автор: maxim1000 30.3.2006, 22:53

Хы-хы... оказалось, вполне достаточно покрутить массив из трех элементов, чтобы увидеть доказательство неправильности "неправильного алгоритма" количество всевозможных последовательностей обменов n^n и у каждого одинаковая вероятность каждая последовательность обменов ведет к какому-то порядку следования элементов в массиве (перестановке) таких перестановок n! чтобы каждая перестановка имела одинаковую вероятность, нужно чтобы все возможные последовательности равномерно распределились по перестановкам а вот этого-то как разбыть и не может, т.к. n^n не делится на n! (n=1 или 2 не в счет) хотя лично для меня это не объясняет так сказать физику процесса - почему и на каком этапе вероятности получаются разными

Автор: esperant0 31.3.2006, 00:20

Цитата(maxim1000 @ 30.3.2006, 22:53) Хы-хы... оказалось, вполне достаточно покрутить массив из трех элементов, чтобы увидеть доказательство неправильности "неправильного алгоритма" количество всевозможных последовательностей обменов n^n и у каждого одинаковая вероятность каждая последовательность обменов ведет к какому-то порядку следования элементов в массиве (перестановке) таких перестановок n! чтобы каждая перестановка имела одинаковую вероятность, нужно чтобы все возможные последовательности равномерно распределились по перестановкам а вот этого-то как разбыть и не может, т.к. n^n не делится на n! (n=1 или 2 не в счет) хотя лично для меня это не объясняет так сказать физику процесса - почему и на каком этапе вероятности получаются разными Интуиция мне тоже не ясна. Но ваше доказательство достаточно.

Автор: nostromo 7.4.2006, 16:33

maxim1000 Цитата а вот этого-то как разбыть и не может, т.к. n^n не делится на n! А вы не обратили внимание на то, что таким рассуждением легко опровергается также и "правильный" алгоритм? ($n (n+1) /2$ операций)

Автор: esperant0 7.4.2006, 20:23

Цитата(nostromo @ 7.4.2006, 16:33) maxim1000 Цитата а вот этого-то как разбыть и не может, т.к. n^n не делится на n! А вы не обратили внимание на то, что таким рассуждением легко опровергается также и "правильный" алгоритм? ($n (n+1) /2$ операций) Вы не обратили внимание, что считается не количество операций, а количество всевозможных вариантов которое можно получить по завершению работы программы

Автор: nostromo 8.4.2006, 11:11

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

Автор: maxim1000 8.4.2006, 11:54

Цитата(nostromo @ 8.4.2006, 10:11 ) Связь между вероятностями выбора очередного элемента для обмена на конкретном шаге алгоритма и вероятностью появления той или иной перестановки из n элементов по завершению работы алгоритма неочевидна. 1. вероятность каждой конкретной последовательности обменов равна 1/n^n 2. вероятность каждой конечной перестановки равна сумме вероятностей тех последовательностей обменов, которые к ней приводят 3. эта вероятность равна (должна быть равна) 1/n! 4. т.к. вероятности всех последовательностей обменов одинаковая, то 1/n!=k*1/n^n, где k - количество разных последовательностей обменов, приводящих к данной перестановке (целое)...

Автор: Заппер 8.4.2006, 16:49

Мне кажется, можно предложить решение линейной сложности для этой задачи. Вот оно: массив[1..N] ... цикл по i от 1 до N массив[i] = массив[случайное(N-i)+i] .., где Цитата случайное(x) - функция, выдающее случайное целое число от 1 до x-1. Отсутствие повторений чисел обеспечивает тот факт, что при каждом выборе мы сужаем рамки на 1, исключая уже выбранное на предыдущем шаге число.

Автор: esperant0 8.4.2006, 19:36

Цитата(Заппер @ 8.4.2006, 16:49) Мне кажется, можно предложить решение линейной сложности для этой задачи. Вот оно:     массив[1..N]     ...     цикл по i от 1 до N         массив[i] = массив[случайное(N-i)+i]     .., где Цитата случайное(x) - функция, выдающее случайное целое число от 1 до x-1. Отсутствие повторений чисел обеспечивает тот факт, что при каждом выборе мы сужаем рамки на 1, исключая уже выбранное на предыдущем шаге число. Линейные решения уже были приведены тут. А вот ваше решение, не мешало бы обосновать. т.е доказать правильность

Автор: nostromo 9.4.2006, 15:01

Цитата(maxim1000 @ 8.4.2006, 11:54) 1. вероятность каждой конкретной последовательности обменов равна 1/n^n 2. вероятность каждой конечной перестановки равна сумме вероятностей тех последовательностей обменов, которые к ней приводят 3. эта вероятность равна (должна быть равна) 1/n! 4. т.к. вероятности всех последовательностей обменов одинаковая, то 1/n!=k*1/n^n, где k - количество разных последовательностей обменов, приводящих к данной перестановке (целое)... Согласен.

Powered by Invision Power Board (http://www.invisionboard.com)
© Invision Power Services (http://www.invisionpower.com)