I wrote a prioritized/weighted left shuffle algorithm (the code is copied from my open source C# project Fluent Random Picker).

What does that mean? You’ve got some values and each of them has a priority/weight (a number).
The higher the priority is, the higher are the chances of the value being far on the left after the shuffle.

The algorithm pretty much runs in linear time. It works with “stochastic acceptance” (see method RouletteWheelSelection).

But: It can get slower if one or multiple priorities are much higher than others. E.g. (1.000.000.000, 1, 1, 1, 1, 1, 1, 1). Why? Because the max is only calculated once (see first line in Shuffle) and calculating it n time would make the performance worse.

Any ideas for improvements? The best solution would be an always O(n) algorithm that can run in parallel, but especially the “parallel” part is probably not possible.

Idea 1: Using this O(n) algorithm to get the max values of some intervals (e.g. in an array with 1.000 priorities I get the largest value, the 100th largest, the 200th largest, … and the 900th largest) in the beginning and keep track of them to be able to replace one max priority with the next one as soon as there is no priority higher than the next one remaining.

Idea 2: Keeping track of the pairs[randomIndex].Priority / castedMax calculations in RouletteWheelSelection and if the last n results of that calculation are all lower than 0.000…, then the max will be re-calculated.

Idea 3: If n values need to be picked: Find out the nth highest value (possible in O(n), see idea 1) and the total max value. If max divided through the nth highest value is > some number (e.g. 10.000), use a different implementation (maybe this O(n * log(n)) implementation).

My code so far:

    /// <summary>
    /// Shuffles the first n elements and respects the probabilities in O(n) time.
    /// </summary>
    /// <param name="elements">The elements (value and probability) to shuffle.</param>
    /// <param name="firstN">Limits how many of the first elements to shuffle.</param>
    /// <returns>The shuffled elements.</returns>
    public IEnumerable<ValuePriorityPair<T>> Shuffle(IEnumerable<ValuePriorityPair<T>> elements, int firstN)
    {
        var max = elements.Max(v => v.Priority);

        var list = elements.ToList();
        var lastIndex = Math.Min(firstN, list.Count) - 1;
        for (int i = 0; i <= lastIndex; i++)
        {
            int randomIndex = RouletteWheelSelection(list, i, max);
            Swap(list, i, randomIndex);
        }

        return list;
    }

    private static void Swap<TElement>(IList<TElement> elements, int index1, int index2)
    {
        var tmp = elements[index1];
        elements[index1] = elements[index2];
        elements[index2] = tmp;
    }

    private int RouletteWheelSelection(IList<ValuePriorityPair<T>> pairs, int startIndex, int max)
    {
        var castedMax = (double)max;
        while (true)
        {
            var randomDouble = _rng.NextDouble();
            var randomIndex = _rng.NextInt(startIndex, pairs.Count);
            if (randomDouble <= pairs[randomIndex].Priority / castedMax)
                return randomIndex;
        }
    }