Корректируйтесь объекты оказываются выбранный из списка

Используйте взвешенную по сегменту очередь: Вместо использования списка разделите вашу коллекцию на сегменты - каждому сегменту соответствует частота извлечения. По мере выбора элементы перемещаются из сегментов с более высокой частотой в сегменты с меньшей частотой.

Простой способ реализовать это - назначить каждому сегменту диапазон значений и сгенерировать случайное число в объединенном диапазоне, чтобы выбрать сегмент для выбора . Вы, вероятно, захотите абстрагировать эту коллекцию в какой-то класс, чтобы не раскрывать потребителям детали.

Алгоритм:

Изначально все элементы начинаются в одной корзине (верхнего уровня).

Когда вы выбираете элемент, переместите его из ведра, в котором он находится, в следующее нижнее ведро. При необходимости создайте сегмент следующего уровня.

Когда добавляется новый элемент, добавьте его в самую верхнюю (наиболее часто используемую) корзину.

Чтобы случайным образом выбрать элемент, сначала выберите ведро, затем выберите элемент в ведре. Переместите выбранный элемент вниз в корзину следующего уровня. Обратите внимание, что перемещение элемента вниз в сегмент с более низкой частотой является необязательным - вы можете установить некоторую точку отсечки.

При создании нового сегмента обновите диапазон извлечения, связанный со всеми сегментами, чтобы придать новому набору желаемую характеристику частотного распределения. .

Реализация на C # (первый вариант) общей взвешенной очереди с разделением на сегменты:

using System;
using System.Collections.Generic;
using System.Linq;

namespace Utility
{
    public class BucketWeightedQueue<T>
    {
        private int m_MaxFallOff;
        private readonly double m_FallOffRate;
        private readonly List<List<T>> m_Buckets;
        private readonly List<int> m_FallOffFactors;
        private readonly Random m_Rand = new Random();

        public BucketWeightedQueue(IEnumerable<T> items, double fallOffRate )
        {
            if( fallOffRate < 0 ) 
                throw new ArgumentOutOfRangeException("fallOffRate");

            m_MaxFallOff = 1;
            m_FallOffRate = fallOffRate;
            m_Buckets = new List<List<T>> { items.ToList() };
            m_FallOffFactors = new List<int> { m_MaxFallOff };
        }

        public T GetRandomItem()
        {
            var bucketIndex = GetRandomBucketIndex();
            var bucket = m_Buckets[bucketIndex];
            var itemIndex = m_Rand.Next( bucket.Count );
            var selectedItem = bucket[itemIndex];

            ReduceItemProbability( bucketIndex, itemIndex );
            return selectedItem;
        }

        private int GetRandomBucketIndex()
        {
            var randFallOffValue = m_Rand.Next( m_MaxFallOff );
            for (int i = 0; i < m_FallOffFactors.Count; i++ )
                if( m_FallOffFactors[i] <= randFallOffValue )
                    return i;
            return m_FallOffFactors[0];
        }

        private void ReduceItemProbability( int bucketIndex, int itemIndex )
        {
            if( m_FallOffRate <= 0 )
                return; // do nothing if there is no fall off rate...

            var item = m_Buckets[bucketIndex][itemIndex];
            m_Buckets[bucketIndex].RemoveAt( itemIndex );

            if( bucketIndex <= m_Buckets.Count )
            { 
                // create a new bucket...
                m_Buckets.Add( new List<T>() );
                m_MaxFallOff = (int)(m_FallOffFactors[bucketIndex] / m_FallOffRate);
                m_FallOffFactors.Add( m_MaxFallOff );
            }

            var nextBucket = m_Buckets[bucketIndex + 1];
            nextBucket.Add( item );

            if (m_Buckets[bucketIndex].Count == 0) // drop empty buckets
                m_Buckets.RemoveAt( bucketIndex );
        }
    }
}

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

По умолчанию весовой коэффициент равен 1, когда вы добавляете элемент, и сохраняете (в «списке») сумма всех весов всех элементов.

Затем, когда вы выбираете элемент случайным образом, вы можете просто выбрать число от 0 до общего веса всех элементов в списке, и пройдите по списку, чтобы найти элемент в этой «позиции» (путем взвешивания). Уменьшите вес этого элемента (это может быть некоторый спад, например: умножьте его вес на 0,8 или 0,5 - у вас будет большой контроль над тем, насколько быстро падает вероятность выбора) и верните его.

Обратной стороной здесь является то, что если у вас много элементов, вы выбираете O (n) (поскольку вам нужно пройтись по списку). Из-за этого я

Все зависит от того, как должна изменяться вероятность выбора при выборе данного элемента.

Простой способ добиться этого - двойное рисование, при котором вы начинаете со списка ввода ( который никогда не изменяется) и пустой список, в который вы добавляете произвольно выбранные элементы. После каждого обычного розыгрыша (из первого списка) вы берете один элемент из второго списка. Если тот же самый элемент (или, скорее, значение предмета) появляется снова, он не выбирается (т. Е. Недействительный отрисовка, начать заново), в противном случае подсчитывается отрисовка и соответствующее значение добавляется во второй список.

Общая концепция кажется связанной с эргодические источники.

DigitalJoe прокомментировал очевидный недостаток этого подхода. Вкратце, Джо отметил, что вероятность предотвращения повторения (не обязательно последовательных повторов, просто «повторения» ) значение ранее нарисованного элемента (значение, найденное во втором списке алгоритма) сильно колеблется в первых нескольких сотнях рисунков. Другой неявный комментарий заключался в том, что после того, как второй список содержит несколько десятков значений, вероятность предотвращения такого дублирования чрезвычайно мала. Оба эти аргумента являются действительными и требуют квалификации.

Это рассуждение соответствует нашему интуитивному пониманию того, как работает второй список: чем больше значений элементов там, тем меньше шансов, что у нас есть «двойная вытяжка», следовательно, чтобы предотвратить повторение. Это правда, но мы сосредоточимся только на втором списке. Необходимо учитывать вероятность получения [из первого списка] ранее увиденного предмета. Мы можем использовать два примера, чтобы понять эту идею, но это, конечно, градиент:

• Случай «A»: Вероятность получения данного значения элемента относительно мала по сравнению с вероятностью получения чего-либо другого. Комбинированная вероятность того, что этот предмет будет вытягиваться несколько раз в течение первых нескольких розыгрышей, поэтому мала, и вероятность того, что вы это сделаете, а затем выбросите его из-за розыгрыша (ов) в списке два, еще ниже (даже если последняя вероятность может быть высокая из-за небольшого количества элементов во втором списке).
• Случай «B»: вероятность вытягивания данного предмета высока по сравнению с вероятностью вытягивания других предметов. В этом случае вероятность наличия повторов в первых нескольких розыгрышах высока, и поскольку вероятность предотвращения фактического повтора (с розыгрышем во втором списке) также высока (достоверность для 2-го розыгрыша, вероятность 50% на втором розыгрыше ... шанс 10% на 11 розыгрыше), общая вероятность "наказать" весьма вероятный предмет высока. Однако это не проблема, потому что относительная вероятность рисования элемента из первого списка гарантирует, что будет, статистически, много других возможностей для создания дубликатов, которые не будут так «принудительно» подавляться по мере увеличения количества рисунков. .

В обоих случаях важно то, что общее распределение фактических чертежей совпадает с распределением во входном списке. Это особенно верно, поскольку количество рисунков становится более статистически значимым .

Что касается вопроса о возможности наличия слишком слабого фильтра повторов, то это тоже становится менее актуальным, поскольку второй список отражает все больше и больше раздача первого списка. Алго 1: Отрисовка без замены из первого списка. Что мы будем использовать копию исходного списка для начала, и каждый раз, когда данный элемент рисуется, мы удаляем его из этого списка, что в целом снижает вероятность того, что то же значение появится снова. К тому времени, когда мы нарисовали все элементы, мы точно воспроизвели распределение исходного списка.
Алгоритм 2: Рисование без замены из списка, в котором исходный список был воспроизведен заданное количество раз . Это похоже на вышеизложенное, но вводит немного больше случайности, т.е. требует большего количества рисунков, чтобы иметь подход распределения рисунков и совпадать с исходным списком.

В некотором смысле, алгоритм двух списков, который я предложил изначально (Рисование с заменой из исходного списка и управление вторым списком, чтобы иногда предотвращать повторы) аналогично алгоритму 2 в том, как он сводит распределение чертежей к исходному списку. Однако преимущество исходного алгоритма состоит в том, что он упрощает управление списками (хотя, честно говоря, простой способ сделать это - заменить нарисованные элементы на "нулевые" значения сортировки,

Использовать время, прошедшее с момента вставки или последнего выбора элемента, в качестве усиления приоритета ... Установите приоритет каждого элемента = количество времени с момента его вставки или последнего выбора, а затем настройте его шанс быть выбранным путем умножения на этот приоритет.

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

общая стратегия выбора взвешенный случайный элемент из списка таков: присвоить каждому элементу вес. нормализовать, чтобы общий вес был 1. (поэтому для начала каждый элемент имеет вес 1 / n). отсортируйте список по весу. теперь выберите случайное число от 0 до 1 и двигайтесь вниз по списку, накапливая итоги, пока не пересечете свое число. например, если ваши веса [0,4, 0,3, 0,2, 0,1] и ваше случайное число 0,63215, ваши первые два шага имеют total = 0,4, total = 0,7, а затем обратите внимание, что 0,7 больше 0,63215, поэтому вы возвращаете второй элемент.

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

обратите внимание, что это довольно неэффективно, если у вас есть много элементов, так как это O (n) в длине списка, но на практике это не имеет значения, если только вы не делаете это во внутреннем цикле, который необходимо сильно оптимизировать, или подобном . если это окажется проблемой, вы можете изучить геометрические структуры данных, такие как деревья диапазонов, чтобы оптимизировать поиск.

На практике это имеет значение, если только вы не делаете это во внутреннем цикле, который нуждается в значительной оптимизации или подобном. если это окажется проблемой, вы можете изучить геометрические структуры данных, такие как деревья диапазонов, чтобы оптимизировать поиск.

На практике это имеет значение, если только вы не делаете это во внутреннем цикле, который нуждается в значительной оптимизации или подобном. если это окажется проблемой, вы можете изучить геометрические структуры данных, такие как деревья диапазонов, чтобы оптимизировать поиск.