Выбор подмножества равномерно случайным образом?

Question

Вопрос:

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

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

Answer 1

let m be the number of elements to select
for i = 1; i <= m; i++
   pick a random number from 1 to n, call it j
   swap array[j] and array [n] (assuming 1 indexed arrays)
   n-- 

В конце цикла последние m элементов массива - это ваше случайное подмножество.Существует вариант шаффла Фишера-Йейтса.

Answer 2

Есть 2 ^ n подмножеств.Выберите число от 0 до 2 ^ n-1 и превратите его в двоичный файл.Те, у которых установлены биты, должны быть взяты из массива и сохранены.

Например, рассмотрим набор 1,2,3,4.

int[] a = new int[]{ 1, 2, 3, 4 }
int n = (2*2*2*2) - 1; // 2^n -1 
int items = new Random().nextInt(n);

// If items is 3 then this is 000011 so we would select 1 and 2
// If items is 5 then this is 000101 so we would select 1 and 3
// And so on
for (int i=0;i<a.length;++i) {
   if ((items & (1 << i)) != 0) {
       // The bit is set, grab this item
       System.out.println("Selected " + a[i]);
   }
}

Answer 3

Если ваши выборы случайны, то вероятность выбора m предметов описанным вами способом будет 1 / pow (n, m).Я думаю, что вам нужно, это 1 / C (н, м).

Answer 4

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

int Choose1(List<int> elts)
{
    var idx = rnd.Next(0,elts.Count);
    var elt = elts[idx];
    elts.RemoveAt(idx);
    return elt;
} 

public List<int> Choose(int fromN, int chooseM)
{
    var range = new List<int>();
    for (int i = 1; i <= fromN; i++)
    {
        range.Add(i);
    }
    var choices = new List<int>();
    for (int i = 0; i < chooseM; i++)
    {
        choices.Add(Choose1(range));
    }
    return choices;
}

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