Случайная выборка уникальных подмножеств массива

Question

Если у меня есть массив:

a = [1,2,3]

Как выбрать случайным образом подмножества массива, чтобы элементы каждого подмножества были уникальными?То есть для a возможные подмножества будут:

[]
[1]
[2]
[3]
[1,2]
[2,3]
[1,2,3]

Я не могу сгенерировать все возможные подмножества, так как реальный размер очень велик, поэтому существует множество подмножеств.В настоящий момент я использую идею «случайного блуждания» - для каждого элемента я «подбрасываю монету» и включаю ее, если монета выпадает из головы, - но я не уверен, что это на самом деле единообразно выбирает пространство.Он чувствует , как будто он смещен к середине, но это может быть просто мой разум при сопоставлении с образцом, так как будет больше возможностей среднего размера.

Использую ли я правильный подход, иликак мне выбрать случайную выборку?

(я знаю, что это скорее вопрос, не связанный с языком и «математический», но я чувствовал, что это не был материал Mathoverflow - мне просто нужен практический ответ).

Answer 1

Просто продолжайте свою оригинальную идею "подбрасывания монет". Он равномерно выбирает пространство возможностей.

Вам кажется, что он смещен в сторону "середины", но это потому, что число возможностей больше всего в "середине". Подумайте об этом: есть только 1 возможность без элементов и только 1 со всеми элементами. Есть N возможностей с 1 элементом и N возможностей с (N-1) элементами. По мере того, как количество выбранных элементов становится ближе к (N / 2), количество возможностей растет очень быстро.

Answer 2

Вы можете генерировать случайные числа, преобразовывать их в двоичные и выбирать элементы из вашего исходного массива, где биты были равны 1. Вот реализация этого в виде обезьяньего патча для класса Array:

class Array
  def random_subset(n=1)
    raise ArgumentError, "negative argument" if n < 0
    (1..n).map do
      r = rand(2**self.size)
      self.select.with_index { |el, i| r[i] == 1 }
    end
  end
end

Использование:

a.random_subset(3) 
#=> [[3, 6, 9], [4, 5, 7, 8, 10], [1, 2, 3, 4, 6, 9]]

Как правило, это не так уж плохо, это O (n * m), где n - это количество подмножеств, которое вы хотите, а m - длина массива.

Answer 3

Способ выбора случайного элемента из набора мощности заключается в следующем:

my_array = ('a'..'z').to_a
power_set_size = 2 ** my_array.length
random_subset = rand(power_set_size)
subset = []
random_subset.to_i(2).chars.each_with_index do |bit, corresponding_element|
  subset << my_array[corresponding_element] if bit == "1"
end

Вместо этого я использую строковые функции вместо того, чтобы работать с реальными "битами" и побитовыми операциями только для моего удобства.Вы можете превратить его в более быстрый (я предполагаю) алгоритм, используя реальные биты.

Что он делает, так это кодирует набор мощности array как целое число от 0 до 2 ** array.length, а затем выбираетодно из этих целых чисел в случайном порядке (действительно, случайно).Затем он декодирует целое число обратно в конкретное подмножество array, используя битовую маску (1 = элемент находится в подмножестве, 0 = нет).

Таким образом, вы получаете равномерное распределение понабор мощности вашего массива.

Answer 4

Я думаю, что подбрасывание монеты в порядке.

ar = ('a'..'j').to_a
p ar.select{ rand(2) == 0 }

Массив из 10 элементов имеет 2 ** 10 возможных комбинаций (включая [] и все 10 элементов), что не более чем 10 раз (1 или 0).Он выводит больше массивов из четырех, пяти и шести элементов, потому что в powerset их намного больше.

Answer 5

a.select {|element| rand(2) == 0 }

Для каждого элемента подбрасывается монета. Если голова (== 0), то она выбрана.