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

Для небольших значений maxValue, когда разумно сгенерировать массив всех целых чисел в памяти, вы можете использовать вариант перемешивание Фишера-Йейтса за исключением выполнения только первых 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 большой, этого будет достаточно для большинства целей.

Вот оптимальный алгоритм, предполагающий, что нам разрешено использовать хэш-карты. Он выполняется за время и пространство 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;
}

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

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

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

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

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

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

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

Если вы выбираете 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 числа, если генерация случайных чисел обходится дорого.)

Мое решение такое же, как у Марка Байерса. Это занимает 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

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

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))

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

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

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

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

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

Это также полностью рабочая программа на C. Что вы обнаружите:

• Функция getrand: это просто ГПСЧ, который возвращает число от 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 номеров на 100000000 много раз. Затем я использую эти многочисленные перестановки, чтобы вычислить вероятность возникновения каждой уникальной перестановки. Затем я сортирую их по этой вероятности. Вы заметили, что числа довольно близки, что, я думаю, означает, что они распределены равномерно. Теоретическая вероятность должна быть 1/1680 = 0,000595238095238095. Обратите внимание, насколько эмпирический тест близок к теоретическому.