Flat Roulette with random number: get interval where random belongs to

Question

For example i have and array with such elements:

0 21 29 0 0 50

let's "flat" this numbers:

enter image description here

let's say my random number is 54, so my number belongs to the last element in my array with index 6 (it's 50)

i can't understand, how to algorytmize that... with c#

i try:

  Random random = new Random();
            int randomNumber = random.Next(1, 100);
            int temp, temp_ind;
            float a_, b_;
            for (j = 0; j < n-1; j++)
            {
                if (roulette[j] != 0)
                {
                    temp_ind = j+1;
                    a_ = roulette[j];
                    while ((roulette[temp_ind] == 0.0) && (temp_ind < n-1))
                    {
                        temp_ind++;
                    }
                    b_ = roulette[temp_ind];
                    if ((a_ <= randomNumber) && (b_ >= randomNumber))
                    {
                        start = j;
                        break;
                    }
                }
            }

but this doesn't work, maybe something could help me?

what is mem_? can you show how new_Gr and roulette are filled initialy, what your current outcome is and that you expect. This snippet itself doesn't compile, is it doable to have something that does? — rene, Jan 05 '14 at 21:13
@rene new_Gr is a matrix, where 0 - is that therre is not path between two edges, and !=0 - path cost; mem_ is never filled, just for remember next interval — Valdis Azamaris, Jan 05 '14 at 21:16
I am not quite clear about the expected behaviour. How can any random number ever be assigned to the bins with zero width? Or are they meant to never be assigned to? — Baldrick, Jan 05 '14 at 21:16
I'm confused, what if your random number is `0`, then what does it belong to? — poy, Jan 05 '14 at 21:17
@Baldrick didn't understand you. What i need is just generate random number, and check in with array interval it's lay's up — Valdis Azamaris, Jan 05 '14 at 21:17
Let's say all my interval is 100%, and i have three parts: 21% 29% 50%, and if i draw it, i will get as in question, but my main trouble is how to check, in which interval is my random — Valdis Azamaris, Jan 05 '14 at 21:19

score 2 · Accepted Answer · edited May 23 '17 at 12:19

Here's a solution which converts the array to a cumulative array (using an extension method from this answer by Eric Lippert), then finds the index of the first match in that array which is higher than the random number.

class Program
{
    static void Main(string[] args)
    {
        var random = new Random();
        int[] roulette = { 0, 21, 29, 0, 50 };

        var cumulated = roulette.CumulativeSum().Select((i, index) => new { i, index });
        var randomNumber = random.Next(0, 100);
        var matchIndex = cumulated.First(j => j.i > randomNumber).index;

        Console.WriteLine(roulette[matchIndex]);
    }
}

public static class SumExtensions
{
    public static IEnumerable<int> CumulativeSum(this IEnumerable<int> sequence)
    {
        int sum = 0;
        foreach (var item in sequence)
        {
            sum += item;
            yield return sum;
        }
    }
}

please edit code, so that it will be without 10000 test task. i will accept, just edit, also please simplify it, for example i have only array roulette[n] and some random number, now your code is to complicated — Valdis Azamaris, Jan 05 '14 at 22:24

Bernhard Barker · Answer 2 · 2014-01-05T21:42:47.440

1

You have hopelessly too many variables, overcomplicating the problem. Beyond the counter and the number, you only need one additional variable to keep track of the closest smaller number.

Below is some code I wrote which has essentially the same idea, it just seems a bit simpler.

int[] roulette = {0, 21, 29, 0, 0, 50};
int closest = -1;
int number = 54;
for (int j = 0; j < roulette.Length; j++)
   // if the values isn't 0 and it's smaller
   // and we haven't found a smaller one yet, or this one's closer
   if (roulette[j] != 0 && roulette[j] < number &&
       (closest == -1 || roulette[j] > roulette[closest]))
   {
      closest = j;
   }

if (closest == -1) // no smaller number found
   Console.WriteLine(0);
else
   Console.WriteLine(roulette[closest]);

Live demo.

For repeated queries, it would be better to sort the numbers, then do a binary search to find the correct position.

edited Jan 05 '14 at 21:42

answered Jan 05 '14 at 21:33

Bernhard Barker

54,589
14
104
138

just if (closest == -1) // no smaller number found Console.WriteLine(0); else Console.WriteLine(roulette[closest]); need i this ? – Valdis Azamaris Jan 05 '14 at 21:41
also when i find with else closest? maybe it's time to break; ? – Valdis Azamaris Jan 05 '14 at 21:44
Yes, you need that last if statement, or something similar. If you search for `14`, there's no smaller non-zero number, thus `closest` will be `-1` and you'll get an exception on `Console.WriteLine(roulette[closest]);`. And if you break as soon as you find one smaller value, you'll just find the first smaller value, not the closest one, i.e. you'll find `21` if given `54`, not `50`. – Bernhard Barker Jan 05 '14 at 21:45
If you search for 14, there's no smaller non-zero number, thus closest will be -1 how to be than? – Valdis Azamaris Jan 05 '14 at 21:50
hello )) how to be with -1 – Valdis Azamaris Jan 05 '14 at 22:09
I don't quite understand your last 2 comments. `closest` starts off at `-1`, so if you don't reassign it, it will still be `-1` at the end. Since it's an index, this is not a valid value. We need it to start off with an invalid value to indicate that we haven't found a value yet. – Bernhard Barker Jan 05 '14 at 22:47

Flat Roulette with random number: get interval where random belongs to

2 Answers2