Создать взвешенный случайный номер

Ответ 1

Выборка отклонения (например, в вашем решении) - это первое, что приходит на ум, когда вы строите таблицу поиска с элементами, заполненными их распределением веса, затем выбираете случайное место в таблице и возвращаете его. В качестве варианта реализации я бы сделал функцию более высокого порядка, которая принимает спецификацию и возвращает функцию, которая возвращает значения, основанные на распределении в спецификации, таким образом вы избегаете необходимости создавать таблицу для каждого вызова. Недостатком является то, что алгоритмическая производительность построения таблицы является линейной по количеству элементов, и потенциально может быть много использования памяти для больших спецификаций (или тех, которые имеют элементы с очень маленькими или точными весами, например, {0: 0.99999, 1: 0,00001}). Положительным моментом является то, что выбор значения имеет постоянное время, что может быть желательно, если производительность критична. В JavaScript:

function weightedRand(spec) {
  var i, j, table=[];
  for (i in spec) {
    // The constant 10 below should be computed based on the
    // weights in the spec for a correct and optimal table size.
    // E.g. the spec {0:0.999, 1:0.001} will break this impl.
    for (j=0; j<spec[i]*10; j++) {
      table.push(i);
    }
  }
  return function() {
    return table[Math.floor(Math.random() * table.length)];
  }
}
var rand012 = weightedRand({0:0.8, 1:0.1, 2:0.1});
rand012(); // random in distribution...

Другая стратегия состоит в том, чтобы выбрать случайное число в [0,1) и перебрать спецификацию весов, суммируя веса, если случайное число меньше суммы, затем вернуть соответствующее значение. Конечно, это предполагает, что весовые коэффициенты равны единице. Это решение не требует первоначальных затрат, но имеет среднюю алгоритмическую производительность, линейную по количеству записей в спецификации. Например, в JavaScript:

function weightedRand2(spec) {
  var i, sum=0, r=Math.random();
  for (i in spec) {
    sum += spec[i];
    if (r <= sum) return i;
  }
}
weightedRand2({0:0.8, 1:0.1, 2:0.1}); // random in distribution...

Ответ 2

Создайте случайное число R между 0 и 1.

Если R в [0, 0.1) → 1

Если R в [0,1, 0,2) → 2

Если R в [0.2, 1] → 3

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

(1, 83,7%) и (2, 16,3%), сверните число от 1 до 1000. 1-837 - это 1. 838-1000 - это 2.

Ответ 3

Это более или менее универсальная версия того, что написал @trinithis, в Java: я делал это с помощью int, а не с плавающей точкой, чтобы избежать беспорядочных ошибок округления.

static class Weighting {

    int value;
    int weighting;

    public Weighting(int v, int w) {
        this.value = v;
        this.weighting = w;
    }

}

public static int weightedRandom(List<Weighting> weightingOptions) {

    //determine sum of all weightings
    int total = 0;
    for (Weighting w : weightingOptions) {
        total += w.weighting;
    }

    //select a random value between 0 and our total
    int random = new Random().nextInt(total);

    //loop thru our weightings until we arrive at the correct one
    int current = 0;
    for (Weighting w : weightingOptions) {
        current += w.weighting;
        if (random < current)
            return w.value;
    }

    //shouldn't happen.
    return -1;
}

public static void main(String[] args) {

    List<Weighting> weightings = new ArrayList<Weighting>();
    weightings.add(new Weighting(0, 8));
    weightings.add(new Weighting(1, 1));
    weightings.add(new Weighting(2, 1));

    for (int i = 0; i < 100; i++) {
        System.out.println(weightedRandom(weightings));
    }
}

Ответ 4

Вот 3 решения в javascript, так как я не уверен, на каком языке вы его хотите. В зависимости от ваших потребностей один из первых двух может работать, но третий, возможно, проще всего реализовать с большими наборами чисел.

function randomSimple(){
  return [0,0,0,0,0,0,0,0,1,2][Math.floor(Math.random()*10)];
}

function randomCase(){
  var n=Math.floor(Math.random()*100)
  switch(n){
    case n<80:
      return 0;
    case n<90:
      return 1;
    case n<100:
      return 2;
  }
}

function randomLoop(weight,num){
  var n=Math.floor(Math.random()*100),amt=0;
  for(var i=0;i<weight.length;i++){
    //amt+=weight[i]; *alternative method
    //if(n<amt){
    if(n<weight[i]){
      return num[i];
    }
  }
}

weight=[80,90,100];
//weight=[80,10,10]; *alternative method
num=[0,1,2]

Ответ 5

Как насчет

int [] numbers = {0, 0, 0, 0, 0, 0, 0, 0, 1, 2};

то вы можете случайным образом выбирать из чисел, а 0 будет иметь вероятность 80%, 1 10% и 2 10%

Ответ 6

Я использую следующие

function weightedRandom(min, max) {
  return Math.round(max / (Math.random() * max + min));
}

Это мой "взвешенный" случайный случай, когда я использую обратную функцию "x" (где x является случайным между min и max), чтобы генерировать взвешенный результат, где минимум является самым тяжелым элементом, и максимальный самый легкий (наименьший шанс получить результат)

Таким образом, использование weightedRandom(1, 5) означает, что шансы получить 1 выше, чем 2, которые выше, чем 3, которые выше, чем 4, что выше, чем 5.

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

После 100 итераций попробуйте, он дал мне:

==================
| Result | Times |
==================
|      1 |    55 |
|      2 |    28 |
|      3 |     8 |
|      4 |     7 |
|      5 |     2 |
==================

Ответ 7

Этот файл находится в Mathematica, но его легко копировать на другой язык, я использую его в своих играх и он может обрабатывать десятичные веса:

weights = {0.5,1,2}; // The weights
weights = [email protected]/[email protected] // Normalize weights so that the list sum is always 1.
min = 0; // First min value should be 0
max = weights[[1]]; // First max value should be the first element of the newly created weights list. Note that in Mathematica the first element has index of 1, not 0.
random = RandomReal[]; // Generate a random float from 0 to 1;
For[i = 1, i <= [email protected], i++,
    If[random >= min && random < max,
        Print["Chosen index number: " <> [email protected]]
    ];
    min += weights[[i]];
    If[i == [email protected],
        max = 1,
        max += weights[[i + 1]]
    ]
]

(Теперь я говорю, что индекс первого элемента списка равен 0). Идея заключается в том, что с нормализованным весом списка существует вероятность того, что веса [n] вернут индекс n, поэтому расстояния между минимумом и max на шаге n должны быть весами [n]. Общее расстояние от минимума min (которое мы считаем равным 0), а максимальное максимальное - суммой весов списка.

Хорошая вещь заключается в том, что вы не добавляете ни один массив или гнездо для циклов, и это значительно увеличивает время выполнения.

Вот код на С# без необходимости нормализации списка весов и удаления некоторого кода:

int WeightedRandom(List<float> weights) {
    float total = 0f;
    foreach (float weight in weights) {
        total += weight;
    }

    float max = weights [0],
    random = Random.Range(0f, total);

    for (int index = 0; index < weights.Count; index++) {
        if (random < max) {
            return index;
        } else if (index == weights.Count - 1) {
            return weights.Count-1;
        }
        max += weights[index+1];
    }
    return -1;
}

Ответ 8

здесь вход и отношения: 0 (80%), 1 (10%), 2 (10%)

позволяет вывести их, чтобы их легко визуализировать.

                0                       1        2
-------------------------------------________+++++++++

позволяет суммировать общий вес и называть его TR для общего соотношения. так что в этом случае 100. позволяет случайным образом получить число из (0-TR) или (от 0 до 100 в этом случае). 100 - это ваш вес. Назовите его RN для случайного числа.

так что теперь мы имеем TR как общий вес и RN как случайное число между 0 и TR.

то давайте представим, что мы выбрали случайный # от 0 до 100. Скажем 21. так что на самом деле 21%.

МЫ ДОЛЖНЫ СОКРАТИТЬ/СЧИТАТЬ ЭТО НА НАШИХ ВХОДНЫХ НОМЕРАХ, НО КАК?

позволяет перемещаться по каждому весу (80, 10, 10) и удерживать сумму весов, которые мы уже посещаем. момент, когда сумма весов, которые мы перебираем, больше, чем случайное число RN (в этом случае 21), мы останавливаем цикл и возвращаем эту позицию элемента.

double sum = 0;
int position = -1;
for(double weight : weight){
position ++;
sum = sum + weight;
if(sum > 21) //(80 > 21) so break on first pass
break;
}
//position will be 0 so we return array[0]--> 0

позволяет сказать, что случайное число (от 0 до 100) равно 83. Давайте сделаем это снова:

double sum = 0;
int position = -1;
for(double weight : weight){
position ++;
sum = sum + weight;
if(sum > 83) //(90 > 83) so break
break;
}

//we did two passes in the loop so position is 1 so we return array[1]---> 1

Ответ 9

Я предлагаю использовать непрерывную проверку вероятности и остальной части случайного числа.

Эта функция сначала устанавливает возвращаемое значение в последний возможный индекс и выполняет итерацию до тех пор, пока остальная часть случайного значения не станет меньше фактической вероятности.

Вероятности должны быть суммированы с одним.

function getRandomIndexByProbability(probabilities) {
    var r = Math.random(),
        index = probabilities.length - 1;

    probabilities.some(function (probability, i) {
        if (r < probability) {
            index = i;
            return true;
        }
        r -= probability;
    });
    return index;
}

var i,
    probabilities = [0.8, 0.1, 0.1],
    count = probabilities.map(function () { return 0; });

for (i = 0; i < 1e6; i++) {
    count[getRandomIndexByProbability(probabilities)]++;
}

console.log(count);

.as-console-wrapper { max-height: 100% !important; top: 0; }

Ответ 10

У меня есть slotmachine, и я использовал код ниже для генерации случайных чисел. В вероятностяхSlotMachine ключи являются выходными данными в slotmachine, а значения представляют вес.

const probabilitiesSlotMachine         = [{0 : 1000}, {1 : 100}, {2 : 50}, {3 : 30}, {4 : 20}, {5 : 10}, {6 : 5}, {7 : 4}, {8 : 2}, {9 : 1}]
var allSlotMachineResults              = []

probabilitiesSlotMachine.forEach(function(obj, index){
    for (var key in obj){
        for (var loop = 0; loop < obj[key]; loop ++){
            allSlotMachineResults.push(key)
        }
    }
});

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

const random = allSlotMachineResults[Math.floor(Math.random() * allSlotMachineResults.length)]

Ответ 11

8 лет с опозданием, но здесь мое решение в 3 строки.

1) Подготовить массив функции вероятности массы так, чтобы

pmf [array_index] = P (X = array_index):

var pmf = [0.8, 0.1, 0.1]

2) Подготовить массив для соответствующей кумулятивной функции распределения так, чтобы

cdf [array_index] = F (X = array_index):

var cdf = pmf.map((sum => value => sum += value)(0))
// [0.8, 0.9, 1]

3а) Генерация случайного числа.

3б) Получить массив элементов, которые больше или равны этому числу.

3c) Верните его длину.

cdf.filter(el => Math.random() >= el).length