Weighted Random Algorithms

Weighted Random 1:
(Requires you know the sum of all the weights)
Expensiveness: 2n+r;

function Object WeightedRandom(ArrayList<Object> objects){
    float sum = getWeightSums(objects);
    float selected = (new Random()).nextFloat() * sum;
    float upTo = 0f;
    for(Object object : objects){
        if(selected < upto + object.weight){
            return object;
        }
    }
}



Weighted Random 2:
(Requires all the weights are between 0 and 1)
Expensiveness: n*r;


function Object WeightedRandom(ArrayList<Object> objects){
    for(Object object : objects){
        if((new Random()).nextFloat() <  object.weight){
            return object;
        }
    }
}

Weighted Random 3:
(Assumes you know the Max of all the weights)
Expensiveness: n+n*r

function Object WeightedRandom(ArrayList<Object> objects){
    float max = getWeightMax(objects);
    for(Object object : objects){
        if((new Random()).nextFloat()*max < object.weight){
            return object;
        }
    }
}