Создайте массив случайных чисел с неравномерным распределением

Question

Я хочу написать Java-код для создания массива случайных чисел в диапазоне [1,4]. Длина массива равна N, которая предоставляется во время выполнения. Проблема заключается в том, что диапазон [1,4] не равномерно распределены:

Это означает, что если создать массивы с N = 100, число «1», будет появляться в среднем 40 раз в массиве , число «2» 10 раз и т. д.

Сейчас я использую этот код для создания единых распределенных случайных чисел в диапазоне [1,4]:

public static void main(String[] args) 
    { 
     int N; 
     System.out.println(); 
     System.out.print("Enter an integer number: "); 
     N = input.nextInt(); 
     int[] a = new int[N]; 
     Random generator = new Random(); 
     for(int i = 0; i < a.length; i++) 
     { 
      a[i] = generator.nextInt(4)+1; 
     } 
    } 

Как реализовать это с неоднородным распределением, как показано на графике выше?

Answer 1

Вот способ сделать это, начиная с кода:

public static void main(String[] args){ 
    int N; 
    System.out.println(); 
    System.out.print("Enter an integer number: "); 
    N = input.nextInt(); 
    int[] a = new int[N]; 
    Random generator = new Random(); 
    for (int i = 0; i < a.length; i++) { 
     float n = generator.nextFloat(); 
     if (n <= 0.4) { 
      a[i] = 1; 
     } else if (n <= 0.7) { 
      a[i] = 3; 
     } else if (n <= 0.9) { 
      a[i] = 4; 
     } else { 
      a[i] = 2; 
     } 
    } 
} 

UPDATE: по предложению @pjs', выберите числа в порядке вероятности desdencing, так что вы, как правило, выйти из, если блок ранее

Answer 2

Другим простым решением является использование nextDouble(), которое генерирует случайный двойник в [0,1]. Если значение равно < .4 выберите 1, иначе если < (.4 + .2) выберите 2 и т. Д., Причем последняя ветка всегда выбирает последний выбор. Это легко обобщается с помощью цикла for.

Answer 3

Пусть a1, a2, a3 и a4 быть двойники, которые определяют относительные вероятности и s = a1+a2+a3+a4 Это означает, что вероятность 1 является a1/s, вероятность 2 является a2/s ...

Затем создать случайный двойной д, используя generator.nextDouble().

Если 0 <= d < a1/s то целое число должно быть равно 1,

, если a1/s <= d < (a1+a2)/s то целое число должно быть 2

, если (a1+a2)/s <= d < (a1+a2+a3)/s то целое число должно быть 3

, если (a1+a2+a3)/s <= d < 1 то целое число должно быть 4

Answer 4

немного более расширяемая версия Miquel's (а также то, что предложила Тереза):

double[] distro=new double[]{.4,.1,.3,.2};   
    int N; 
    System.out.println(); 
    System.out.print("Enter an integer number: "); 
    Scanner input = new Scanner(System.in); 
    N = input.nextInt(); 
    int[] a = new int[N]; 
    Random generator = new Random(); 
    outer: 
    for(int i = 0; i < a.length; i++) 
    { 
     double rand=generator.nextDouble(); 
     double val=0; 
     for(int j=1;j<distro.length;j++){ 
      val+=distro[j-1]; 
      if(rand<val){ 
       a[i]=j; 
       continue outer; 
      } 
     } 
     a[i]=distro.length; 
    } 

Answer 5

Для более общего подхода, вы можете заполнить NavigableMap с вероятностью распределения:

double[] probs = {0.4, 0.1, 0.2, 0.3}; 
NavigableMap<Double, Integer> distribution = new TreeMap<Double, Integer>(); 
for(double p : probs) { 
    distribution.put(distribution.isEmpty() ? p : distribution.lastKey() + p, distribution.size() + 1); 
} 

, а затем запросить карту с равномерно распределенным случайным ключом в диапазоне [0, 1>:

Random rnd = new Random(); 
for(int i=0; i<20; i++) { 
    System.out.println(distribution.ceilingEntry(rnd.nextDouble()).getValue()); 
} 

Это заполнит карту со следующими парами ключ/значение:

Чтобы запросить карту, вы сначала генерируете равномерно распределенное двойное число в диапазоне от 0 до 1. Запрос карты с использованием метода ceilingEntry и передача случайного числа вернет "mapping associated with the least key greater than or equal to the given key", так, например, передача значения в диапазоне < 0,4, 0,5] вернет запись с отображением 0.5 -> 2. Использование getValue() на возвращаемой карте будет возвращаться 2.

Answer 6

Для конкретной проблемы, о которой вы говорили выше, решения, предоставляемые другими, работают очень хорошо, и alias method будет излишним. Однако, вы сказали в комментарии, что вы на самом деле собираетесь использовать это в дистрибутиве с гораздо большим диапазоном. В этом случае накладные расходы на настройку таблицы псевдонимов могут оказаться полезными для получения поведения O (1) для фактического создания значений.

Вот источник на Java. Это легко вернуть его обратно, используя запас в Java Random, если вы не хотите, чтобы захватить Вихрь Мерсенна:

/* 
* Created on Mar 12, 2007 
* Feb 13, 2011: Updated to use Mersenne Twister - pjs 
*/ 
package edu.nps.or.simutils; 

import java.lang.IllegalArgumentException; 
import java.text.DecimalFormat; 
import java.util.Comparator; 
import java.util.Stack; 
import java.util.PriorityQueue; 
import java.util.Random; 

import net.goui.util.MTRandom; 

public class AliasTable<V> { 
    private static Random r = new MTRandom(); 
    private static DecimalFormat df2 = new DecimalFormat(" 0.00;-0.00"); 

    private V[] primary; 
    private V[] alias; 
    private double[] primaryP; 
    private double[] primaryPgivenCol; 

    private static boolean notCloseEnough(double target, double value) { 
     return Math.abs(target - value) > 1E-10; 
    } 

    /** 
    * Constructs the AliasTable given the set of values 
    * and corresponding probabilities. 
    * @param value 
    * An array of the set of outcome values for the distribution. 
    * @param pOfValue 
    * An array of corresponding probabilities for each outcome. 
    * @throws IllegalArgumentException 
    * The values and probability arrays must be of the same length, 
    * the probabilities must all be positive, and they must sum to one. 
    */ 
    public AliasTable(V[] value, double[] pOfValue) { 
     super();  
     if (value.length != pOfValue.length) { 
     throw new IllegalArgumentException(
       "Args to AliasTable must be vectors of the same length."); 
     } 
     double total = 0.0; 
     for (double d : pOfValue) { 
     if (d < 0) { 
      throw new 
       IllegalArgumentException("p_values must all be positive."); 
     } 
     total += d; 
     } 
     if (notCloseEnough(1.0, total)) { 
     throw new IllegalArgumentException("p_values must sum to 1.0"); 
     } 

     // Done with the safety checks, now let's do the work... 

     // Cloning the values prevents people from changing outcomes 
     // after the fact. 
     primary = value.clone(); 
     alias = value.clone(); 
     primaryP = pOfValue.clone(); 
     primaryPgivenCol = new double[primary.length]; 
     for (int i = 0; i < primaryPgivenCol.length; ++i) { 
     primaryPgivenCol[i] = 1.0; 
     } 
     double equiProb = 1.0/primary.length; 

     /* 
     * Internal classes are UGLY!!!! 
     * We're what you call experts. Don't try this at home! 
     */ 
     class pComparator implements Comparator<Integer> { 
     public int compare(Integer i1, Integer i2) { 
      return primaryP[i1] < primaryP[i2] ? -1 : 1; 
     } 
     } 

     PriorityQueue<Integer> deficitSet = 
     new PriorityQueue<Integer>(primary.length, new pComparator()); 
     Stack<Integer> surplusSet = new Stack<Integer>(); 

     // initial allocation of values to deficit/surplus sets 
     for (int i = 0; i < primary.length; ++i) { 
     if (notCloseEnough(equiProb, primaryP[i])) { 
      if (primaryP[i] < equiProb) { 
       deficitSet.add(i); 
      } else { 
       surplusSet.add(i); 
      } 
     } 
     } 

     /* 
     * Pull the largest deficit element from what remains. Grab as 
     * much probability as you need from a surplus element. Re-allocate 
     * the surplus element based on the amount of probability taken from 
     * it to the deficit, surplus, or completed set. 
     * 
     * Lather, rinse, repeat. 
     */ 
     while (!deficitSet.isEmpty()) { 
     int deficitColumn = deficitSet.poll(); 
     int surplusColumn = surplusSet.pop(); 
     primaryPgivenCol[deficitColumn] = primaryP[deficitColumn]/equiProb; 
     alias[deficitColumn] = primary[surplusColumn]; 
     primaryP[surplusColumn] -= equiProb - primaryP[deficitColumn]; 
     if (notCloseEnough(equiProb, primaryP[surplusColumn])) { 
      if (primaryP[surplusColumn] < equiProb) { 
       deficitSet.add(surplusColumn); 
      } else { 
       surplusSet.add(surplusColumn); 
      } 
     } 
     } 
    } 

    /** 
    * Generate a value from the input distribution. The alias table 
    * does this in O(1) time, regardless of the number of elements in 
    * the distribution. 
    * @return 
    * A value from the specified distribution. 
    */ 
    public V generate() { 
     int column = (int) (primary.length * r.nextDouble()); 
     return r.nextDouble() <= primaryPgivenCol[column] ? 
        primary[column] : alias[column]; 
    } 

    public void printAliasTable() { 
     System.err.println("Primary\t\tprimaryPgivenCol\tAlias"); 
     for(int i = 0; i < primary.length; ++i) { 
     System.err.println(primary[i] + "\t\t\t" 
      + df2.format(primaryPgivenCol[i]) + "\t\t" + alias[i]); 
     } 
     System.err.println(); 
    } 
}