0

All done in C++. Let's say that I have two arrays:

int arrElem[]={1,2,3,4};
int arrPref[]={0,2,3,0};

arrElem is an array to elements from witch I must choose and an array of preference. The array of prefrence indicates, let's say, the percentage/10 of preference for it's corresponding element in elements array - with that I want to say:

  • element arrElem[0]=1 has no preference
  • element arrElem[1]=2 has 20% of preference
  • element arrElem[2]=3 has 30% of preference
  • element arrElem[3]=4 has no preference

the preference has no higher bound limit but if it's 10 or more, than it's corresponding element is automatically chosen. I can't seem to find a way to write a randomizer that would pick the element this way.

EDIT: to clarify how the chances are calculated for an object:

(100% - (sum of all preferences*10 in set )/ (number of elements in set))+(element preference*10) dont know really what to do with the situation when (sum of all preferences*10 in set ) is more then 100

Nordar
  • 187
  • 3
  • 14
  • What happens if there are multiple elements with preference 10 or higher? – Nobody moving away from SE Sep 26 '13 at 20:01
  • are you saying that 20% of the time, element 2 should be picked? – vlad Sep 26 '13 at 20:01
  • @Nobody - than random pick between them – Nordar Sep 26 '13 at 20:04
  • What is the base chance per element? Is 20% supposed to equal base + 20% or base * 1.2 value? Work out your proportions and then you can generate a random number of that range to determine what is the actual selected element. – StarPilot Sep 26 '13 at 20:04
  • @vlad - what i WOULD LIKE IT TO BE is that: normally, having 4 choices, the chance for each is 25%, then with preferences element 2 would have [100%-(20%+30%)/4]+20%=12.5%+20%=32.5% chance to be chosen – Nordar Sep 26 '13 at 20:09
  • 1
    Possible duplicate of [generating random number with a specific distribution in c](http://stackoverflow.com/questions/7304425/generating-random-number-with-a-specific-distribution-in-c). Possible alternatives include [Changing probability of getting a random number](http://stackoverflow.com/questions/8529665/changing-probability-of-getting-a-random-number), ['Chances' for a function to occur](http://stackoverflow.com/questions/18821783/chances-for-a-function-to-occur), and no doubt many others. – Jonathan Leffler Sep 26 '13 at 20:13
  • I think you're missing [] in the variables declarations (after the names) – Asaf Sep 26 '13 at 20:19
  • @Jakubs, if you know that, then why haven't you coded it already? You know the algorithm you need to apply to generate each element's chance. The particulars of implementing it should be simple now that you know your algorithm and how it works. – StarPilot Sep 26 '13 at 20:24

3 Answers3

2

You have to make a couple of iterations through your list. The first time you add up all of your "preferences," subtract that from 100, then figure out the rest of the percentages you add to every element. If you want to stick with ints, I guess I would choose a pretty high number for your "100%" like 1000000. So in your case above, you'd have 500,000 of preference, then your per-element gets (1,000,000 - 500,000) / num [4] = 125,000.

Now, pick a random number between 0 and your total percentage (again, 1,000,000 in this case) - 1 (i.e. 999,999).

Go through your list again. For each element, including the first, add the per-element amount and its preference amount. For element[0] your running total will be 125,000. If the random number you chose is < 125,000, then that is your pick. Otherwise, go on to the next element. Now our running total is 125,000 + 125,000 (every element) + 200,000 (this item's preference) or 450,000. If the random number you chose is < 450,000, then this is your pick.

You'd need a little extra logic to always pick the last item in case the math doesn't come out to exactly what your 100% number is.

keefer
  • 385
  • 2
  • 7
  • Your answer was most helpfull. Now im strugling with two other issues: -when the number of elements varies -when the substract of all preferences is less than 0 any hints? – Nordar Sep 26 '13 at 21:16
  • EDIT: okey, i've managed the situations when the number of elements varies. still no clue about the other one. – Nordar Sep 26 '13 at 21:23
  • I'm not sure what to tell you about all the prefs. I guess what I would do is add up all the preferences and normalize them to 100% so that they would at least in relation to each other be the same. So in the example of preferences {0, 1, 2, 3, 4, 5, 0}, your per-element amount would be 0, and your preference multiplier instead of being 100,000 (in the way I wrote it in my example) would instead be (1,000,000 / total_pref [15 here]) or 66666 per "preference". That would give you approximately the ratio of preferences relative to each other. – keefer Sep 26 '13 at 21:45
  • Basically, instead of making the preference amount constant (at 100,000 in my example), you're just calculating it dynamically. I guess the logic would be after the first loop, if preference <= 10, then calculate a per-element add-on. Otherwise, calculate a new per-preference amount and 0 out the per-element add-on. – keefer Sep 26 '13 at 21:50
  • Great help, thank you. Oh, and it's a part of for my Ant Colony Optimization algorithm implementation. More precisely the part where the ant chooses it's path - elements are graph nodes avalible to it in specific moment and preferences are pheromone values of the path to node. – Nordar Sep 26 '13 at 23:15
1

  1. Count number of elements in array = N.

  2. Count number of preferences (up to 10 allowed) = P.

  3. Create another array maintaining score for each element in the original array. The score is:

    (1-0.1*P)/N + (p*0.1)

    p being the element's preference (0..10)

  4. Integrate the score array so that Integrated[i]=sum(score[0]…score[i]

Now you're ready to work:

  1. Get a random number ,R, between 0 and 1
  2. Scan the integral array for the first entry greater or equal to R. Get its index i.
  3. Fetch element i from the elements array.

You got your probabilities.

The score/integral array is better be double or float or you can use a large (as much as possible) base, maybe multiply by 1M.... Note you don't really need to maintain the score array since you can integrate by summing each score without keeping the score.

Edit: If you want to use integers for the integral without loss of accuracy, you can change to the following:

In step 3: calculate the score like this: p*N + 10 - P

When drawing numbers: In step 1: Get random number R between 0 and 10N.

This will do the trick with integers WITHOUT LOSS OF ACCURACY!

Avi Perel
  • 422
  • 3
  • 8
0

So does in your scenario arrElement[1] has 2/5 chance of choosing and the third one 3/5?

I will assume so. You have to sum all the preferences (to pref_sum) and make a random variable between 0 and pref_sum-1. Then iterate through all preferences. If pref_sum-arrPref[i]<0 then choose ith element as a result; else subtract preference: pref_sum-=arrPref[i].

akrasuski1
  • 820
  • 1
  • 8
  • 25
  • no, because this way arrElem[0] and arrElem[4] has no chance to be picked. as i said in one of the comments above, the cance for arrElem[1]=2 is [100%-(20%+30%)/4]+20%=12.5%+20%=32.5% – Nordar Sep 26 '13 at 20:13