Случайный выбор массива с уклоном [дубликат]
C способ сделать это:
float areaForPoly(const int numVerts, const Point *verts)
{
Point v2;
float area = 0.0f;
for (int i = 0; i<numVerts; i++){
v2 = verts[(i + 1) % numVerts];
area += verts[i].x*v2.y - verts[i].y*v2.x;
}
return area / 2.0f;
}
6 ответов
Вот взвешенная функция выбора с некоторым кодом, который ее использует.
import random
def WeightedPick(d):
r = random.uniform(0, sum(d.itervalues()))
s = 0.0
for k, w in d.iteritems():
s += w
if r < s: return k
return k
def Test():
k = {'A': 68, 'B': 62, 'C': 47, 'D': 16, 'E': 81}
results = {}
for x in xrange(10000):
p = WeightedPick(k)
results[p] = results.get(p, 0) + 1
print results
Test()
-
1Большое спасибо! Этот код возвращает точно правильные результаты. Спасибо за ваши быстрые ответы, все. – LaundroMat 3 April 2010 в 10:56
-
2Но все же: точный вес не достигается (тест со 100 миллионами rnd дал мне 24,8203% для «A»). Должен ли я беспокоиться об этом (т. Е. Это код, который виноват?), Или это просто характер случайности? – LaundroMat 3 April 2010 в 11:08
-
3@LaundroMat Да, вероятность сходится по мере увеличения количества испытаний, но никогда не будет точным. Вы можете прочитать о дисперсии или стандартном отклонении, чтобы узнать, чего вы можете ожидать. – user 3 April 2010 в 11:33
Я разработал алгоритм несколько лет назад, с приложением в Perl и SQL, вы можете прочитать об этом здесь , в комплекте с анализом и проверками, почему он (скорее всего) правильный.
Концепция проста: для каждого элемента выбирайте случайное число, тяните его через какую-то функцию, которая зависит от веса элементов и выбирает элемент с наименьшим значением.
функция:
x[i] = -log(1 - rand())/weight[i]
-
1
-
2Умный трюк, но это ужасная идея использовать это на практике. Это не очевидно правильно (несмотря на страницы математического доказательства), и это дорого вычислить (для этого требуются вызовы N rand () и вызовы N log ()). Кроме того, у него, вероятно, будут численные проблемы. Когда 1 - rand () близко к 0, журнал может быть сколь угодно большим; возможно, переполненный. – user 5 April 2010 в 09:54
Алгоритм был бы таким.
Выберите число случайным образом между 1 и 274. Для этого вызовите функцию rand () (предположим, что она возвращает значение от 0 до 1), умножьте rand () на 274. Результирующее значение теперь должно находиться в диапазоне. Если его между 1 и 68, выберите A, если между 69 и 130 выберите B и так далее. Таким образом, ваша вероятность останется в живых, и ваша операция будет успешной.
PS: Я парень Java, не знаю синтаксиса Python.
-
1Если он существует, вы должны использовать функцию / метод, который возвращает целое число в определенном диапазоне вместо масштабирования значения с плавающей запятой, чтобы избежать проблем с псевдонимом. – Joey 3 April 2010 в 09:53
-
2Точно, метод масштабирования будет отличным. Я имею в виду, что я обычно выдавал полученное значение из метода rand, отбрасывая его на целое число. – bragboy 3 April 2010 в 09:56
Это должно сделать трюк:
>>> k = {'A': 68, 'B': 62, 'C': 47, 'D': 16, 'E': 81}
>>> import random
>>> def weighted_pick(dic):
... total = sum(dic.itervalues())
... pick = random.randint(0, total-1)
... tmp = 0
... for key, weight in dic.iteritems():
... tmp += weight
... if pick < tmp:
... return key
-
1
-
2
Самый простой способ сделать это, когда ваши веса являются относительно небольшими целыми числами (например, в вашем примере), состоит в том, чтобы построить длинную строку, содержащую все символы в соответствующих весах, и выбрать из нее случайный случай:
import random
d = {'A': 68, 'B': 62, 'C': 47, 'D': 16, 'E': 81}
s = ''.join(k*v for k,v in d.items())
random.choice(s)
Обратите внимание, что этот метод будет использовать довольно много памяти, если ваши весы большие, и в этом случае вы можете предпочесть другое решение.
следует также посмотреть на , что эта ссылка
делает два списка для k, например xk и yk
from scipy import stats
custm = stats.rv_discrete(name='test', values=(xk, yk))
custm.rvs(size=1)