Генерирование отсортированных случайных чисел без сортировки? На)

Ответ 1

Итак, вы спрашиваете, будут ли распределенные числа таким образом распределены равномерно.

Вы создаете серию:

y _j= & sum; _{я = 0} ^j (x _i/A)

где A - сумма всех x _i. x _i - список (положительных) дельт.

Это можно сделать, если x _i экспоненциально распределены (с любым фиксированным средним). Итак, если x _i равномерно распределены, результирующий y _j не будет равномерно распределен.

Сказав это, довольно легко создать экспоненциальные значения x _i.

Одним из примеров может быть:

sum := 0
for I = 1 to N do:
    X[I] = sum = sum - ln(RAND)
sum = sum - ln(RAND)
for I = 1 to N do:
    X[I] = X[I]/sum

и ваши случайные числа будут отсортированы в диапазоне [0, 1).

Ссылка: Генерация отсортированных списков случайных чисел. В документе есть и другие (более быстрые) алгоритмы.

Конечно, это порождает числа с плавающей запятой. Для равномерного распределения целых чисел вы можете заменить sum выше на sum/RANGE на последнем шаге (т.е. R.H.S станет X[I]*RANGE/sum, а затем округлите числа до ближайшего целого числа).

Ответ 2

A равномерное распределение имеет верхнюю и нижнюю границы. Если вы используете свой предложенный метод, и ваши дельта выбираются достаточно большими, чтобы вы столкнулись с верхней границей, прежде чем вы сгенерировали все свои номера, что бы ваш алгоритм сделал дальше?

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

Ответ 3

Если вы принимаете числовое число от 1 до 1000, и вы должны использовать 100 из этих чисел, дельта должна быть как минимум 10, иначе вы не сможете достичь отметки 1000. Как насчет некоторых работающих, чтобы продемонстрировать это в действии...

Вероятность любого заданного числа в равномерно распределенном случайном выборе составляет 100/1000, например. 1/10 - никакого шока нет, возьмите это в качестве основы.

Предполагая, что вы начинаете использовать дельта и что дельта составляет всего 10.

Шансы получить номер 1 - 1/10 - кажется прекрасным. Шансы получить номер 2 - 1/10 + (1/10 * 1/10) (потому что вы можете набрать 2 дельта 1 подряд или просто нажать 2 в качестве первой дельта.) Шансы получить номер 3: 1/10 + (1/10 * 1/10 * 1/10) + (1/10 * 1/10) + (1/10 * 1/10)

Первый случай был дельта 3, второй - 3 дельта 1 строки, третий - дельта 1, затем 2, а четвертый - дельта 2, за которой следует 1.

Для ввода пальцев мы не будем создавать комбинации, которые достигают 5.

Сразу же первые несколько чисел имеют больший процентный шанс, чем прямой случайный.

Это можно изменить, изменив значение дельта, чтобы фракции были разными, но я не думаю, что вы могли бы найти дельту, которая создавала одинаковые коэффициенты.

Чтобы дать аналогию, которая могла бы просто ее разорвать, если вы считаете свою дельту как только 6, и вы выполняете ее дважды, это эквивалентно бросанию 2 кубиков - каждая из дельт является независимой, но вы знаете, что 7 имеет более высокий шанс быть выбранным, чем 2.

Ответ 4

Я думаю, что это будет очень похоже, но крайности будут отличаться из-за нормализации. Например, 100 номеров, выбранных случайным образом между 1 и 100, могут быть равны 1. Однако 100 номеров, созданных с использованием вашей системы, могут иметь дельта 0,01, но когда вы их нормализуете, вы масштабируете их до диапазона 1 → 100, что будет означать, что вы никогда не получите эту странную возможность набора очень низких чисел.

Ответ 5

Ответ Alok и комментарий Дана Дайера указывают, что с помощью экспоненциальное распределение для дельт даст равномерное распределение целых чисел.

Итак, новая версия образца кода в вопросе будет:

import random,sys
running = 0
max = 1000
deltas = [random.expovariate(1.0) for i in range(0,11)]
floats = []
for d in deltas:
    running += d
    floats.append(running)
upper = floats.pop()
ints = [int(round(f/upper*max)) for f in floats]
print(ints)

Обратите внимание на использование random.expovariate(1.0), генератор случайных чисел экспоненциального распределения Python (очень полезно!). Здесь он называется со значением 1.0, но поскольку script нормализуется против последнего числа в последовательности, само значение не имеет значения.

Результат (бросок с честными играми):

[11, 43, 148, 212, 249, 458, 539, 725, 779, 871]

Ответ 6

Q: Будет ли полученное распределение целых чисел быть таким же, как генерация 100 случайных чисел из равномерно распределенной функции плотности вероятности?

A: Каждая дельта будет равномерно распределена. Центральная предельная теорема говорит нам, что распределение суммы большого числа таких отклонений (так как они имеют конечное среднее и дисперсию) будет иметь тенденцию к нормальному распределению. Следовательно, более поздние отклонения в вашей последовательности не будут равномерно распределены.

Итак, короткий ответ - "нет". Боюсь, я не могу дать простое решение, не делая алгебру. У меня нет времени делать сегодня!

Ответ 7

ссылка (1979) в Alok answer интересна. Он дает алгоритм генерации равномерной статистики порядка не путем сложения, а последовательным умножением:

max = 1.
for i = N downto 1 do
   out[i] = max = max * RAND^(1/i)

где RAND равномерна на [0,1). Таким образом, вам не нужно нормализовать в конце, и на самом деле даже не нужно хранить числа в массиве; вы можете использовать это как итератор.

Экспоненциальное распределение: теория, методы и приложения  По Н. Балакришнану, Асит П. Басу дает другой вывод этого алгоритма на стр. 22 и кредитует Мальмквиста (1950).

Ответ 8

Вы можете сделать это за два прохода:

в первом проходе генерируют дельта от 0 до (MAX_RAND/n)

во втором проходе, нормализовать случайные числа, находящиеся в пределах границ

Тем не менее O (n), с хорошей локальностью ссылки.