Задача перетасовать случайным образом массив.
Дана функция возвращающая целое число от 1 до N, где N - длина массива.
Правильный ответ такой:
Стандартная перетасовка, делаем цикл: i уменьшается от N до 1. Меняем местами элемент массива с номером i и со случайным номером меньше либо равном i. Если случайное число получилось больше чем i, то повторно генерируем другое случайное число.

Вопрос: Почему нельзя было менять элемент с номером i на элемент с любым номером? Почему обязательно <=i ?

(0) Видимо, потому что вопрошающий запретил.

(1) +1

и еще чтобы не получить "совершенно случайно" в итоге тот же самый исходный массив

(1) Это из книги по алгоритмам, автор считает что так правильно. Да и книгу везде рекомендуют как хороший справочник.

(2) ИМХО вероятность такого одинакова в обоих случаях.

(3) "автор считает что так правильно", видимо он приводит какие-то аргументы? Ты хочешь, чтобы здесь их угадали?

(5) Аргументов как раз нет. Только ответ как правильно решать эту задачу. Решения на все задачи даются самые оптимальные. Но мне кажется несколько раз генерировать случайное число без веских причин не очень оптимально.

Потому что элементы с номером > i уже отсортированы в случайном порядке. Если мы их будем повторно тасовать, то можем, к примеру, получить не нормальное распределение (при условии, что наша функция возвращает случайные числа именно в нормальном распределении).

из какого диапазона генерится  случайное число? алгоритм выглядит бредовым, скорей всего ты неправильно переписал/понял

(7) >> то можем, к примеру, получить не нормальное распределение

А может и не можем, да? То есть не понятно на самом деле, нормальное будет распределение или нет.

Вот это и нужно выяснить.

+(8) скорей всего просто генерится от 1 до i, и никакой повторной генерации. И вероятность получить исходный массив - 1/N!, что не противоречит нормальному распределению

(8) от 1 до N

Трудно по другому понять слова что нужно генерировать случайное число повторно.

(9) Несмотря на то, что в соседней теме убедительно доказали, что ты тролль, к тому же дурак, отвечу: раз мы можем получить не нормальное распределение, значит мы не можем гарантировать, что полученное распределение нормально.

(10) Если бы генерировалось от 1 до i, то задачи бы не было. Массив бы тасовался стандартным способом.

Суть и сложность задачи в том, что дана функция которая возвращает целое число от 1 до N.

(12) Забаньте b_ru, он нарушает правила форума. Врет, троллит, загрязняет тему и обзывается.

(11) т.е. на последнем шаге будет повторно генериться число 1..N пока не выпадет единица? Наверное автор идиот, но я скорее соглашусь с (12) (в части оценки ТС)

в дополнение к (10): нормальность распределения можно попробовать доказать матндукцией, навскидку выглядит вполне реально.

(16) можешь доказать нормальность распределения для N=3?

(17) 3 варианта первого шага, 2 для второго. Убедись что в шести полученных вариантах получились разные перестановки. Бинго.

(0) Каждую перестановку можно записать, как набор
{a1, a2, a3,..aN}, гже a-i - различные числа от 1 до N, количество всех перестановок - это N!
Нумеруем все возможные перестановки от числами от 1 до N! и выбираем случайное число от 1 до N!, выбираем соответсвующую ей перестановку и сортируем в соответствии с ней наш массив.

Получается, что каждая перестановка равновероятна, значит массив отсортирован случайно.
Видимо в (0) реализация этого алгоритма

На javascript самая простая тасовка массива такая:
arr.sort(function(){return 0.5 - Math.random()});

(18) про то что они разные никто не сомневается.
Вопрос был в том, как доказать, что вероятность попадания любого элемента на любую позицию одинакова.

(19) да, в (0) реализация именно этого алгоритма. Вопрос в том, чем он хуже другого алгоритма о котором я спрашивал там же.

(20) по условию задачи нужно использовать функцию которую дали, а не Math.random().
Иначе бы и задачи не было, если бы разрешалось тупо Math.random() использовать.

Если взять массив из 8 элементов, то:
на первой позиции с вероятностью ~0.16 будет второй элемент,
и с вероятностью ~0.098  будет восьмой элемент.
Значит этот метод не нормальный, что и требовалось доказать.

(21) ммм... ты имеешь 6 исходов, которые тебе дал ГСЧ и которые ты считаешь равновероятными, им сопоставлены 6 перестановок. Что тебе ещё надо чтобы "доказать, что вероятность попадания любого элемента на любую позицию одинакова"?

Не тупи.

(24)
Шаг 1.
На восьмое место попадает любой из 8 элементов с вероятностью 1/8. И он никогда больше оттуда не уйдет.
Шаг 2.
На седьмое место с вероятностью 1/7 попадет один из оставшихся. Но надо умножить на 7/8 что на предыдущем шаге он не ушел на восьмое. Итого 1/7*7/8 = 1/8.
Шаг 3.
На шестое попадет один из оставшихся с вероятностью 1/6. Учтем условие, что вероятность что именно он не попал ранее ни на восьмое ни на седьмое место. 1 - 1/8 - 1/8 = 6/8
Имеем 1/6*6/8 = 1/8
и т.д.

Что еще надо?

(23)
Над задачами пусть школота размышляет и решает. Я практик. И вообще-то раз задача дается на javascript, то Math.Random и Array.sort - неотъемлемые части языка, поэтому как можно запретить ими пользоваться? Просто говоришь - "мне удалось найти более простое решение задачи, не используя данную вами функцию".

(27) Значит ты не смог решить поставленную задачу. Ты придумал другую более простую задачу и решил ее.

(28) Не нужно высасывать задачи из пальца и гордиться  потом. Это не умно.

(26) >> И он никогда больше оттуда не уйдет.

тут ты ошибся

(25) Тут ты ошибся. 6 исходов достигаются 9-ю вариантами перестановок. Равновероятность нужно доказать. Хотя я уже вижу что вероятность не одинаковая.

С задачкой разобрался, темку можно закрыть.

Можете продолжить разбираться сами

(28)
Еще раз говорю - я не школьник, я решаю не задачи, а проблемы. И как очень ленивый человек, стараюсь решить их оптимальным способом.

(30) с чего бы? приведи контрпример.

вообще-то сабж рожден из задач обратимого шифрования, там обычно решают ее методом задания эталонного массива

1. делают соответствие например 512 строк
2. первое поле нумеруют от 1 до 512 по порядку
3. второе поле нумеруют от 1 до XXXXh случайными числами
4. сортируют соответствие по полю индексу 2+1
5. далее берут исходные данные размером 512 байт и перемешивают по соответствию, и так пока не закончатся данные

банально при массиве в 1 гиг, замучиешся получать ранд на каждый байт :)))

(33) генератор случайных чисел может выдать его номер в любой момент. ты перепутал оригинальное решение задачи с тем которое мы обсуждаем, которое оказалось не правильным. (31) поправка. не 9 конечно, а 3^3 = 27. на 6 все равно не делится.

При N=3 после перестановки на первом месте могут оказаться элементы массива с такой вероятностью:
первый - 9/27
второй - 10/27
третий - 8/27

При любом N на первом месте с большей вероятностью оказывается второй элемент, и с наименьшей последний.

Ускорил первоначальный алгоритм из книжки более чем в 10 раз если тестировать на массиве из 1'000'000 элементов!

(38) Хочешь отойти от 1С? Куда?

(39) Не хочу. 1с - лучшая. Но у меня есть еще хобби - программирование.

(0)А как рандом числа, которое меньше либо равно i может оказаться больше чем i?

+(41)решение криво написано. Отсюда и непонятки.

+(42)Вот алгоритм http://space-base.ru/library/?book=25
40 постов про какое-то распределение говорили. Что разбирали? Не важно главное разбирать:)

(38)
И как, побил (20)?

мне когда надо было равномерно рассортировать массив просто скидывал в другой массив случайный элемент из остатка от первого массива
типа 1 й- случайный из 40
2 й - случайный из 39
3 й - случайный из 38
....
тут вопрос в точном распределении или в скорости сортировки?

(45) так у тебя то же самое и получается...

(46) почти
у меня каждое число делает только 1 перестановку

+ (46) Только массива два - расход памяти ДВОЙНОЙ!

(47) И в (0) - перестановок каждого элемента - ОДНА!

(47) там - тоже. Представь, что "отсортированная часть массива" - это второй массив...
(48) если массив динамический - то расход памяти такой же

(50) Если динамический - СТО-кратный расход процессорного времени!

Одного не понимаю... Почему второй элемент (по условию решения задачи) нужно _обязательно_ поставить в первую ячейку...? И цикл должен идти от N до 2-х. 1-ый элемент уже некуда переставлять ведь.
Чо то ТС темнит...

*(52) Одного не понимаю... Почему ДЛЯ второГО элементА (по условию решения задачи) нужно _обязательно_ УБЕДИТЬСЯ - поставить в первую ячейку ИЛИ НЕТ...? (Можно же просто после цикла на чёт/нечет проветрить полученный от рандома индекс)
И цикл должен идти от N до 2-х. 1-ый элемент уже некуда переставлять ведь.
Чо то ТС темнит...

(51) ага. но алгоритм от этого принципиально не меняется...

(54) Принципиально меняется! в (6) на то уточнение даётся "Решения на все задачи даются самые оптимальные"

Ибо даже одна лишняя переменная - это минус балл.

Как в задаче со списком: доказать, что список имеет зацикленность используя минимум переменных. Сколько необходимо переменных?

Правильный ответ в (7)

(52) Потому что могло такое получится, что последний элемент остался не затронутым

(56) см (53)

(36) Рассказывай, как считал. Вместе ошибку найдём.

(38) Показывай. Вместе посмеёмся.

(57) Потому что, если N - нечетное, то вероятность получения четного числа не равна вероятности получения нечетного)

(58) Сенькс! )) Хм...

(43) >> Вот алгоритм http://space-base.ru/library/?book=25
Алгоритм был написан в (0)
Мы тут разбирали вопрос почему этот алгоритм такой не красивый.

(44) В (20) решение для другой задачи, их нельзя сравнивать.

(45) >> тут вопрос в точном распределении или в скорости сортировки?
точное распределение должно быть обязательно, на все 100%, иначе не возможно.
Скорость сортировки должна быть оптимальная. Использование памяти тоже. Поэтому вариант со вторым массивом не годится. Ведь элементов массива может быть миллиарды.

(53) Можно сделать цикл и от N до 2. Или от 1 до N-1. Я как бы не против.

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

Похоже ты просто троллишь, потому что видно что в вопросе не разобрался, а всем пишешь что они не правы никак это не аргументируя.

>> Потому что, если N - нечетное, то вероятность получения четного числа не равна вероятности получения нечетного)
С этой проблемой можно легко справиться, я придумал один трюк. Подумай сам немного.

bolobol правильно написал, на последних элементах можно сильно ускориться проверяя на чет/нечет, деление на 3, на 4, и т.д.

(55) >> доказать, что список имеет зацикленность используя минимум переменных. Сколько необходимо переменных?

Две переменные, минимум, ИМХО. Не массивы конечно, а ссылки на элементы списка.

Стандартно берем дополнительный массив и заполняем от 0 до Количество -1.

Рандомом берем 2 индекса от 0- N-1 (если генерируют 2 одинаковых числа повторяем.)

Берем значения по индексу из дополнительного массива. Меняем местами. Удаляем из дополнительного массива выбранные индексы (от большего к меньшему)

(66) Это ты на какое сообщение ответил?

(67) на 0. Или тебе алгоритм полностью написать,
N это количество в дополнительном массиве

(68) Тогда вообще не понятно что ты хотел этим сказать. Какой еще дополнительный массив? Ты точно правильно понял вопрос?

(64) Плохо видно.
Вероятность - 1/3.

Рассмотрим массив из трёх элементов: 123. Начнём тасовать. Всего два шага: перестановка первого элемента и перестановка второго.
Результат на первом шаге|Результат на втором шаге
123|123
123|213
132|132
132|312
321|321
321|231
Вероятность попадания последнего элемента на первое место равна 1/3. По-моему, очевидно, что вероятность этих исходов одинакова.
Но ты писал
>>Хотя я уже вижу что вероятность не одинаковая
И как же ты это увидел?

>>Потому что, если N - нечетное, то вероятность получения четного числа не равна вероятности получения нечетного)
>>>>С этой проблемой можно легко справиться, я придумал один трюк. Подумай сам немного.
Для любого N? Я не смог. Колись.

(69) Тут по идее он должен был кинуть ссылку на мсдн и сказать: вот читайте, там все есть )))

(70) Если по-твоему перестановки всего две, то количество путей равно:
Первая перестановка - 3 варианта
Вторая перестановка - 3 варианта
Итого 3 * 3 = 9
А у тебя всего 6 нарисовано.

(72) Что?
Последний элемент может попасть на три позиции:
123
132
321
Второй на две. Итого шесть.

>>Потому что, если N - нечетное, то вероятность получения четного числа не равна вероятности получения нечетного)
>>>>С этой проблемой можно легко справиться, я придумал один трюк. Подумай сам немного.
Для любого N? Я не смог. Колись.

Какие три варианта при второй перестановке? Второй элемент может попасть либо на первое место, либо на второе. И это по условию задачи.

(73) Что? С чего ты взял что второй только на две?

(74) Почитай внимательно вопрос в (0).

(75) Цитирую (0):
>>Вопрос: Почему нельзя было менять элемент с номером i на элемент с любым номером? Почему обязательно <=i ?

Т.е. если i=2, то второй элемент может попасть на позицию <=i - первую или вторую.

(77) Если  <=i, то будет все как по книжке, этот вариант 100% правильный и здесь его не обсуждаем.

Обсуждаем алгоритм при котором можно менять элемент с номером i на элемент с любым номером, о том и вопрос в (0) и вся эта тема.

(73) >>Потому что, если N - нечетное, то вероятность получения четного числа не равна вероятности получения нечетного)

Если ГСЧ выдал число равное N, то вызываем ГСЧ повторно.

(69)


Угу

ДопМассив=Ноавый Массив();

Для сч=0 по ОригМассив.Количество()-1 Цикл
ДопМассив[сч]=сч;
КонецЦикла

Пока ДопМассив.Количество()>1 Цикл
N=ОригМассив.ВГраница();


Поз1=СлучайноеЧисло(0,N);
Поз2=СлучайноеЧисло(0,N);
// Если Поз1=Поз2 повторить
Переставить(ОригМассив,ДопМассив[Поз1],ДопМассив[Поз2]);

Если Поз1 > Поз2 Тогда
ДопМассив.Удалить(поз1);
ДопМассив.Удалить(поз2);
Иначе
ДопМассив.Удалить(поз2);
ДопМассив.Удалить(поз1);

Кол=ДопМассив.Количество();


КонецЕсли;



КонецЦикла

КонецЦикла

Жалко нет кнопки удалить. Писал с листа

ДопМассив=Новый Массив();

Для сч=0 по ОригМассив.Количество()-1 Цикл
ДопМассив[сч]=сч;
КонецЦикла

Пока ДопМассив.Количество()>1 Цикл
N=ДопМассив.ВГраница();


Поз1=СлучайноеЧисло(0,N);
Поз2=СлучайноеЧисло(0,N);
// Если Поз1=Поз2 повторить
Переставить(ОригМассив,ДопМассив[Поз1],ДопМассив[Поз2]);

Если Поз1 > Поз2 Тогда
ДопМассив.Удалить(поз1);
ДопМассив.Удалить(поз2);
Иначе
ДопМассив.Удалить(поз2);
ДопМассив.Удалить(поз1);

КонецЕсли;

КонецЦикла

То есть мы берем значения индексов из начений массива ДопМассив. В ДопМассиве остаются значения индексов ОригМассива которые не подвергались перестановке

(82) Спасибо за старания! Хорошо написал, молодец.