aleatoriamente muestras de subconjuntos únicos de una matriz

Question

Si tengo una matriz:

a = [1,2,3] 

¿Cómo seleccionar aleatoriamente subconjuntos de la matriz, de manera que los elementos de cada subgrupo son únicos? Es decir, para a los subconjuntos posibles serían:

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

no puede generar todos los posibles subconjuntos como el tamaño real de una es muy grande por lo que hay muchos, muchos subconjuntos. Por el momento, estoy usando una idea de "paseo aleatorio": para cada elemento de una, "lanzo una moneda" e incluyo si la moneda sale cara, pero no estoy seguro de si esto realmente muestrea de manera uniforme el espacio. Es se siente como sesgo hacia el centro, pero esto podría ser solo mi mente haciendo coincidencia de patrones, ya que habrá más posibilidades de tamaño medio.

¿Estoy utilizando el enfoque correcto, o cómo debería ser un muestreo aleatorio?

(Soy consciente de que esto es más agnóstico y pregunta 'mathsy' una lengua, pero sentí que no era realmente el material Mathoverflow -. Sólo necesito una respuesta práctica)

Answer 1

Se podría generar números aleatorios , los convierte a binario y elegir los elementos de la matriz original en el que los bits son 1. esta es una implementación de este como un mono-parche para la clase 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 

Uso:

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

En general, esto no funciona tan mal, es O (n * m) donde n es el número de subconjuntos que desea ym es la longitud de la matriz.

Answer 2

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

Para cada elemento, una moneda se voltea. Si sale (== 0), entonces está seleccionado.

Answer 3

Creo que el cambio de moneda está bien.

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

Una matriz con 10 elementos tiene 2 ** 10 combinaciones posibles (incluyendo [] y los 10 elementos) que no es más de 10 veces (1 o 0). Realiza más matrices de cuatro, cinco y seis elementos, porque hay muchos más en el conjunto de poder.

Answer 4

Simplemente siga adelante con su idea original de "inversión de moneda". Muestrea uniformemente el espacio de posibilidades.

Se siente como que está sesgado hacia el "medio", pero eso se debe a que el número de posibilidades es mayor en el "medio". Piénselo: solo hay 1 posibilidad sin elementos y solo 1 con todos los elementos. Hay N posibilidades con 1 elemento y N posibilidades con elementos (N-1). A medida que la cantidad de elementos elegidos se acerca a (N/2), el número de posibilidades crece muy rápidamente.

Answer 5

Una manera de seleccionar un elemento aleatorio del conjunto potencia es la siguiente:

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 

Esto hace uso de funciones de cadenas en lugar de trabajar con los "bits" reales y operaciones bit a bit sólo para mi conveniencia. Puede convertirlo en un algoritmo más rápido (supongo) mediante el uso de bits reales.

Lo que hace, es codificar el powerset de array como un número entero entre 0 y 2 ** array.length y luego toma uno de esos números enteros al azar (aleatoria uniformemente, de hecho). Luego decodifica el entero en un subconjunto particular de array usando una máscara de bits (1 = el elemento está en el subconjunto, 0 = no lo está).

De esta manera usted tiene una distribución uniforme sobre el conjunto de potencia de su matriz.