Создайте набор из M элементов из массива размера N

Question

ОБНОВЛЕНИЕ: согласно комментариям давайте сделаем некоторые пояснения.

Я пытаюсь понять решение для следующей задачи: Случайным образом сгенерируйте набор из M элементов из массива размера N. Каждый элемент должен иметь равную вероятность выбора.

Я нашел следующее решение (я уже прочитал этот вопрос , но он не отвечает на мой вопрос):

int rand(Random random, int min, int max) {
  return random.nextInt(1 + max - min) + min;
}

char[] generateArray(char[] original, int subsetSize) {
  char[] subset = new char[subsetSize];
  Random random = new Random();

  for (int i = 0; i < subsetSize; i++) {
    subset[i] = original[i];
  }
  for (int i = subsetSize; i < original.length; i++) {
    int r = rand(random,0, i);
    boolean takeIthElement = r < subsetSize;
    if (takeIthElement) {
      subset[r] = original[i];
    }
  }

  return subset;
}
// rand() function returns inclusive value 
// i.e. rand(0, 5) will return from 0 to 5

Этот код был найден в книге "Взлом кодового интервью" (Раздел Hard, Задание 3). Автор объясняет это следующим образом:

Предположим, у нас есть алгоритм, который может извлечь случайный набор m элементов из массива размером n - 1. Как мы можем использовать этот алгоритм для извлечения случайного набора m элементов из массива размером n? Сначала мы можем получить случайный набор размером m из первых n - 1 элементов. Затем нам просто нужно решить, следует ли вставлять array[n] в наше подмножество (что потребует извлечения из него случайного элемента). Самый простой способ сделать это - выбрать случайное число k от 0 до n. Если k < m, вставьте array[n] в subset[k]. Это как «справедливо» (то есть с пропорциональной вероятностью) вставит array[n] в подмножество и «справедливо» удалит случайный элемент из подмножества. Это даже чище писать итеративно. В этом подходе мы инициализируем подмножество массива, чтобы оно было первым m элементами оригинала. Затем мы перебираем массив, начиная с элемента m, вставляя array[i] в подмножество в (случайной) позиции k всякий раз, когда k < m.

Я думаю, что автор хотел сказать, что нам нужно сгенерировать не установленный , но массив. Итак, я думаю, что правильное описание задач должно быть: Случайным образом сгенерируйте массив из M элементов из массива размера N. Каждый элемент должен иметь равную вероятность выбора.

Если это правда, то код выше не работает правильно. Причины:

1. Например, у нас есть массив {'1', '2', 'a', 'b'} и m = 2
2. Следовательно, мы должны иметь качественные вероятности для генерации следующих наборов:

{1, 2}; {2, 1}; {1, a}; {a, 1}; {1, b}; {b, 1}; {a, 2}; {2, a}; {b, 2}; {2, b}; {a, b}; {b, a}

Меня беспокоит то, что функция никогда не будет генерировать следующие наборы: {2, 1}; {2, a}; {2, b}

Значит, это неверно.

Answer 1

Прежде всего, из объяснения и кода вполне понятно, что автор имел в виду, так же, как они написали. Множество может быть смоделировано как массив в реальной реализации, это ничего не значит. В задачах программирования очень часто люди используют довольно простые структуры - например, массив вместо java.util.Set.

Итак, задача в основном:

Случайно выбирает набор M элементов из массива размером N.

Предположим, N >= M.

Теперь самое сложное: почему этот алгоритм дает правильные результаты?

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

Давайте начнем с рекурсии.

Предположим, мы можем произвольно выбирать M элементы из массива размером N - 1. Как мы выбираем M элементы из массива размером N?

Поскольку в массиве есть «новый» элемент, мы можем либо заменить один из выбранных элементов им, либо оставить набор как есть. Но мы должны сохранять случайные свойства.

Набор M элементов из N-1 может быть выбран (N-1)! / M!*(N-1 - M)! способами.
Набор M элементов из N может быть выбран N! / M!*(N - M)! способами.

Это означает, что мы должны сохранить набор с вероятностью (N-M)/N и заменить один из элементов с вероятностью M/N. Нам также нужно будет выбрать элемент для замены с вероятностью 1/M.

Посмотрим, как это будет выглядеть в коде. Предположим, subset - это наш случайно выбранный набор M элементов из N-1.

Сначала мы должны решить, заменить ли один из элементов или нет. Нам нужна (N-M)/N вероятность. Для этого мы можем просто сгенерировать случайное число от 0 до N. Если это число меньше M, мы заменим.

boolean replace = rand(random, 0, N) < M;
if (replace) {
   // then replace
}

Теперь нам нужно выбрать один из элементов для замены. Поскольку мы моделируем массив как набор, мы можем просто случайным образом выбрать индекс от 0 до M - 1 (включительно). Итак, мы получаем:

boolean replace = rand(random, 0, N) < M;
if (replace) {
   subset[rand(random, 0, M - 1)] = original[N];
}

Здесь мы можем заметить, что если наше первое случайное значение (rand(random, 0, N)) меньше M, оно равно случайное значение между 0 и M-1. Таким образом, нам не нужен второй rand:

int r = rand(random, 0, N);
boolean replace = r < M;
if (replace) {
   subset[r] = original[N];
}

Остальное должно быть довольно тривиально.

Базовый случай рекурсии M == N. В этом случае мы ничего не заменяем, поэтому набор выделенных элементов является простым исходным массивом.

После этого рекурсию можно просто закодировать как цикл. i представляет N на каждом шаге - это дает ваш код.

Answer 2

Как я могу доказать это с помощью математики?

Ваш второй цикл for выполняется дважды, сначала с i, равным 2, затем с i, равным 3.

Когда i равно 2, r становится 0, 1 или 2, каждый с вероятностью 1/3. Таким образом, символ a перемещается в ваш результат с индексом 0 или 1 или не отображается вовсе, каждый с вероятностью 1/3. Теперь это либо [a, 2], [1, a] или [1, 2].

Когда i равен 3, r равен 0, 1, 2 или 3. b перемещается в индекс 0 с вероятностью 1/4, в индекс 1 с вероятностью 1/4 и никуда не перемещается с вероятность 1 / 2.

В следующей таблице я привел результат во всех возможных случаях. Значения в r, 0, 1 и 2 являются возможными значениями в первой итерации (i = 2). Справа или r - возможные значения во второй итерации.

r    0       1       2       3
0  [b, 2]  [a, b]  [a, 2]  [a, 2]
1  [b, a]  [1, b]  [1, a]  [1, a]
2  [b, 2]  [1, b]  [1, 2]  [1, 2]

Таким образом, в таблице вы можете прочитать, что если r равно 0 оба раза, ваш метод вернет [b, 2] и т. Д.

Каждая из 12 ячеек в таблице имеет равную вероятность, то есть 1/12. Давайте проверим: [1, 2], [1, a], [1, b], [a, 2] и [b, 2] там дважды. [a, b] и [b, a] встречаются по одному, но это один и тот же набор, поэтому этот набор также встречается дважды. Это охватывает все возможные подмножества, поэтому они одинаково вероятны.

Answer 3

Я думаю, что автор хотел сказать, что нам нужно сгенерировать не set , а array .

Нет, автор действительно имел в виду set , но в результате получается результирующий set в массиве . Сказав, что результатом является set , это означает, что порядок значений не имеет значения, что означает, что {1, 2} и {2, 1} - это то же самое set .

Учитывая, что это нормально, результат никогда не будет {2, 1}, если вероятность результата со значениями 1 и 2 равна 1/6, т.е. неупорядоченная (установленная) вероятность.

---

Если вам нужен упорядоченный результат, т. Е. 12 различных результатов в том виде, в котором вы их перечислили, то самое простое решение - это перемешать исходный массив и принять первые значения M. Это гарантирует равную вероятность всех результатов и гарантирует отсутствие дубликатов.

Перестановка массива обычно выполняется с помощью Fisher-Yates shuffle , который предназначен для перебора массива и случайной замены элемента на предыдущий.

Алгоритм в вопросе является вариантом этого. Если пропускает случайное перемешивание первых M значений, так как порядок не имеет значения. Затем он случайным образом заменяет последующие элементы случайным элементом, за исключением того, что при случайной позиции> M перестановка не происходит, а заменяемое значение просто отбрасывается, так как в итоге оно выходит за пределы результирующего набора.

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