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

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);

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

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

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

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

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

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

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

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

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

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

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

получили 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)]

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

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

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

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

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

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

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

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

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

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

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

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

Похоже что это то же самое что написал Legioner

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

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

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

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

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

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

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

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

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

/* 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];
}
}
}