Как случайно выбрать половину * элемента списка с эквити **?

Как забрать ровно * половину элемента списка с эквити **?

(*) Половина равна n / 2, достаточно int.

Количество пунктов в списке больше 10 ^ 9. Таким образом, n / 2-1 недостаточно близко к n, чтобы быть заметным приближением.

(**) Принцип равноправия и справедливости означает, что все элементы списка имеют одинаковую вероятность выбора.

У меня был такой инструмент выбора акций:

 myList.Where(i => rand.NextDouble() >= 0.5);

но с этим у меня может быть больше / меньше половины, с небольшой вероятностью все / ни одна из них.

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


random c#
person xdtTransform    schedule 05.07.2018    source источник

Ответы (1)


arrow_upward
1
arrow_downward

Если вам известно количество элементов в последовательности, вы можете выбрать count из них случайным образом и с учетом равенства, используя следующий код:

public static IEnumerable<T> RandomlySelectedItems<T>(IEnumerable<T> sequence, int count, int sequenceLength, Random rng)
{
    int available = sequenceLength;
    int remaining = count;

    using (var iterator = sequence.GetEnumerator())
    {
        for (int current = 0; current < sequenceLength; ++current)
        {
            iterator.MoveNext();

            if (rng.NextDouble() < remaining / (double)available)
            {
                yield return iterator.Current;
                --remaining;
            }

            --available;
        }
    }
}

Это имеет то преимущество, что он не создает копию последовательности и является операцией O (N).

В вашем примере вы должны передать count как n / 2.

person Matthew Watson    schedule 05.07.2018
comment
Мне нравится O (n), но тот факт, что вы перестаете выбирать, как только половина выбрана, означает, что элемент, который не был повторен, не имел шанса быть выбранным. Это не выбор с 1 / Ni, где i - это итератор. Но все равно. Это неправильно, я должен делать математику, я вижу реальную вероятность элемента - person xdtTransform; 05.07.2018
comment
@xdtTransform Математика здесь работает. Элемент в конце списка не будет повторяться только в половине случаев; в половине случаев, когда он повторяется, он всегда будет выбран. - person Rawling; 05.07.2018
comment
@ Роулинг, математика кажется правильной. Я не могу пинговать вас по поводу обмана, но большая часть ответов на этот вопрос нарушает справедливость. это не явная часть вопроса. - person xdtTransform; 05.07.2018
comment
@xdtTransform Этот алгоритм хорошо известен, и он выбирает все элементы с равномерным распределением. - person Matthew Watson; 05.07.2018
comment
Это не совсем математически равномерное распределение, поскольку числа с плавающей запятой неточны, но оно должно быть достаточно близким для всех практических целей. Альтернативой было бы случайное перемешивание вашего массива, а затем взятие первых N элементов (но это меняет порядок вашего массива). - person Matthew Watson; 05.07.2018
comment
@xdtTransform Скажем, 6 элементов. Во-первых, это 3/6 = 0.5 шанс выбора. Во-вторых, это 0.5*2/5 + 0.5*3/5 = 0.5 шанс. В-третьих, это 0.25*1/4 + 0.5*2/4 + 0.25*3/4 = 0.5 шанс. Так и продолжается. - person Rawling; 06.07.2018