It's a slot machine game. We already know the number of different outputs. But it needs to work on any kind of variations of that table, obviously.

So far, I have tried several naive approaches:

• Dumping all results in an array and try to distribute them by moving along the array.
• Tried to insert elements one by one, finding an empty and 'periodic' slot for each element.

Output Table Image

Examples Image

I use indexes of rows data to create and distribute array elements periodically. (eg: first row corresponds to value 0, second row corresponds to value 1 and so on..)

So my output array will consist elements from 0 to 10 and the size will be 100 for provided table.

EDIT: I have deleted the old code because I come up with an actual solution. Unfortunately I'm not sure if it is the correct/optimum way and has no idea how to check it.

Here is my code: https://goonlinetools.com/snapshot/code/#ng5xi35uewbrgc40avciud

Here are the sample result

Can someone maybe check my code and verify that I have the correct result?

CodePudding user response：

So, you want a pool where each possibility happens a fixed amount of times, before refilling the pool. What you can do is make an array of integers, each index corresponding to the result, and each value being the probability. Then, you create an integer that stores the sum of all probabilities. When you want an item, create a number between 1 and the sum of probabilities (inclusive). Go down the array, subtracting the probability from the random number. When it is <= 0, that is your random choice. To remove from the pool, subtract 1 from the chance of what you landed on, and 1 from the sum. When the sum is zero, that means the pool is empty and can be refilled. Here is an example in c#:

class RandomPool {
    private int[] chances;
    public int Total {get; private set;} // total pooled items
    public readonly int Length;
    public int this[int i] {
        get => chances[i]; // get the chance at an index
        set {
            Total  = value - chances[i]; // updates the total
            chances[i] = i; // sets the chance at an index
        }
    }
    public RandomPool(int length) {
        chances = new int[length];
        Length = length;
    }
    public int Get() {
        // creates a random number 1-total
        int rand = Random.Range(1, total   1);
        int i = 0;
        // loops through the chances 
        while (true) {
            // decreases the random value by the change
            rand -= chances[i];
            // if it is <= 0
            if (rand <= 0)
                return i; // return the index of the chosen item
            i  ;
        }
    }

Then you can use it like this:

var pool = new RandomPool(3); // create the pool
pool[0] = 5; // assign the chances
pool[1] = 2;
pool[3] = 3;
while (pool.Total > 0) { // while there is something in the pool
    int x = pool.Get(); // get an item
    Console.WriteLine($"Randomly chose index: {p}"); // log the result
    pool[x]--; // remove one from the pool
}

When pool.Total == 0 you can refill the pool. Also, I haven't tested this code, so there might be a few errors.

CodePudding user response：

Here is a way to get this. I will start with the inspiration, and then add how to do it efficiently.

Imagine you have a series of alarm clocks in front of you. 5 of them go off 13x per day. The rest go off 9, 8, 7, 6, and 5 times per day. (I chose this example to match your output table image.) Each starts a random point between when it last went off and when it next goes off.

The answer you want is the order in which they go off. This order is periodic - it repeats every day. They also go off in exactly the right proportions every day. But the random start makes them go off randomly.

Now how do we figure this out efficiently? The idea is to use a PriorityQueue to track when each alarm clock goes off. So we'll want something like a Record(double priority, String result, double weight) to put into our queue. Our result field will be your string description, the weight will be your 13 or whatever, and using Random you'll start priority at rand.nextDouble() / weight. The priority queue will compare based on priority.

And now the heart of the loop where you you populate your array will be:

QueueItem qi = queue.poll();
answer.add(qi.result);
queue.offer(QueueItem(qi.priority   1/qi.weight, qi.result, qi.weight);

This makes each array item take time O(log(queue.size())) to produce. And you see that every qi.weight times qi.result comes up, the priority increases by 1. (So it is periodic.)