Если я правильно понял задачу, то я решал бы её так.
1. Отсортировать масси по убыванию значения оценки. P.S. На самом деле оказалось, что не обязательно.
2. Далее исходим из таких соображений. Пусть сумма всех оценок sum(M(i)) будет равна S и примем это за 100% вероятность. То есть, со 00% вероятностью один из элементов нашего массива будет выбран.
Тогда вероятность выпадания i-го элемента будет пропорциональна его оценке: P(i) = M(i)/S
3. Будем проходить по каждому элементу отсортированного массива и будем вычислять вероятность P(i). Выбираем случайное число P = random()*N, где N - оставшееся число непройденных элементов. Если P < P(i), то показываем этот рандомный элемент i и завершаем цикл.
4. Пересчитываем S = sum(M(i)) для всех оставшихся элементов.
Сложность алгоритма получается O(N^2)
Это так, сходу решение.
Но его можно улучшить ка минимум до О(N), а, возможно, и до O(1). Но тогда придётся ввести дополнительное поле вероятности.
UPD: Вынесу пример из комментариев:
Пусть у нас массив из оценок [5, 5, 3, 2]
Сумма всех оценок S = 5+5+3+2 = 15
Вероятности выбора каждого элемента:
[5/15, 5/15, 3/15, 2/15] = [0.33333, 0.33333, 0.2, 0.133333], в сумме они дадут 1, как и должно быть.
1. Берём первый элемент с оценкой 5 и с вероятностью 0.3333 выбираем его: P = random()*1.0
Если P<0.333, то выбираем 1-й элемент и заканчиваем работу. Иначе идём дальше
2. Берём 2-й элемент с оценкой 5. Теперь у нас вероятность изменилась и мы её пересчитываем, чтобы в сумме была 1:
S = 5 + 3+ 2 = 10
Пересчитываем вероятности:
[5/10, 3/10, 2/10] = [0.5 ,0.3, 0.2] - в сумме опять 1, как и должно быть.
Теперь с вероятностью 0.5 определяем, берём ли мы 2-й элемент в качестве результата или нет: P = random()*1.0
Если P< 0.5, то заканчиваем работу. Иначе, идём дальше.
3. Пересчитываем общую сумму оценок: S = 3 + 2 = 5
Новые вероятности для оставшихся оценок: [3/5, 2/5] = [0.6, 0.4], в сумме опять 1
С вероятностью 0.6 определяем, оставляем ли 3-й элемент в качестве результата или нет.
Если нет, то дальше
4. Пересчитываем сумму оставшихся оценок: S = 2.
Новые вероятности для оставшихся оценок: [2/2] = [1].
То есть, со 100% вероятностью забираем последний элемент.
Но вот чтобы добраться до последнего элемента надо продраться через тернии более высоких оценок. Сложно, маловероятно, но в принципе это возможно.
UPD: Для оптимизации расчёта новой суммы S просто вычитаем из предыдущей S значение оценки i-го элемента. Сводим алгоритм к O(N)
UPD2: Если надо инвертировать и сделать так, чтобы элементы с минимальными оценками показывались чаще, то надо инвертировать вероятность: 1-P
UPD3, решение за время O(1) Я тут ещё раз подумал и решение оказалось ещё более простым.
Пусть у нас массив из оценок [5, 5, 3, 2]
Сумма всех оценок S = 5+5+3+2 = 15
Вероятности выбора каждого элемента:
[5/15, 5/15, 3/15, 2/15] = [0.33333, 0.33333, 0.2, 0.133333]
Строим отрезок, откладывая на нём эти четыре значения.
Берём случайное число от 0 до 1 и смотрим, в какой из этих четырёх отрезков он попадает. Вот и решение.
Если надо, чтобы маловероятные оценки выпадали, то строим инвертированные вероятности:
[0.6666, 0.6666, 0.8, 0.8666666]
