Comments 21
С описанием пока не очень понятно:
т.е. для n = 7 имеем 7 битов, сгенерированных случайно, допустим: 0101101,
делим. (массивы изначально пустые?! Это был риторический вопрос), получаем P0=[0,0,0], P1[1,1,1,1]
@ все элементы, которым сопоставлены нули заносятся в массив P0, остальные в массив P1@
Перемешиваем… и тут вопрос: что перемешиваем каждый массив в отдельности?
Но там и так все значения одинаковые. Или мы перемешиваем индексы?
т.е. для n = 7 имеем 7 битов, сгенерированных случайно, допустим: 0101101,
делим. (массивы изначально пустые?! Это был риторический вопрос), получаем P0=[0,0,0], P1[1,1,1,1]
@ все элементы, которым сопоставлены нули заносятся в массив P0, остальные в массив P1@
Перемешиваем… и тут вопрос: что перемешиваем каждый массив в отдельности?
Но там и так все значения одинаковые. Или мы перемешиваем индексы?
Вы немного не поняли. Сопоставить элементам массива биты, не означает записать их в этот массив. Массив Р содержит элементы, которые нужно переставить. В вашем случае будет так:
Тогда массивы Р0 и Р1:
Нужен ли в статье модельный пример? Мне казалось все достаточно понятным.
P=[1,2,3,4,5,6,7];
g=[0,1,0,1,1,0,1];
Тогда массивы Р0 и Р1:
P0=[1,3,6];
P1=[2,4,5,7];
Нужен ли в статье модельный пример? Мне казалось все достаточно понятным.
Кажется надо явно написать в начале, что мы учитываем возможность разной вероятности 0 и 1. Потому что если она одинаковая, то можно, например, просто сгенерировать случайное число от 0 до n!..
С ростом n для вам будут нужны все более длинные числа с равномерным распределением в заданном диапазоне…
n=256 около 1700 бит
n=512 около 3900 бит
n=1024 около 8800 бит
n=2048 около 19600 бит
В каждом случае вам потребуется гарантировать (доказывать) независимость и равномерность распределения. этих чисел.
И если мне не изменяет память, чтобы номер преобразовать в подстановку вам потребуется делить длинные числа и находить остатки от деления длинных чисел.
А так, наверное, проблем больше не будет…
n=256 около 1700 бит
n=512 около 3900 бит
n=1024 около 8800 бит
n=2048 около 19600 бит
В каждом случае вам потребуется гарантировать (доказывать) независимость и равномерность распределения. этих чисел.
И если мне не изменяет память, чтобы номер преобразовать в подстановку вам потребуется делить длинные числа и находить остатки от деления длинных чисел.
А так, наверное, проблем больше не будет…
Изучая код функции randperm в Matlab, я обнаружил следующий алгоритм.
1) Генерируем равномерно распределенные случайные числа (например, в диапазоне 0..1) для каждого элемента последовательности, для которой мы хотим получить случайную перестановку.
2) Сортируем полученные случайные числа по неубыванию, запоминая при этом индексы оригинальной последовательности случайных чисел. В результате получается последовательность индексов.
3) Размещаем элементы исходной последовательности в соответствии с индексами, полученными на шаге 2).
В матлаб-коде это выглядит так:
Преимущество метода — заранее известно требуемое кол-во случайных чисел. В зависимости от используемого метода сортировки заранее известна сложность (максимальная или средняя, в случае qsort)
Если требуется получить перестановку не произвольных элементов, а последовательности натуральных чисел длиной n — то можно сразу возвращать массив индексов.
Вопросы:
1) Для описанного выше метода, гарантируется ли равномерное распределение перестановок?
2) Если оно гарантируется — какой метод эффективнее, описанный выше или приведенный в статье?
1) Генерируем равномерно распределенные случайные числа (например, в диапазоне 0..1) для каждого элемента последовательности, для которой мы хотим получить случайную перестановку.
2) Сортируем полученные случайные числа по неубыванию, запоминая при этом индексы оригинальной последовательности случайных чисел. В результате получается последовательность индексов.
3) Размещаем элементы исходной последовательности в соответствии с индексами, полученными на шаге 2).
В матлаб-коде это выглядит так:
function b = randperm(a)
% The function accepts a vector a and returns its random permutation as b
x = rand(size(a)); % Generate a random number vector with the same size as a
[xs,i] = sort(x); % Sort the random numbers, store indices such that xs = x(i), see help sort
b = a(i); % Use the same indices to permute the original vector a
Преимущество метода — заранее известно требуемое кол-во случайных чисел. В зависимости от используемого метода сортировки заранее известна сложность (максимальная или средняя, в случае qsort)
Если требуется получить перестановку не произвольных элементов, а последовательности натуральных чисел длиной n — то можно сразу возвращать массив индексов.
Вопросы:
1) Для описанного выше метода, гарантируется ли равномерное распределение перестановок?
2) Если оно гарантируется — какой метод эффективнее, описанный выше или приведенный в статье?
1) да, гарантируется
2) ваш метод существенно сложнее (требует генерации чисел на отрезке)
Если мы можем использовать достаточно сильные генераторы (например, генерировать равномерно числа на отрезке) — то мы можем генерировать и равномерно числа из 1,2,...,n — и использовать метод Кнута.
2) ваш метод существенно сложнее (требует генерации чисел на отрезке)
Если мы можем использовать достаточно сильные генераторы (например, генерировать равномерно числа на отрезке) — то мы можем генерировать и равномерно числа из 1,2,...,n — и использовать метод Кнута.
1) Генерируем равномерно распределенные случайные числа (например, в диапазоне 0..1) для каждого элемента последовательности, для которой мы хотим получить случайную перестановку.
В вашем случае, числами 0 и 1 не обойдешся. Rand должен давать случайные числа из диапазона шириной существенно большей числа элементов перестановки.
Предложенный метод, сильно напоминает тасование Кнута (вариант с сортировкой). У оригинального алгоритма Кнута (Фишера–Йетса) асимптотика O(n).
Асимптотическая оценка скорости сортировки в лучшем случае равна O(n log n), что несравнимо с оценкой O(n) скорости работы оригинального тасования Кнута. Cортирующий метод дает несмещенные перестановки, но он менее чувствителен к возможным проблемам генератора случайных чисел. Однако следует уделить особое внимание генерации случайных чисел, чтобы избежать повторения, поскольку алгоритм с сортировкой, в общем случае, не сортирует элементы случайно.
1. Если rand генерирует равномерно распределенные числа, то перестановки, полученные им, также будут иметь равномерное распределение. Думаю, если сделать проверку аналогичную той, что делал я в статье, то перестановки сгенерируются с равномерным распределением.
Про гарантированное распределение, тут все определяется качеством чисел, которые выдает rand.
2. Возможно, предложенный Санделиусом алгоритм и не самый быстрый, но не такой требовательный к качеству входной последовательности (смотрите в табличке третью строку там вероятность появления нулей 0,9, но перестановки все равно получаются равномерно распределенными).
Я буду читать комментарии
В примере на С++ можно было бы не использовать дополнительную память.
Если я правильно понимаю, функция выдаёт независимые биты, и потому не важно, в каком порядке мы их спрашиваем. Можно по аналогии с qSort идти от начала, запрашивая рандомные биты, пока не наткнёмся на 1, а потом двигаться с конца, пока не получим 0.
Если я правильно понимаю, функция выдаёт независимые биты, и потому не важно, в каком порядке мы их спрашиваем. Можно по аналогии с qSort идти от начала, запрашивая рандомные биты, пока не наткнёмся на 1, а потом двигаться с конца, пока не получим 0.
Правильно я понимаю, что алгоритм не гарантирует остановку?
Допустим, ГСЧ заклинило, и он начал выдавать «совершенно случайно» только нули или только единицы.
Тогда рекурсивный алгоритм будет жрать время и стек до посинения.
Или, допустим, ГСЧ решил выдавать такую последовательность:
1 ноль, n-1 единиц
1 единица, n-2 нулей
1 ноль, n-3 единиц…
в среднем-то нулей и единиц поровну… Ну да, в белом шуме попалась «любимая мелодия».
А время работы из линейного или логлинейного превратилось в квадратичное!
Допустим, ГСЧ заклинило, и он начал выдавать «совершенно случайно» только нули или только единицы.
Тогда рекурсивный алгоритм будет жрать время и стек до посинения.
Или, допустим, ГСЧ решил выдавать такую последовательность:
1 ноль, n-1 единиц
1 единица, n-2 нулей
1 ноль, n-3 единиц…
в среднем-то нулей и единиц поровну… Ну да, в белом шуме попалась «любимая мелодия».
А время работы из линейного или логлинейного превратилось в квадратичное!
Ну, если PRG зажилил энтропию и не отдает — то тут уж ничего сделать нельзя (либо выдать фиксированный ответ, либо зависнуть).
Насчёт равномерности — требуются доказательства!
Ибо разным последовательностям случайных бит соответствуют одинаковые перестановки.
Например, (для n=5)
00000, xyz… = 11111, xyz… = xyz… — потому что, как я уже сказал выше, все-нули и все-единицы — это просто пропуск одного шага
01111, 0111, xyz… = 00111, 01, xyz… — два раза отщепили первый элемент и перетасовали хвост, — это отщепили два элемента, сохранили их порядок, перетасовали хвост…
Ибо разным последовательностям случайных бит соответствуют одинаковые перестановки.
Например, (для n=5)
00000, xyz… = 11111, xyz… = xyz… — потому что, как я уже сказал выше, все-нули и все-единицы — это просто пропуск одного шага
01111, 0111, xyz… = 00111, 01, xyz… — два раза отщепили первый элемент и перетасовали хвост, — это отщепили два элемента, сохранили их порядок, перетасовали хвост…
Sign up to leave a comment.
Метод Санделиуса для получения случайных перестановок