Looking for a Library that handles probability.

[Jeeves]

Hi everybody. I've succeeded in creating a function that picks a random sequence of specific numbers from an array.
The order of the numbers in the array are sorted/randomised using rand() and a basic sort function. Then I use rand() to generate a value for the array pointer in a for loop, to select a pseudo-random element.Problem is: I want to reduce the chance of a specific number being randomly picked.

I realised that the way I've picked the series so far is probably a bit backward, seeing as there's probably a library of functions that does stuff like this somewhere: you pass this function some values, it randomly orders them; it can also pick a biased order favouring certain numbers.

Figured it's better to ask here first before trawling the net.

Thanks in advance

[Garrador]

You could write a sort of "score" system, and store these numbers in a dictionary with their score as the second dimension. Then let the scoring system evalute a number's score.

Might be too much for a simple thing, but if you're creating an app that i.e: shuffles a playlist randomly, but selects the songs you listen most to, more frequently.

Probability on its own isn't really hard to create some functions for. Either way, there are obviously tons of probability and such out there. I.e: http://biology.nmsu.edu/software/probability/

[stoopdapoop]

I'm really confused about what you need.

From your descriptions It sounds like you may have a shuffled array of n values, you want n-1 of those values to have an equal chance of being selected as the next element, and you have a single value where you want the chance to be lower.

if I'm understanding you correctly, then you aint need no fancy schmancy library. All you need to do is generate your random index as you were before, but make sure to check the value stored at your randomly indexed location. If it's the one that you want to be more rare, then you simply generate another random number, and do an inequality check that only passes for some subset of valid range of randomly generatable numbers. If the inequality check passes, then return the "rare" value. If it doesn't pass, then reroll.

this isn't really a "good" solution because if you roll to your "rare" number, and have it fail the second test several times in a row then it can take longer. But it's very unlikely that the same value will get selected more than once in a row.

[Jeeves]

Argh goddam It!. Just re-read my post and could of sworn it made more sense last night.

From your descriptions It sounds like you may have a shuffled array of n values, you want n-1 of those values to have an equal chance of being selected as the next element, and you have a single value where you want the chance to be lower.

Yes that's right Stoop. Thanks man, I can get this to work now; didn't realise it was that simple.

I just see all the for loops and arrays and think I'm doing things inefficiently, the 'C way'. Like most people I'd just prefer a nice #include, rather then pages of for loops, arrays, or even worse: case statements.

Garrador, the library link made for interesting reading, it will probably come in useful if this becomes slightly more complicated.

If there is a function somewhere that takes a series of numbers, and some user defined probabilities for picking each number, as its arguments, and spits out a random series of those numbers, hit me up.

I'll bug you both some more if something unexpected comes up.

[zombie@computer]

Argh goddam It!. Just re-read my post and could of sworn it made more sense last night.

From your descriptions It sounds like you may have a shuffled array of n values, you want n-1 of those values to have an equal chance of being selected as the next element, and you have a single value where you want the chance to be lower.

Yes that's right Stoop. Thanks man, I can get this to work now; didn't realise it was that simple.

I just see all the for loops and arrays and think I'm doing things inefficiently, the 'C way'. Like most people I'd just prefer a nice #include, rather then pages of for loops, arrays, or even worse: case statements.

Garrador, the library link made for interesting reading, it will probably come in useful if this becomes slightly more complicated.

If there is a function somewhere that takes a series of numbers, and some user defined probabilities for picking each number, as its arguments, and spits out a random series of those numbers, hit me up.

I'll bug you both some more if something unexpected comes up.

Code: Select all

std::vector<float> RandSequence(std::vector<float> srcArray, int maxAmount, bool allowDuplicates, std::vector<float> probabilities = std::vector<float>())
{
   float rndSelector = 0;
   std::vector<float> probs = std::vector<float>(srcArray.size());
   std::vector<float> outp = std::vector<float>(maxAmount);

   if (probabilities.size() == 0)
   {   
      rndSelector = (float)srcArray.size();
      for(float x = 0; x < rndSelector; x++)
         probs[(int)x] = x;
   }
   else
   {   
      for(unsigned x = 0; x < srcArray.size(); x++)
      {
         probs[x] = rndSelector;
         rndSelector += probabilities[x];
      }
   }

   for( int x=0; x < maxAmount; x++)
   {
      int y = probs.size()-1;
      float r = Rand(rndSelector);
      for( ; y >= 0; y --)
      {
         if (r > probs[y])
         {
            outp[x] = srcArray[y];
            if (!allowDuplicates)
            {
               if (y == probs.size()-1)
               {
                  if (probs.size()== 1)
                  {
                     outp.resize(x);
                     return outp;
                  }
                  rndSelector = probs[y];
                  probs.erase(probs.begin() + y);
                  srcArray.erase(srcArray.begin() + y);
               }
               else
               {
                  float l = probs[y+1] - probs[y];
                  probs.erase(probs.begin() + y);
                  srcArray.erase(srcArray.begin() + y);

                  while(y < probs.size())
                     probs[y++] -= l;
                  rndSelector -= l;
               }
            }
            break;
         }
      }
      if (y == -1)
      {
         outp.resize(x);
         return outp;
      }
   }
   return outp;
}


Bit rusty in C++, but this should do:

Code: Select all

srand(239835384);

std::vector<float> numbers(6);
numbers[0] = 1;
numbers[1] = 2;
numbers[2] = 3;
numbers[3] = 4;
numbers[4] = 5;
numbers[5] = 6;

std::vector<float> probabilities(6);
probabilities[0] = 1;
probabilities[1] = 10;
probabilities[2] = 5.5f;
probabilities[3] = 1;
probabilities[4] = 6.0f;
probabilities[5] = 1;

RandSequence(numbers, 1000, true, probabilities);//Generate 1000 numbers from 'numbers' , using preset probabilities

RandSequence(numbers, 50, true);//Generate 50 numbers from 'numbers' , with equivalent probabilities
RandSequence(numbers, 50, false);//Same, but once a number has been generated, remove it from the possible draws.

Returns a vector with x amount of numbers, which may be less than the maxAmount passed if the third parameter is false and the sourcearray ran out of items to draw



[Jeeves]

Thanks for that Zombie, that must have taken some time, I appreciate it. The problem I'm having with that code is that when I compile, I get an error in stdlib.h saying that rand() has too many arguments.

float r = rand(rndSelector);

Code: Select all

 _CRTIMP int __cdecl __MINGW_NOTHROW   rand   (void); // what comes up in stdlib.h

Thanks in advance

[zombie@computer]

ah yeah, forgot that part

Code: Select all

float Rand(float max)
{
   return (float)rand()/((float)RAND_MAX/max);
}

stdlib doesnt have a random float generator. Now it has (or at least an approximation to one)