Выбрав k из n

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

Составьте список всех возможностей n. Перемешайте их (вам не нужно чтобы перетасовать все номера n только k из них, выполнив первый k шагов Фишер Йейтс). Выберите первый k. Этот подход занимает время O(k) (предполагается, что выделение массива размера n принимает O(1) time) и O(n). Это проблема, если k очень малый относительно n.
Сохраните набор видимых элементов. Выберите случайное число из [0, n-1]. Пока элемент находится в наборе, выберите новый номер. Этот подход занимает пространство O(k). Время выполнения немного больше сложный для анализа. Если k = theta(n), тогда время выполнения O(k*lg(k))=O(n*lg(n)), потому что это сборщик купонов проблема. Если k мал относительно n, то он немного более чем O(k) из-за вероятности (хотя и низкой) выбора тот же номер два раза. Это лучше, чем приведенное выше решение в условия пространства, но хуже с точки зрения времени выполнения.

Мой вопрос:

существует ли O(k) время, O(k) пространственный алгоритм для всех k и n?

Ответ 1

С помощью O (1) хеш-таблицы частичный метод Fisher-Yates может быть выполнен для запуска в O (k) времени и пространства. Трюк состоит в том, чтобы просто сохранить только измененные элементы массива в хэш-таблице.

Вот простой пример в Java:

public static int[] getRandomSelection (int k, int n, Random rng) {
    if (k > n) throw new IllegalArgumentException(
        "Cannot choose " + k + " elements out of " + n + "."
    );

    HashMap<Integer, Integer> hash = new HashMap<Integer, Integer>(2*k);
    int[] output = new int[k];

    for (int i = 0; i < k; i++) {
        int j = i + rng.nextInt(n - i);
        output[i] = (hash.containsKey(j) ? hash.remove(j) : j);
        if (j > i) hash.put(j, (hash.containsKey(i) ? hash.remove(i) : i));
    }
    return output;
}

Этот код выделяет HashMap из 2 и times; k ведер для хранения измененных элементов (этого должно быть достаточно, чтобы гарантировать, что хеш-таблица никогда не будет перефразирована), и просто запускает частичный перехват Fisher-Yates на нем.

Вот быстрый тест на Ideone; он выбирает два элемента из трех 30 000 раз и подсчитывает количество раз, когда выбирается каждая пара элементов. Для непредвзятой перетасовки каждая упорядоченная пара должна появиться примерно 5000 (или около 100 раз), за исключением невозможных случаев, когда оба элемента будут равны.

Ответ 2

Что вы можете использовать, это следующий алгоритм (используя javascript вместо псевдокода):

var k = 3;
var n = [1,2,3,4,5,6];

// O(k) iterations
for(var i = 0, tmp; i < k; ++i) {

    // Random index O(1)
    var index = Math.floor(Math.random() * (n.length - i));

    // Output O(1)
    console.log(n[index]);

    // Swap and lookup O(1)
    tmp = n[index];
    n[index] = n[n.length - i - 1];
    n[n.length - i - 1] = tmp;
}

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

Память O (n), если вы хотите получить числа в виде набора, просто обратитесь к последним k записям из n.

Ответ 3

Ваш второй подход не принимает время Theta (k log k) в среднем, он принимает около n/(n-k + 1) + n/(n-k + 2) +... + n/n операций, что меньше k (n/(nk)), так как у вас есть k слагаемых, каждый из которых меньше n/(nk). При k <= n/2 в среднем требуется 2 * k операций. При k > n/2 вы можете выбрать произвольное подмножество размера n-k и взять дополнение. Таким образом, это уже средний алгоритм времени и пространства O (k).