Эффективно выбирая случайное подмножество размеров $ m $ из набора размера $ n $

Question

Это перекрестный пост моего вопроса Здесь на math.se .

У меня есть список $ n $ items и хотелось бы случайно выбрать $ m $ установить от него эффективно (с точки зрения сложности времени). Кроме того, я хочу, чтобы все возможные подмножества были выбраны с равной вероятностью. Очевидное решение состоит в том, чтобы выбрать случайное целое число от $ 1 $ на $ n $ и выберите соответствующий элемент, Затем повторите $ M $ Times, не считая событие, в котором выбирают и уже выбранный элемент. Это становится все более неэффективным, как $ m $ Подходы $ n $ так для $ (NM) $ - установить и вернуть его комплимент. .

Для значений $ m $ рядом с $ n / 2 $ , лучшее решение, которое я думаю Было бы рассмотреть каждый из элементов $ n $ и решите либо выбрать этот элемент или отказаться от него, каждый раз обновляя вероятность выбора или отказа в зависимости от количества Элементы выбранные VS отброшены перед. В частности, алгоритм будет работать следующим образом (Python):

def randomSubset(n,m):
  L = []
  for i in range(n):
    if uniform(0,1)<m/(n-i): L,m = L+[i],m-1
  return L

.

Однако я обеспокоен тем, что это может не привести к каждому подмножению, выбранному с равной вероятностью.

У меня есть два вопроса. Во-первых, делает этот алгоритм подзрак с равной вероятностью (если так, я бы хотел доказательство того, что он делает, и если бы не я также хотел бы доказательство того, что он не имеет). Во-вторых, в целом я хотел бы знать, какие хорошие решения существуют для этой проблемы. Очевидно, что если $ m << n $ тогда первый метод лучше, чем второй, однако, в какой-то момент второй метод (если он на самом деле работает) лучше, чем первый. Более того, совершенно другой подход может быть лучшим в целом.

Answer 1

Вероятность того, что элемент $ 1 $ принадлежит случайному $ m $ Spaness Class="Math-container"> $ n $ set - $ m / n $ . Поэтому вы должны включить $ 1 $ В вашем подмножестве с вероятностью $ m / n $ .

Если вы поместите $ 1 $ В вашем подмножестве, то вы остаетесь в выборе $ (M - 1) $ --sset of $ (n - 1) $ набор ".

Если вы не поместили $ 1 $ в вашем подмножестве, то вы остаетесь с выбором $ M $ < / span / setsset $ (n - 1) $ set.

Это означает, что вам нужно немного обновить свой алгоритм, замена $ m $ с $ m- | l | $ .

Полученный алгоритм несколько похож на Сборка резервуара .

Третий подход, с некоторыми сходствами, генерируют случайную перестановку 1 $, \ ldots, n $ и выбора первого $ m $ Записи.

Нижняя часть всех этих подходов состоит в том, что они проходят во времени $ \ Theta (n) $ , тогда как для $ m \ ll \ sqrt {n} $ , ваш первый алгоритм работает в (ожидаемом) времени $ \ Tilde \ theta (m) $ . .

Мы можем улучшить на $ \ theta (n) $ время работы следующим образом. Мы будем генерировать случайную заказанную $ m $ - set $ m $ Индексы $ i_1, \ ldots, i_m $ , где $ i_j \ in \ {1, \ ldots, n- (j-1) \} $ < / span>. $ J $ 'TH-элемент в подмножестве, будет $ i_j $ ' Th Memble in в < Spaness Class= «Математика-контейнер»> $ \ {1, \ ldots, n \} $ Нет из номеров, которые еще не выбраны.

Чтобы завершить описание алгоритма, нам нужно решить следующую проблему: Учитывая $ S \ subsEtq \ {1, \ ldots, n \} $ И $ i $ , найдите $ i $ 'Th маленький элемент в $ \ uverline {s} $ . Мы можем предположить, что $ s $ хранится в структуре (например, самобалансирующееся двоичное дерево), которое может эффективно ответить на следующий тип запроса: учитывая <класс Span= «Математический контейнер»> $ x $ , сколько элементов в $ S $ меньше, чем $ x $ . Затем мы можем найти $ i $ "Масштабное число в $ \ uverline {s} $ Использование двоичного поиск.

В целом этот алгоритм работает в $ \ Tilde \ Theta (m) $ для всех значений $ m $ < / span>, где Tilde скрывает факторы логарифмии в $ n $ . (Когда $ m \ ll \ sqrt {n} $ Мы можем использовать свой первый подход, тем самым избавиться от этой зависимости от $ n $ .)