Generate random number with non-uniform density

Did someone know how to generate random numbers with a non-unif开发者_开发知识库orm density?

Easiest solution if applicable: Use C++11 random facilities or the ones from Boost, which have lots of non-uniform distributions for you.

Use a uniform density RNG, and pass its result through a mapping function to convert to your desired density distribution.

You should state what distribution you need. Basically, you use the inverse of the probability function you want. For example, the most common way to get normal distribution is Box-Muller transform.

Here is the code for Box-Muller just to get the idea:

float box_muller(float m, float s)  /* normal random variate generator */
{                       /* mean m, standard deviation s */
    float x1, x2, w, y1;
    static float y2;
    static int use_last = 0;

    if (use_last)               /* use value from previous call */
    {
        y1 = y2;
        use_last = 0;
    }
    else
    {
        do {
            x1 = 2.0 * ranf() - 1.0;
            x2 = 2.0 * ranf() - 1.0;
            w = x1 * x1 + x2 * x2;
        } while ( w >= 1.0 );

        w = sqrt( (-2.0 * log( w ) ) / w );
        y1 = x1 * w;
        y2 = x2 * w;
        use_last = 1;
    }

    return( m + y1 * s );
}

This class takes a distribution as a matrix (each row is a couple of a number and its frequency) and generates random numbers. So you can have Look at main method and run.

public class RandomGenerator {
    HashMap<Integer,Range> mappa = new HashMap<Integer,Range>();
    Random random = new Random();
    int max;




    public static void main(String as[]){ 
        int[][] matrice = new int[3][2];
        //number 5 occurs 5 times
        matrice[0][0] = 5 ;
        matrice[0][1] = 5 ;
        //number 18 occurs 18 times
        matrice[1][0] = 18 ;
        matrice[1][1] = 18 ;
        //number 77 occurs 77 times
        matrice[2][0] = 77 ;
        matrice[2][1] = 77 ;

        RandomGenerator randomGenerator = new RandomGenerator(matrice); 


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





    public int getNext(){
        int percentile = random.nextInt(max);
        Range r =mappa.get(percentile);
        return r.getValMax();
    }

    public HashMap<Integer, Range> getMappa() {
        return mappa;
    }

    public void setMappa(HashMap<Integer, Range> mappa) {
        this.mappa = mappa;
    }

    public RandomGenerator(int[][] distribuzioneOriginale ){
        ArrayList<Range> listaRange = new ArrayList<Range>();
        int previous = 0;
        int totaleOccorrenze = 0;
        for (int riga = 0; riga < distribuzioneOriginale.length; riga++) {

            Range r = new Range();
            r.setValMin(previous);
            r.setValMax(distribuzioneOriginale[riga][0]);
            r.setOccorrenze(distribuzioneOriginale[riga][1]);
            totaleOccorrenze += distribuzioneOriginale[riga][1];
            previous = distribuzioneOriginale[riga][0];

            listaRange.add(r);
        }



        int indice = 0;
        for (int iRange = 0; iRange < listaRange.size(); iRange++) {
            Range r = listaRange.get(iRange);

            int perc = (int) ( 1000* (r.getOccorrenze() / (double)  totaleOccorrenze)  )  ;

            for (int i = 0; i < perc; i++) {
                mappa.put( i + indice  , r);
            }
            indice += perc;
        }

        max = indice;

    }



    class Range{
        int valMin;
        int valMax;
        int occorrenze; 


        public int getValMin() {
            return valMin;
        }
        public void setValMin(int valMin) {
            this.valMin = valMin;
        }
        public int getValMax() {
            return valMax;
        }
        public void setValMax(int valMax) {
            this.valMax = valMax;
        }
        public int getOccorrenze() {
            return occorrenze;
        }
        public void setOccorrenze(int occorrenze) {
            this.occorrenze = occorrenze;
        }  

    }
}

In your comment in the question:

1/sqrt(2*pi) * e^(-x^2)

The only variable is x. x itself will have a uniform density. So just pick a good random number, then stick it into that equation.