Сформировать массив из n элементов на основе исходного массива с коэффициентами вероятности для каждого элемента

Рейтинг: 2Ответов: 4Опубликовано: 21.01.2023

Не силен в алгоритмах, буду благодарен любой наводке для понимания принципа решения задачи.

Есть исходный массив с элементами, количество элементов не фиксированное, может быть как 2 так и 50.
Например

const items = [
  {
    id: 1,
    name: 'Item 1',
    odds: 0.1
  },
  {
    id: 2,
    name: 'Item 2',
    odds: 0.75
  },
  {
    id: 3,
    name: 'Item 3',
    odds: 2.15
  },
  {
    id: 4,
    name: 'Item 4',
    odds: 17
  },
  {
    id: 5,
    name: 'Item 5',
    odds: 80
  },
]

Сумма odds всех элементов всегда равна 100.
Нужно опираясь на шанс (odds), вероятно как-то модифицируя его, сформировать массив с фиксированным количеством элементов, например 20. При этом выборка должна быть разнообразной, например при вероятностях [1, 1, 1, 1, 96] не должно получиться 20 одинаковых элементов.
Элементы с высоким шансом должны встречаться чаще чем остальные, некоторые элементы могут вообще не попасть в результирующий массив, если длинна исходного массива больше чем длинна массива на выходе.

Пример ожидаемого результата

const resultItems = ['Item 5', 'Item 5', 'Item 1', 'Item 5', 'Item 5', 'Item 5', 'Item 4', 'Item 5', 'Item 3', 'Item 5', 'Item 5', 'Item 5', 'Item 5', 'Item 2', 'Item 4', 'Item 5', 'Item 5', 'Item 5', 'Item 4', 'Item 5']

Ответы

▲ 2

Ну не знаю я JS... Вот на С++, на каждой итерации выбирается один элемент. Я взял вероятности попроще, чтоб увидеть, что результат соответствует вероятностям (см. https://ideone.com/HmR5I7):

#include <iostream>

using namespace std;

struct Item
{
    int id;
    double p;
    int count = 0;
} items[] =
{
    {1, 10},
    {2, 15},
    {3, 20},
    {4, 25},
    {5, 30}
};


int main()
{
    srand(time(0));
    const int count = 1000;
    for(int j = 0; j < count; ++j)
    {
        double pi = 0, p = rand()*100.0/RAND_MAX;
        for(int i = 0; i < 5; ++i)
        {
            pi += items[i].p;
            if (p < pi)
            {
                cout << items[i].id << " ";
                items[i].count++;
                break;
            }
        }
    }
    cout <<"\n\n";
    for(int i = 0; i < 5; ++i)
    {
        cout << items[i].id << "  " << items[i].count << endl;
    }

}
▲ 1

Первый способ

  1. Берём рандомный элемент из массива

  2. Генерируем случайное число в промежутке [0, 100]

  3. Если вероятность элемента больше чем сгенерированное число, то включаем его в наш массив

    const items = [{
      id: 1,
      name: 'Item 1',
      odds: 0.1
    }, {
      id: 2,
      name: 'Item 2',
      odds: 0.75
    }, {
      id: 3,
      name: 'Item 3',
      odds: 2.15
    }, {
      id: 4,
      name: 'Item 4',
      odds: 17
    }, {
      id: 5,
      name: 'Item 5',
      odds: 80
    }];
    
    const getRandomItems = (items, count) => {
      const randomItems = [];
    
      while (randomItems.length !== count) {
    
        const randomIndex = Math.floor(Math.random() * items.length);
        const randomItem = items[randomIndex];
        const includeChance = Math.random() * 100;
    
        if (randomItem.odds >= includeChance) randomItems.push(randomItem.name);
    
      }
    
      return randomItems;
    }
    
    console.log(getRandomItems(items, 32));

У этого алгоритма есть недостаток: Он может работать потенциально очень долго, т.к. не понятно когда массив заполнится

Второй способ (смотрите в UPD на исправленную версию)

  1. Генерируем случайное число в промежутке [0, 100]

  2. Гуляем по массиву и смотрим у кого из элементов веротяность появления больше чем у сгенерированного числа

  3. Кто первый попался того и включаем в наш массив

    const items = [{
      id: 1,
      name: 'Item 1',
      odds: 0.1
    }, {
      id: 2,
      name: 'Item 2',
      odds: 0.75
    }, {
      id: 3,
      name: 'Item 3',
      odds: 2.15
    }, {
      id: 4,
      name: 'Item 4',
      odds: 27
    }, {
      id: 5,
      name: 'Item 5',
      odds: 70
    }];
    
    const getRandomItems = (items, count) => {
      const randomItems = [];
      
      while(count !== 0) {
        let includeChance = Math.random() * 100;
        
        for (const item of items) {
          if (includeChance < item.odds) {
            randomItems.push(item.name);
            --count;
            break;
          }
        }
      }
    
      return randomItems;
    }
    
    console.log(getRandomItems(items, 32));

У этого алгоритма сложность будет равна count * items.length

У этого алгоритма есть недостаток: Если будут 2 элемента с вероятностями по 50, то всегда будет включён, тот кто первый. Чтобы устранить этот недостаток было предложено использовать накопительные суммы вероятностей, но пока я не очень понимаю что это такое не буду вписывать в свой алгоритм

UPD

Я наконец-то осознал как работают "накопительные суммы вероятностей" :) Попробую объяснить на простых примерах

Обозначения:

  • НП - Наибольший Полуинтервал - [0, 100)
  • СЧ - это случайное Сгенерированное Число в пределах НП

Начнём с самой проблемы, как мы уже увидели что если у нас 2 элемента с вероятностями по 50, то всегда будет выбираться первый. Но на самом деле это только верхушка проблемы, в общем проблема в том что второй алгоритм будет включать ВСЕГДА только первый элемент сруди тех у кого одинаковые вероятнсти. Например пусть у нас есть следующие вероятности [1, 1, 2, 2, 3, 3, 4, 4, 80], тогда если случайным образом нам выпадет число 1/2/3/4, то в результирующем массиве мы получим только первые 1/2/3/4, а вторые не будут включены никогда. Схематически это можно изобразить так:

введите сюда описание изображения

Выбираем случайную точку на отрезке - это и будет нашим СЧ. Далее проводим вертикальную прямую от этой точки и смотрим с каким прямоугольником прямая пересечётся первой, этот прямоугольник и есть элемент, который мы добавим в массив. Теперь ясно видно, почему вторые (другие равные) прямоугльники не будут включены никогда

По схеме мы явно видим и вторую проблему: если СЧ будет больше чем максимально возможная вероятность (в схеме это 80), то мы не добавим ничего в наш массив. Было бы хорошо покрыть весь НП, чтобы при любом значении СЧ мы что-то добавляли в массив. Таким образом нам нужно добиться того чтобы схема выглядела так:

введите сюда описание изображения

Во второй схеме явно видно, что:

  1. при любом значении СЧ мы что-то добавим в наш массив
  2. у каждого элемента теперь есть шанс попасть в массив, независимо от того где он находился в исходном массиве, т.к. мы покрываем все значение из НП
  3. каждый из элементов занимает, пропорциональный своей вероятности, полуинтервал

Глядя на вторую схему, легко понять каким полуинтервалам принадлежит тот или иной прямоугольник:

  1. 1 - [0, 1)
  2. 1 - [1, 2)
  3. 2 - [2, 4)
  4. 2 - [4, 6)
  5. 3 - [6, 9)
  6. 3 - [9, 12)
  7. 4 - [12, 16)
  8. 4 - [16, 20)
  9. 80 - [20, 100)

В таком подходе есть ещё один очень важный плюс: Если например у нас будут вероятности [1, 1, 1, 1, 1, 95], то шанс попадания одного из элементов с вероятностью 1 в 5 раз больше чем при первом подходе. Но это не значит что они обязательно будут включены в массив. Дело вот в чём, они попадут в массив, если

  1. количество требуемых элементов достаточно велико
  2. метод генерирующий случайные числа выдаёт их, в заданном полуинтервале, равномерно. Например нам нужны 1000 СЧ в НП, то не будет такой картины, что числа после 50 выпадают заметно чаще чем до него или что отдельные взятые полуинтервалы к примеру [25, 50) и [75, 100] имеют больший шанс, что СЧ будет принадлежать им

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

Если не гарантируется равномерность, то каким бы большим числом не было количество требуемых элементов, будет НЕнулевая вероятность того, что некоторые элементы никогда не попадут в массив

Если же не выполняются оба условия, то можете считать, что никогда не увидите в массиве элементы с низким шансом

Так что есть немало факторов, кроме самих подходов, которые влияют не результат. "в 5 раз" - может показаться большой разницей, но это тоже зависит от исходных данных, например пусть вероятности [0.1, 0.1, 0.1, 0.1, 0.1, 99,5], тогда что 0.1 что 0.5 почти не будет играть роли

Чтобы понять как запрограммировать второй подход, вышеописанные полуинтервалы нужно переписать в следующем виде:

  1. 1 - [0, 0 + 1)
  2. 1 - [0 + 1, 0 + 1 + 1)
  3. 2 - [0 + 1 + 1, 0 + 1 + 1 + 2)
  4. 2 - [0 + 1 + 1 + 2, 0 + 1 + 1 + 2 + 2)
  5. 3 - [0 + 1 + 1 + 2 + 2, 0 + 1 + 1 + 2 + 2 + 3)
  6. 3 - [0 + 1 + 1 + 2 + 2 + 3, 0 + 1 + 1 + 2 + 2 + 3 + 3)
  7. 4 - [0 + 1 + 1 + 2 + 2 + 3 + 3, 0 + 1 + 1 + 2 + 2 + 3 + 3 + 4)
  8. 4 - [0 + 1 + 1 + 2 + 2 + 3 + 3 + 4, 0 + 1 + 1 + 2 + 2 + 3 + 3 + 4 + 4)
  9. 80 - [0 + 1 + 1 + 2 + 2 + 3 + 3 + 4 + 4, 0 + 1 + 1 + 2 + 2 + 3 + 3 + 4 + 4 + 80)

Отсюда видно, что в правой части - то что в левой части + вероятность текущего элемента

Теперь перед нами стоит задача: Понять какому из промежутков принадлежит СЧ. Т.к. мы не можем сразу с ходу ответить на этот вопрос, то нам придётся начиная перебирать полуинтервалы начиная с первого

И так пусть СЧ - это x, и чтобы понять принадлежит ли x полуинтервалу [a, b), нам надо убедиться что выполняется a <= x < b:

  1. 0 <= x < 0 + 1 - отнимаем (0) => 0 - (0) <= x - (0) < 0 + 1 - (0) => 0 <= x - (0) < 1, если условие выполняется, то останавливаемся, если нет, то смотрим следующий
  2. 0 + 1 <= x < 0 + 1 + 1 - отнимаем ((0) + 1) => 0 + 1 - ((0) + 1) <= x - ((0) + 1) < 0 + 1 + 1 - ((0) + 1) => 0 <= x - ((0) + 1) < 1, если условие выполняется, то останавливаемся, если нет, то смотрим следующий
  3. 0 + 1 + 1 <= x < 0 + 1 + 1 + 2 - отнимаем (((0) + 1) + 1) => 0 + 1 + 1 - (((0) + 1) + 1) <= x - (((0) + 1) + 1) < 0 + 1 + 1 + 2- (((0) + 1) + 1) => 0 <= x - (((0) + 1) + 1) < 2, если условие выполняется, то останавливаемся, если нет, то смотрим следующий

и т.д. пока не дойдём до последнего. Но этот алгоритм можно упростить, заметив следующее:

  1. для упрощения мы всегда отнимаем левую часть у всех частей неравенства. Оно и логично, ведь как мы заметили раньше, правая часть - это левая часть + вероятность текущего элемента, а значит можно не пересчитывать два раза одно и то же

  2. после упрощений слева всегда остаётся 0

  3. сравнивать 0 <= СЧ бессмысленно, т.к. изначально СЧ принимает значения [0, 100), потому всё что нам надо - это сравнивать СЧ с правой частью полуинтервала

  4. для каждого нового полуинтервала мы сначала отнимаем, то что отнимали в предыдущих шагах. Зачем? Мы можем не тратить время на повторные вычисления

  5. У первого интервала всегда левая часть будет 0, потому его можно не писать и не учитывать при вычислениях. Тогда наши полуинтервалы будут выглядеть так:

    1. 1 - [0, 1)
    2. 1 - [1, 1 + 1)
    3. 2 - [1 + 1, 1 + 1 + 2)

    и т.д. думаю смысл ясен

Учитывая замечания, предыдущий алгоритм можно выполнять так:

  1. x < 1, если условие выполняется, то останавливаемся, если нет, то смотрим следующий
  2. x < 1 + 1 - отнимаем 1 (правая часть предыдущего полуинтервала) => x - (1) < 1, если условие выполняется, то останавливаемся, если нет, то смотрим следующий
  3. x - (1) < 1 + 1 + 2 - (1) - откуда появился - (1) у правой части? Мы уже уменьшили на предыдущем шаге наш x, а значит при следующем сравнении, правая часть так же должна быть уменьшена на то же значение, на сколько мы уменьшили x - должны были отнимать (1 + 1), но мы уже 1 единицу отсюда отняли на предыдущем шаге, потому по сути надо просто отнять (1 + 1) - 1 = 1 => x - (1 + 1) < 1 + 2 - 1 => x - 1 - 1 < 2, если условие выполняется, то останавливаемся, если нет, то смотрим следующий
  4. x - (1 + 1) < 1 + 1 + 2 + 2 - (1 + 1) => x - (1 + 1) < 2 + 2 - отнимаем 2 => x - (1 + 1 + 2) < 2, если условие выполняется, то останавливаемся, если нет, то смотрим следующий
  5. x - (1 + 1 + 2) < 1 + 1 + 2 + 2 + 3 - (1 + 1 + 2) => x - (1 + 1 + 2) < 2 + 3 - отнимаем 2 => x - (1 + 1 + 2 + 2) < 3, если условие выполняется, то останавливаемся, если нет, то смотрим следующий
  6. x - (1 + 1 + 2 + 2) < 1 + 1 + 2 + 2 + 3 + 3 - (1 + 1 + 2 + 2) => x - (1 + 1 + 2 + 2) < 3 + 3 - отнимаем 3 => x - (1 + 1 + 2 + 2 + 3) < 3, если условие выполняется, то останавливаемся, если нет, то смотрим следующий
  7. x - (1 + 1 + 2 + 2 + 3) < 1 + 1 + 2 + 2 + 3 + 3 + 4 - (1 + 1 + 2 + 2 + 3) => x - (1 + 1 + 2 + 2) < 3 + 4 - отнимаем 3 => x - (1 + 1 + 2 + 2 + 3 + 3) < 4, если условие выполняется, то останавливаемся, если нет, то смотрим следующий
  8. x - (1 + 1 + 2 + 2 + 3 + 3) < 1 + 1 + 2 + 2 + 3 + 3 + 4 + 4 - (1 + 1 + 2 + 2 + 3 + 3) => x - (1 + 1 + 2 + 2 + 3 + 3) < 4 + 4 - отнимаем 4 => x - (1 + 1 + 2 + 2 + 3) < 4, если условие выполняется, то останавливаемся, если нет, то смотрим следующий
  9. x - (1 + 1 + 2 + 2 + 3 + 3 + 4) < 1 + 1 + 2 + 2 + 3 + 3 + 4 + 4 + 80 - (1 + 1 + 2 + 2 + 3 + 3 + 4) => x - (1 + 1 + 2 + 2 + 3 + 3 + 4) < 4 + 80 - отнимаем 4 => x - (1 + 1 + 2 + 2 + 3 + 3 + 4 + 4) < 80, если мы дошли до последнего шага, то значит последний элемент будет очевидно включён

Для простоты записи давайте заменим x - (...) на x_(номер шага), тогда это всё можно записать в очень простом виде:

  1. x_1 < 1
  2. x_2 < 1
  3. x_3 < 2
  4. x_4 < 2
  5. x_5 < 3
  6. x_6 < 3
  7. x_7 < 4
  8. x_8 < 4
  9. x_9 < 80

, где каждый x_n - можно выразить через предыдущий

Если внимательно посмотреть на правую сторону, то мы увидим что там остались ровно те вероятности, которые были изначально у элементов. Теперь у нас есть всё, чтобы запрограммировать это:

Второй способ (исправленный)

const items = [{
  id: 1,
  name: 'Item 1',
  odds: 0.1
}, {
  id: 2,
  name: 'Item 2',
  odds: 0.75
}, {
  id: 3,
  name: 'Item 3',
  odds: 2.15
}, {
  id: 4,
  name: 'Item 4',
  odds: 27
}, {
  id: 5,
  name: 'Item 5',
  odds: 70
}];

const getRandomItems = (items, count) => {
  const randomItems = [];
  
  while(count !== 0) {
    let includeChance = Math.random() * 100;
    
    for (const item of items) {
      if (includeChance < item.odds) {
        randomItems.push(item.name);
        --count;
        break;
      }
      
      includeChance -= item.odds;
    }
  }

  return randomItems;
}

console.log(getRandomItems(items, 32));

Примеры для наглядности разницы работы первого и второго алгоритма:

const getRandomItems1 = (items, count) => {
  const randomItems = [];
  
  while(count !== 0) {
    let includeChance = Math.random() * 100;
    
    for (const item of items) {
      if (includeChance < item.odds) {
        randomItems.push(item.name);
        --count;
        break;
      }
    }
  }

  return randomItems;
}

const getRandomItems2 = (items, count) => {
  const randomItems = [];
  
  while(count !== 0) {
    let includeChance = Math.random() * 100;
    
    for (const item of items) {
      if (includeChance < item.odds) {
        randomItems.push(item.name);
        --count;
        break;
      }
      
      includeChance -= item.odds;
    }
  }

  return randomItems;
}

const items1 = [{
  id: 1,
  name: 'Item 1',
  odds: 50
}, {
  id: 2,
  name: 'Item 2',
  odds: 50
}];

console.log(JSON.stringify(getRandomItems1(items1, 16))); // Только 'Item 1'
console.log(JSON.stringify(getRandomItems2(items1, 16)));

console.log('----------------------------------------');

const items2 = [{
  id: 1,
  name: 'Item 1',
  odds: 20
}, {
  id: 2,
  name: 'Item 2',
  odds: 20
}, {
  id: 3,
  name: 'Item 3',
  odds: 30
}, {
  id: 4,
  name: 'Item 4',
  odds: 30
}];

console.log(JSON.stringify(getRandomItems1(items2, 16))); // Только 'Item 1' и/или 'Item 3'
console.log(JSON.stringify(getRandomItems2(items2, 16)));

console.log('----------------------------------------');

const items3 = [{
  id: 1,
  name: 'Item 1',
  odds: 1
}, {
  id: 2,
  name: 'Item 2',
  odds: 1
}, {
  id: 3,
  name: 'Item 3',
  odds: 1
}, {
  id: 4,
  name: 'Item 4',
  odds: 1
}, {
  id: 5,
  name: 'Item 5',
  odds: 1
}, {
  id: 6,
  name: 'Item 6',
  odds: 95
}];

console.log(JSON.stringify(getRandomItems1(items3, 16))); // Только 'Item 1' и/или 'Item 6'
console.log(JSON.stringify(getRandomItems2(items3, 16)));

Для меня самым интересным во всём этом является то, что разница между кодом первого и второго алгоритмов - это всего одна строчка includeChance -= item.odds, а за этим стоит целая теория :)

▲ 1

Для генерации выборок используется массив - "лесенка" из вероятностей нарастающим итогом, аналогично предложенной @Harry в комментариях к вопросу. Для обеспечения "разнообразия" выборок (чем больше разных видов элементов в выборке, там лучше) используется дополнительный цикл с ограничением на кол-ва повторных попыток. Лучший вариант выборки (самый разнообразный) выводится в консоль.

const items = [{
    id: 1,
    name: 'Item 1',
    odds: 0.1
  },
  {
    id: 2,
    name: 'Item 2',
    odds: 0.75
  },
  {
    id: 3,
    name: 'Item 3',
    odds: 2.15
  },
  {
    id: 4,
    name: 'Item 4',
    odds: 17
  },
  {
    id: 5,
    name: 'Item 5',
    odds: 80
  },
]

let scale = [],
  out = [],
  best = [],
  i = 0,
  iterations = 0,
  max_iterations = 10,
  min_elem = 5,
  amount = 10;
min_elem = Math.min(min_elem, items.length);
items.forEach(el => { // делаем "лесенку" из вероятностей нарастающим итогом
  i += el['odds'];
  scale.push(i);
})
while ((new Set(out)).size < min_elem) { // повторяет генерацию, если менее min_elem видов элементов в выборке
  out = [];
  for (i = 0; i < amount; i++) { // генерим очередную выборку
    out.push(items[scale.findIndex(s => s >= Math.random() * 100)]['name']);
  }
  if ((new Set(out)).size > (new Set(best)).size) best = out; // заносим в best лучшую (самую разнообразную) выборку
  if (iterations++ >= max_iterations) break; // прекращаем попытки, если предельное количество попыток достигнуто
}
console.log(best) // выводим лучшую (самую разнообразную) выборку
s = new Set(best)
console.log(`В выборке ${s.size} видов элементов: {${Array.from(s).sort()}}, использовано попыток: ${iterations - 1}`)

▲ 0

choose принимает массив вероятностей с единичной суммой. Для случайной величины проверяется в какую часть единичного отрезка она попадает. Размеры частей равны вероятностям из probs. choose возвращает индекс в массиве probs.

sample - обёртка над choose. Она формирует массив из вероятностей, годный для choose. Индекс массива отображается в имя элемента.

const choose = probs => {
    let value = Math.random();
    for (let i = 0; i < probs.length; ++i) {
        value -= probs[i];
        if (value < 0) {
            return i;
        }
    }
    return probs.length - 1;
};

const sample = (items, n) => {
    let values = items.map(item => item['odds']);
    const sum = values.reduce((a, b) => a + b, 0);
    const probs = values.map(p => p / sum);
    const choices = [];
    for (let i = 0; i < n; ++i) {
        choices.push(items[choose(probs)]['name']);
    }
    return choices;
};

const items = [
    { name: 'Item 1', odds: 10 },
    { name: 'Item 2', odds: 20 },
    { name: 'Item 3', odds: 40 }
];

console.log(sample(items, 20).join(", "));