Как реализовать выдачу рандомного элемента из массива с учетом рейтинта?
==========================================================================

 Помогите решить задачу, есть на сервере массив с обьектами. В каждом обьекте есть грубо говоря имя(которое не имеет сейчас значения) и рейтинг. Этот рейтинг изменяется с помощью нажатия на кнопку-оценку этого элемента,которая прибавляется и делится на количество оценок. Задача: реализовать механизм рандомного показа элемента на UI с более приоритетным уклоном в сторону элементов с низким рейтингом, то есть не показывать просто элемент с наиболее низким рейтингом, а чтобы элементы с низким рейтингом имели приоритет, желательно без ввода сторонних значений, типа priority 

 Если я правильно понял задачу, то я решал бы её так.  

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] 

 Достаточно частая задача. Вы должны просто отсортировать массив обьектов. Обычно с сервера уже присылают сортированный массив но можно сделать и на клиенте.  

```
const singers = [
  { name: 'Steven Tyler', band: 'Aerosmith', born: 1948 },
  { name: 'Karen Carpenter', band: 'The Carpenters', born: 1950 },
  { name: 'Kurt Cobain', band: 'Nirvana', born: 1967 },
  { name: 'Stevie Nicks', band: 'Fleetwood Mac', born: 1948 },
];

function compareValues(key, order = 'asc') {
  return function innerSort(a, b) {
    if (!a.hasOwnProperty(key) || !b.hasOwnProperty(key)) {
      // property doesn't exist on either object
      return 0;
    }

    const varA = (typeof a[key] === 'string')
      ? a[key].toUpperCase() : a[key];
    const varB = (typeof b[key] === 'string')
      ? b[key].toUpperCase() : b[key];

    let comparison = 0;
    if (varA > varB) {
      comparison = 1;
    } else if (varA < varB) {
      comparison = -1;
    }
    return (
      (order === 'desc') ? (comparison * -1) : comparison
    );
  };
}

// array is sorted by band, in ascending order by default
singers.sort(compareValues('band'));

// array is sorted by band in descending order
singers.sort(compareValues('band', 'desc'));
```
 

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

  

**Пример:**  

Было (одна цифра - рейтинг элемента):  

5861273  

Стало:  

1238765 (или 2138765 или 3128765 и т.д.)