Взвешенный выбор с ограничениями

У меня есть алгоритм взвешенного выбора, который работает, но я хотел бы улучшить его в двух аспектах (в порядке важности):

1. Гарантировать, что будет выбрано минимальное число из каждого возможного выбора.
2. Уменьшите вычислительную сложность с O (нм) до O (n) или O (m) , где n - запрошенное количество случайно выбранных элементов и m - это типы доступных элементов.

Изменить: Количество запрашиваемых номеров обычно мало (менее 100) для моих целей. Таким образом, алгоритмы со сложностью O (t) или O (t + n) , где t - общее количество элементов, обычно работают хуже, чем O (нм) из-за O (t) > O (m) .

Упрощенный код:

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Security.Cryptography;

public class Program
{
    static void Main(string[] args)
    {
        // List of items with discrete availability
        // In this example there is a total of 244 discrete items and 3 types, 
        // but there could be millions of items and and hundreds of types. 
        List<Stock<string>> list = new List<Stock<string>>();
        list.Add(new Stock<string>("Apple", 200));
        list.Add(new Stock<string>("Coconut", 2));
        list.Add(new Stock<string>("Banana", 42));

        // Pick 10 random items
        // Chosen with equal weight across all types of items
        foreach (var item in Picker<string>.PickRandom(10, list))
        {
            // Do stuff with item
            Console.WriteLine(item);
        }
    }
}

// Can be thought of as a weighted choice
// where (Item Available) / (Sum of all Available) is the weight.
public class Stock<T>
{
    public Stock(T item, int available)
    {
        Item = item;
        Available = available;
    }
    public T Item { get; set; }
    public int Available { get; set; }
}

public static class Picker<T>
{
    // Randomly choose requested number of items from across all stock types
    // Currently O(nm), where n is requested number of items and m is types of stock
    // O(n) or O(m) would be nice, which I believe is possible but not sure how
    // O(1) would be awesome, but I don't believe it is possible
    public static IEnumerable<T> PickRandom(int requested, IEnumerable<Stock<T>> list)
    {
        // O(m) : to calcuate total items,
        // thus implicitly have per item weight -> (Item Available) / (Total Items)
        int sumAll = list.Sum(x => x.Available);

        // O(1)
        if (sumAll < requested)
            throw new ArgumentException("Requested amount must not exceed total available");

        // O(1)
        Random rng = new Random(Seed());

        // O(n) for the loop alone : O(nm) total
        for (int n = 0; n < requested; n++)
        {
            // O(1) to choose an item : uses implicit ordering
            int choice = rng.Next(1, sumAll);
            int current = 0;

            // O(m) to find the chosen item
            foreach (Stock<T> stock in list)
            {
                current += stock.Available;

                if (current >= choice)
                {
                    yield return stock.Item;

                    // O(1) to re-calculate weight once item is found
                    stock.Available -= 1;
                    sumAll--;

                    break;
                }
            }
        }
    }

    // Sufficiently random seed
    private static int Seed()
    {
        byte[] bytes = new byte[4];
        new RNGCryptoServiceProvider().GetBytes(bytes);
        return bytes[0] << 24 | bytes[1] << 16 | bytes[2] << 8 | bytes[3];
    }
}

Функция PickRandom () использует yield return и IEnumerable , но это не обязательно. Когда я впервые написал функцию, я просто пытался проявить смекалку, чтобы она могла выполнять итерацию по чему угодно (даже, скажем, перечислимому элементу из запроса LINQ to SQL). Впоследствии я обнаружил, что, хотя гибкость и хороша, мне она никогда по-настоящему не нужна.

Моя первая мысль при решении вопроса № 1 (гарантия того, что выбрано минимальное число из каждого возможного выбора) заключалась бы в выборе необходимого минимума из каждого введите совершенно неслучайным образом, используйте мой существующий алгоритм, чтобы выбрать оставшуюся неограниченную часть, а затем перемешайте результаты вместе. Это казалось наиболее естественным и имитирует то, как я бы сделал что-то подобное в реальной жизни, но я думаю, что это не самый эффективный способ.

Моя вторая идея заключалась в том, чтобы сначала создать массив результатов, случайным образом выбирая индексы для заполнения сначала требуемые минимумы, а затем заполните остальные, используя мой существующий алгоритм, но во всех моих попытках это приводило к увеличению сложности "большого О" или к большому беспорядку индексов, записываемых повсюду. Я все еще думаю, что этот подход возможен, я просто еще не смог его проработать.

Затем решил прийти сюда, так как эта проблема кажется, что ее можно абстрагировать до довольно общего алгоритма, но все ключевые слова я использование для поиска обычно указывает мне на генерацию базовых взвешенных случайных чисел (в отличие от выбора отдельных элементов, сгруппированных по типу с определенной доступностью). И не удалось найти ничего, что ограничивало бы проблему минимальным выбором для каждого типа элемента, оставаясь при этом случайным. Так что я надеюсь, что либо кто-то со знанием дела сможет найти простое эффективное решение, либо кто-то, кто слышал об этой проблеме раньше, знает несколько ключевых слов лучше, чем я, и может указать мне правильное направление.