LINUX.ORG.RU

Удаление элемента массива с некоторой вероятностью


0

0

Не знаю получиться ли нормально объяснить что я хочу, но попытаюсь :)

Есть массив из N элементов. Каждый элемент - некоторое число от 0 до M.
Есть Q итераций. На каждой итерации есть ВЕРОЯТНОСТЬ удаления 1 элемента из массива.
Так вот, если генерировать случайное число от 0 до N-1 и удалять элемент с соответствующим номером, то, как я понимаю, теоретически будет равномерное распределение вероятностей. На каждой итерации вероятность удаления элемента будет равна для каждого из них.

Вопрос: как сделать, чтобы вероятность удаления элемента на каждой итерации была прямо пропорциональна величине элемента.
Т.е. если все элементы в массиве равны, то будет то же равномерное распределение.
Иначе, допустим, в массиве N-1 нулей, и 1 элемент равен M. Тогда на след. итерации удалиться именно он.
Если этот элемент равен M-1, другой 1, остальные нули, то опять же скорее всего удалиться элемент величиной M-1, НО уже есть вероятность удаления элемента величиной 1.
В общем чем больше элемент, тем больше шансов у него быть удаленным на след. итерации, и наоборот.

Пока что пришел в голову только такой вариант решения: генерируем случайное число k от 0 до N-1, и случайное число q от 0 до M. Если k-й элемент массива меньше или равен q, то удаляем его.
Получается, что 0 будет удален всегда - т.к. он будет меньше или равен любого сгенерированного числа.
Если же элемент равен M, то он будет удален лишь в том случае, если сгенерированное число так же будет равно M (а вероятность этого довольно мала).
НО данный вариант не работает, если на каждой итерации будут так же добавляться некоторые элементы в массив неслучайным(!) образом. Ну и к тому же в данном случае 100% будет удаляться 1 элемент на каждой итерации, даже если остались только очень маленькие элементы.

В общем надеюсь более-менее понятно объяснил суть.


★★★★★

double[] arr = {1, 2, 3, 2, 1};
double sum = 0;
double randomValue;
int i;

for (int i = 0; i < sizeof(arr) / sizeof(*arr); ++i) {
    sum += arr[i];
}

randomValue = (double) rand() / RAND_MAX * sum;

i = 0;
while (randomValue > arr[i]) {
    randomValue -= arr[i];
    ++i;
}
printf("%d", i);

код не проверял, но идея, думаю, понятна.

Legioner ★★★★★ ()

можно делить значение на максимальное число элементов и максимальное значение, но это скорее всего не то, что тебе надо(т.е. не то распределение)... думать лень

dimon555 ★★★★★ ()

1) делаешь вектор содержащий N твоих массивов, каждый из массивов содержит свой порядковый номер во всех элементах.

2) генеришь на каждом шаге случайное число до N и получаешь из вектора номер массива, если его не встречалось ранее выдаешь.

3) когда число выдач успешных равно N прекращаешь.

psv1967 ★★★★★ ()
Ответ на: комментарий от psv1967

....каждый из массивов составляющий вектор имеет длинну M и содержит свой n из N во всех элементах.

psv1967 ★★★★★ ()

psv1967 если честно, то не понял что имеешь ввиду.
к тому же, при больших значениях M и N - не слишком ли много больших массивов будет? И не слишком ли долго будет работать все это?
Хотелось бы обойтись одним массивом.

Legioner, попробую твой вариант, отпишусь нормально ли работать будет.

kovrik ★★★★★ ()

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

anonymous ()
Ответ на: комментарий от kovrik

ну у тебя ведь только генератор равномерного распределения?

решение прямое очень простое если используются нормальные средства :):

получили n чисел, каждое от 0 до m
n<-1000
m<-100
nm <- round(runif (n, min=0, max=m))

нашли порядок выбывания чисел согласно условиям задачи

nm[sample(1:n,m,replace=FALSE,prob=nm+1)]


если у нас нет sample с возможностью указать prob, то пишем замену :)

например получаем массив о котором собственно речь

nm_vector <- unlist(mapply(rep,1:n,nm))

и выбираем из него по элементу

nm[sample(nm_vector,1)]

придется проверять что элемент встречался ранее.

psv1967 ★★★★★ ()
Ответ на: комментарий от psv1967

если памяти так мало, то в пределах разрядности :) потом на блоки бить придется чтобы sum(nm+1) не ушла за разрядность

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

length(nm[(cumsum(nm+1)<runif(1,min=1,max=sum(nm+1)))])

psv1967 ★★★★★ ()

Не понял, на каждой итерации обязательно должен быть удален элемент?

Может быть так:

1. Сосчитать сумму всех элементов.

2. Поделить все элементы на сумму.

3. Составить массив вида l = [a0, a0 + a1, a0 + a1 + a2...]

4. Сгенерировать число p = [0, 1]

5. Идти по массиву l и сравнивать с числом из p. Если оказалось что l[i] < p, то выкидываем i-ы элемент

Может быть я не правильно понял задачу.

e3d08dff ()

Если элементов в массиве не очень много, то так, как Легионер сказал.

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

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

Все операции логарифмические => профит при очень больших N.

lodin ★★★★ ()
Ответ на: комментарий от lodin

> Если много, то считать сумму и проходить в среднем половину массива каждый раз может оказаться несколько печально.

Массив упорядоченный - так что поиск в нём организуется элементарно, скорей всего даже есть нужные стандартные функции.

Сумма каждый раз меняется на величину удаляемого элемента, затраты на подсчёт - одна операция.

anonymous ()
Ответ на: комментарий от lodin

Разумеется, забыл самое интересное. Зачём вся конструкция.

Пусть у нас есть случайное число n, меньшее веса [под]дерева. Если мы в листе — нашли, убираем лист. Если нет, сравниваем n с весом левого потомка: если меньше — спускаемся в левого потомка, если же больше — вычитаем вес левого потомка из n и спускаемся направо. Вероятность попасть в каждый лист при этом как раз равна весу листа, делённому на вес всего дерева (=сумме элементов массива).

lodin ★★★★ ()

/* Unequal probability sampling; without-replacement case */

static void ProbSampleNoReplace(int n, double *p, int *perm,
int nans, int *ans)
{
double rT, mass, totalmass;
int i, j, k, n1;

/* Record element identities */
for (i = 0; i < n; i++)
perm[i] = i + 1;

/* Sort probabilities into descending order */
/* Order element identities in parallel */
revsort(p, perm, n);

/* Compute the sample */
totalmass = 1;
for (i = 0, n1 = n-1; i < nans; i++, n1--) {
rT = totalmass * unif_rand();
mass = 0;
for (j = 0; j < n1; j++) {
mass += p[j];
if (rT <= mass)
break;
}
ans[i] = perm[j];
totalmass -= p[j];
for(k = j; k < n1; k++) {
p[k] = p[k + 1];
perm[k] = perm[k + 1];
}
}
}

psv1967 ★★★★★ ()
Вы не можете добавлять комментарии в эту тему. Тема перемещена в архив.