Weighted Random Selection

You can use cumulative frequency:

x random in [0:100) (or closed interval, can''t remember which is correct)

if x < 25 then 1
if x < 30 then 2
if x < 60 then 3
...

which is essentially the same as your method, just (slightly) more concise.

NOTE: I wasn''t advocating use of if combs, it was a specific case of a general algorithm (i.e. a specific case of the APs).

Speed is unlikely to be an issue, so choose the simplest to code.

A method I use is a class I call WeightedTable. I initialize a WeightedTable with an array of integers representing the relative weights of each of the entries. I can call a WeightedTable:Choose() method to obtain one of the choices.

Here is a sample implementation off the top of my head; note that it could be improved immensely, but I'm too lazy to look up my actual implementation.

class WeightedTable
{
    int NumEntries;
    int *EntryTable;
    int MaxWeight;
    
public:
    WeightedTable(){EntryTable=NULL;};
    ~WeightedTable(){if(EntryTable) delete[] EntryTable;};
    
    void InitTable(int NEntries);
    void SetTable(int NEntries, int *Entries);
    int Choose(); // Return index of randomly selected entry

};


void WeightedTable::InitTable(int NEntries)
{
 
 NumEntries=NEntries;
 if(EntryTable) delete[] EntryTable;
 EntryTable=new int[NEntries];
}

void WeightedTable::SetTable(int NEntries, int *Entries)
{
 // Initialize from array

 // If not allocated, allocate now

 // If resizing, re-allocate

 if(!EntryTable || NEntries != NumEntries) InitTable(NEntries);
 
 // Now, cycle through table, setting weights

 int c;
 int wt;
 
 wt=0;
 for(c=0;c<NEntries;c++)
 {
    wt+=Entries[c]; // Each successive weight is a cumulative

                    // sum of the preceding weights

    EntryTable[c]=wt;
 }
 
 MaxWeight=wt;
}

int WeightedTable::Choose()
{ // Return index of randomly selected entry


    int Rnd;
    
    Rnd=RandRange(1, MaxWeight);
    
    int c;
    for(c=0;c<NumEntries;c++)
      if(Rnd<=EntryTable[c])
      {
       return c;
      }
      
    return -1; // Failure?

}

Since all weights are relative to each other, you can create arbitrarily high or low biases. For instance: {1000,1000,10000, 1}. In this case, Choose() would have a 1000/12001 chance of selecting element 0, but only a 1/12001 chance of selecting element 3. (Roughly).
If at some point you wish to set the chance of an element's selection to 0, just set it's weight to 0. As long as at least 1 element in the table is non-zero, it will function correctly. I find this handy for debugging purposes.

Anyway, hope this helps

Josh
vertexnormal AT email DOT com

Check out Golem at:
www.angelfire.com/rpg2/vertexnormal

[edited by - VertexNormal on July 23, 2003 2:09:33 AM]

Thank you everyone for your replies! I think I will indeed make a class based off of the suggestions of everyone. That seems like the best way to do it. Thanks again!

[edited by - UBC_Wiskatos on July 23, 2003 2:00:24 PM]