Наиболее эффективный способ случайного выбора набора различных целых чисел

Question

Я ищу наиболее эффективный алгоритм случайного выбора набора из n различных целых чисел, где все целые числа находятся в некотором диапазоне [0..maxValue].

Ограничения:

• maxValue больше n и, возможно, намного больше
• Мне все равно, отсортирован ли список вывода или нет
• все целые числа должны быть выбраны с равной вероятностью

Моя первоначальная идея состояла в том, чтобы создать список целых чисел [0..maxValue], а затем извлечь n элементов в произвольном порядке без замены.Но это кажется совершенно неэффективным, особенно если maxValue велико.

Есть ли лучшие решения?

Answer 1

Вот оптимальный алгоритм, предполагающий, что нам разрешено использовать хеш-карты.Он работает в O (n) времени и пространстве (а не в O (maxValue) времени, что слишком дорого).

Он основан на алгоритме случайной выборки Флойда.См. Мой пост в блоге об этом для деталей.Код на Java:

private static Random rnd = new Random();

public static Set<Integer> randomSample(int max, int n) {
    HashSet<Integer> res = new HashSet<Integer>(n);
    int count = max + 1;
    for (int i = count - n; i < count; i++) {
        Integer item = rnd.nextInt(i + 1);
        if (res.contains(item))
            res.add(i);
        else
            res.add(item);
    }
    return res;
}

Answer 2

Для небольших значений maxValue, таких, что разумно сгенерировать массив всех целых чисел в памяти, вы можете использовать вариацию Фишера-Йейтса shuffle за исключением выполнения только первых n шагов .

---

Если n намного меньше, чем maxValue и вы не хотите генерировать весь массив, вы можете использовать этот алгоритм:

1. Сохранение отсортированного списка l выбранного числа, изначально пустого.
2. Выберите случайное число x между 0 и maxValue - (элементы в l)
3. Для каждого числа в l, если оно меньше или равно x, добавьте 1 к x
4. Добавьте скорректированное значение x в отсортированный список и повторите.

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

---

Вот еще один алгоритм, который проще, но имеет потенциально неограниченное время выполнения:

1. Сохраните набор s выбранного элемента, изначально пустой.
2. Выберите случайное число от 0 до maxValue.
3. Если номер не в s, добавьте его к s.
4. Вернитесь к шагу 2, пока s не будет иметь n элементов.

На практике, если n мало и maxValue велико, этого будет достаточно для большинства целей.

Answer 3

Если вы выбираете M элементов из N, стратегия меняется в зависимости от того, имеет ли M тот же порядок, что и N или намного меньше (т.е. меньше, чем N / log N).

Если они похожи по размеру, то вы проходите каждый пункт от 1 до N.Вы отслеживаете, сколько предметов у вас так далеко (давайте назовем это m предметов, выбранных из n, через которые вы прошли), а затем вы берете следующее число с вероятностью (M-m)/(N-n) и выбрасываете егоиначе.Затем вы обновляете m и n соответствующим образом и продолжаете.Это алгоритм O(N) с низкими постоянными затратами.

Если, с другой стороны, M значительно меньше, чем N, тогда стратегия повторной выборки является хорошей.Здесь вы захотите отсортировать M, чтобы вы могли быстро найти их (и это будет стоить вам O(M log M) времени - например, вставьте их в дерево).Теперь вы равномерно выбираете числа от 1 до N и вставляете их в свой список.Если вы обнаружите столкновение, выберите снова.Вы столкнетесь примерно в M/N времени (на самом деле, вы интегрируете от 1 / N до M / N), что потребует от вас выбора (рекурсивно), поэтому вы ожидаете, что M/(1-M/N) выборазавершить процесс.Таким образом, ваша стоимость этого алгоритма составляет примерно O(M*(N/(N-M))*log(M)).

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

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

Answer 4

Один из способов сделать это без генерации полного массива.

Скажем, я хочу случайно выбранный набор из m элементов из набора {x1, ..., xn}, где m <= n. </p>

Рассмотрим элемент x1. Я добавляю x1 к своему подмножеству с вероятностью m / n.

• Если я делаю добавление x1 к своему подмножеству, тогда я уменьшу свою проблему с выбором (m - 1) элементов из {x2, ..., xn}.
• Если я не добавлю x1 к своему подмножеству, тогда я уменьшу свою проблему до выбора m элементов из {x2, ..., xn}.

вспенить, промыть и повторять до тех пор, пока m = 0.

Этот алгоритм - O (n), где n - количество элементов, которые я должен рассмотреть.

Я скорее представляю, что существует алгоритм O (m), где на каждом шаге вы учитываете, сколько элементов нужно удалить с «фронта» набора возможностей, но я не убедил себя в хорошем решении, и у меня есть сделать какую-то работу сейчас!

Answer 5

Хитрость заключается в том, чтобы использовать вариацию shuffle или, другими словами, частичное перемешивание.

function random_pick( a, n ) 
{
  N = len(a);
  n = min(n, N);
  picked = array_fill(0, n, 0); backup = array_fill(0, n, 0);
  // partially shuffle the array, and generate unbiased selection simultaneously
  // this is a variation on fisher-yates-knuth shuffle
  for (i=0; i<n; i++) // O(n) times
  { 
    selected = rand( 0, --N ); // unbiased sampling N * N-1 * N-2 * .. * N-n+1
    value = a[ selected ];
    a[ selected ] = a[ N ];
    a[ N ] = value;
    backup[ i ] = selected;
    picked[ i ] = value;
  }
  // restore partially shuffled input array from backup
  // optional step, if needed it can be ignored
  for (i=n-1; i>=0; i--) // O(n) times
  { 
    selected = backup[ i ];
    value = a[ N ];
    a[ N ] = a[ selected ];
    a[ selected ] = value;
    N++;
  }
  return picked;
}

ПРИМЕЧАНИЕ алгоритм строго O(n) в во времени и пространстве , производит несмещенных выборок (это частичная несмещенная перетасовка ) и не нужны hasmaps (которые могут быть недоступны и / или обычно скрывают сложность за их реализацией, например, время выборки не O(1), в худшем случае оно может быть даже O(n))

адаптировано с здесь

Answer 6

Мое решение такое же, как у Марка Байерса. Это занимает O (n ^ 2) времени, поэтому полезно, когда n намного меньше maxValue. Вот реализация в Python:

def pick(n, maxValue):
    chosen = []
    for i in range(n):
        r = random.randint(0, maxValue - i)
        for e in chosen:
            if e <= r:
                r += 1
            else:
                break;
        bisect.insort(chosen, r)
    return chosen

Answer 7

ОБНОВЛЕНИЕ: Я не прав. Выходные данные этого не распределены равномерно. Подробности о том, почему здесь .

---

Я думаю, что этот алгоритм ниже оптимальный . То есть Вы не можете получить лучшую производительность, чем эта.

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

Это также полностью рабочая программа на Си. То, что вы найдете:

• Функция getrand: Это просто PRNG, который возвращает число от 0 до upto.
• Функция randselect: Это функция, которая случайным образом выбирает n уникальных чисел из m многих чисел. Вот о чем этот вопрос.
• Функция main: Это только для демонстрации использования других функций, чтобы вы могли скомпилировать их в программу и повеселиться.

#include <stdio.h>
#include <stdlib.h>

int getrand(int upto) {
    long int r;
    do {
        r = rand();
    } while (r > upto);
    return r;
}

void randselect(int *all, int end, int select) {
    int upto = RAND_MAX - (RAND_MAX % end);
    int binwidth = upto / end;

    int c;
    for (c = 0; c < select; c++) {
        /* randomly choose some bin */
        int bin = getrand(upto)/binwidth;

        /* swap c with bin */
        int tmp = all[c];
        all[c] = all[bin];
        all[bin] = tmp;
    }
}

int main() {
    int end = 1000;
    int select = 5;

    /* initialize all numbers up to end */
    int *all = malloc(end * sizeof(int));
    int c;
    for (c = 0; c < end; c++) {
        all[c] = c;
    }

    /* select select unique numbers randomly */
    srand(0);
    randselect(all, end, select);
    for (c = 0; c < select; c++) printf("%d ", all[c]);
    putchar('\n');

    return 0;
}

Здесь - это вывод примера кода, в котором я случайным образом выводил 4 перестановок из пула 8 чисел для 100 000 000 раз. Затем я использую эти многочисленные перестановки, чтобы вычислить вероятность возникновения каждой уникальной перестановки. Затем я сортирую их по этой вероятности. Вы замечаете, что числа довольно близки, что, я думаю, означает, что оно распределено равномерно. Теоретическая вероятность должна быть 1/1680 = 0,000595238095238095 . Обратите внимание, насколько эмпирический тест близок к теоретическому.

Answer 8

Линейный конгруэнтный генератор по модулю maxValue + 1.Я уверен, что написал этот ответ раньше, но я не могу его найти ...