FORUMS
Remove All Ads from XDA

[Q] choose array-elements with certain probability

57 posts
Thanks Meter: 8
 
By RazorHail, Member on 30th November 2010, 10:24 PM
Post Reply Email Thread
hello,
I'm writing a Android App (java) - but I guess this question is pretty general, and isn't java-specific:

so I have an Array of Elements

and I let a random-number-generator pick one array-element randomly and hand it to me.

now I've also built in a "score"-field into each array Element

so what I want to do now, is that the random-number-generator takes the array's "score" in consideration, and gives me the array-elements with the higher/lower scores with a higher/lower probability


I dont want it to ALWAYS/NEVER give me the elements with the highest/lowest score - just with a higher/lower probability


I hope I could describe my problem in a proper way....

does anybody know how to achieve this?
(as I said, i use java, but i guess code in any language - or even pseudo-code would help me out)
 
 
1st December 2010, 10:07 AM |#2  
OP Member
Thanks Meter: 8
 
More
*bump*

anybody?
1st December 2010, 01:17 PM |#3  
stephj's Avatar
Inactive Recognized Developer
Flag Lancashire
Thanks Meter: 104
 
10
More
Try this, it's in C# but it's pretty close to Java.

You cannot directly weight the random function so you have to use a different method.
By applying a weight to each item in the array, then using a random function to select using the weighting values, the results of the selection can be swayed.

The weighting values are relative to each other.

Using the values in the code, 'B' should turn up about three times more often than 'A'

The only object that may need some explanation is Random:

http://msdn.microsoft.com/en-us/libr...(v=VS.80).aspx

Code:
using System;

namespace RandomWeighting
{
    class Program
    {
        static void Main(string[] args)
        {

        char[] Select =  new char[10] {'A','B','C','D','E','F','G','H','I','J'};
        int[] Weight = new int[10]  {10,30,25,60,20,70,10,80,20,30};
        int[] WeightSum = new int[10];

        int i,j,k;
        Random Rnd = new Random();

        WeightSum[0]=Weight[0];

        for (i = 1; i < 10; i++)
            WeightSum[i] = WeightSum[i - 1] + Weight[i];

        for (j = 0; j < 70; j++)
        {
            k = Rnd.Next(WeightSum[9]);

            for (i = 0; k > WeightSum[i]; i++) ;

            Console.Write(Select[i]);
        }
        Console.WriteLine();
        }
    }
}
Output:
Code:
HEFIBHHCCFBCAEFFDHACHBEJHHFDFIDFEDFFCHHDJBIDJEHHFHCJJJBHJGBDDGFDDFHHHB
Note the low density of A and G as opposed to H

It is just a sample at random, but 2 'A's and 7 'B's roughly matches the conjecture above, but over a million selections, the distribution is as follows:
Code:
A  30664
B  84187
C  70648
D  168481
E  56529
F  197311
G  28145
H  225764
I  56613
J  81658
If your code changes values in the Weight array then the WeightSum array must be recalculated.
The Following User Says Thank You to stephj For This Useful Post: [ View ] Gift stephj Ad-Free
1st December 2010, 07:50 PM |#4  
OP Member
Thanks Meter: 8
 
More
wow, thats a lot!

The only thing I dont understand about the code is this line:

k = Rnd.Next(WeightSum[9]);

for (i = 0; k > WeightSum[i]; i++) ;

what exactly happens here?
what kind of a for-loop is this?
why is there no body?
and strangely, while debugging this line, i noticed that the value of i jumps to some random number in this line - and I have no idea why and how


------

by the way: I've already tried it out, it works pretty good.
although I noticed that the first element always gets picked ALOT, no matter how low the weight.
I think thats a flaw in the algorithm
2nd December 2010, 11:45 AM |#5  
stephj's Avatar
Inactive Recognized Developer
Flag Lancashire
Thanks Meter: 104
 
10
More
After the following code:
Code:
        for (i = 1; i < 10; i++)
            WeightSum[i] = WeightSum[i - 1] + Weight[i];
The WeightSum array contains the following values:
Code:
[0]	10
[1]	40
[2]	65
[3]	125
[4]	145
[5]	215
[6]	225
[7]	305
[8]	325
[9]	355

The Random.Next() function that takes a single integer as an argument is defined as:

-------- Courtesy of MS VS .NET Help ------

public virtual int Next(int maxValue)

Parameters maxValue Type: System.Int32
The exclusive upper bound of the random number to be generated. maxValue must be greater than or equal to zero.

Return Value Type: System.Int32
A 32-bit signed integer greater than or equal to zero, and less than maxValue; that is, the range of return values ordinarily includes zero but not maxValue. However, if maxValue equals zero, maxValue is returned.

-------------- End of Help ----------------



So, we are asking for a random value between 0 and 354,(element WeightSum[9] above). The following code then finds which is the lowest element of WeightSum which holds a value greater than the one we have been given. When this happens 'i' contains the index to use for the selection.

Code:
for (i = 0; k > WeightSum[i]; i++);
The standard construction of a for loop in C is

for(One or more initialisation statements; Do_While_True Condition; One or more iteration statements)
{
loop processing code;
}

If there is nothing to do in the loop body, you don't need it, and you can replace it with the ';' at the end of the for statement. In effect, it is identical to the following code:-
Code:
i=0;
while(k > WeightSum[i])
  {
    i++;
  }
As regards the first element being picked more than the others, have a look at the distribution table in post #3. It is what you would expect for the values given. I assume the difference is either the Random function in Java or some different implementation between C# and Java.

You may have to change some of the code slightly, i.e. change the for() loop to the while() loop above and step though it in the Java debugger to get to the root of the problem.

You can't debug a for loop followed by an immediate ';' The entire for loop is executed to completion when you use debug and try and step through it. To debug it place a dummy statement in the for loop. A breakpoint may now be set on this line.

Code:
int i,z;

for (i = 0; k > WeightSum[i]; i++)
{
 z=0;
}
The Following User Says Thank You to stephj For This Useful Post: [ View ] Gift stephj Ad-Free
23rd August 2011, 01:36 AM |#6  
Junior Member
Thanks Meter: 0
 
More
Lightbulb ActionScript and Javascript versions ...
Thanks for the great write-up! In case anyone is interested, I've adapted this into a javascript and ActionScript class. If anyone is interested, I've attached the code. For a more in-depth post, check out blog.teamthinklabs.com.

Cheers!

Kipp Ashford
Art Director
Seven2 Interactive
Post Reply Subscribe to Thread

Guest Quick Reply (no urls or BBcode)
Message:
Previous Thread Next Thread
Thread Tools Search this Thread
Search this Thread:

Advanced Search
Display Modes