Supongamos que desea seleccionar de manera uniforme y sin reemplazo, un conjunto de k elementos distintos de un conjunto de norte artículos. Este problema es lo mismo que elegir. k índices distintos de [0n)[0n).
Esto se puede hacer en De acuerdo) hora:
uniformsubset (k, n) = {
s = {}
m = n
para r en k-1 hasta 0
m = uniforme ([r, m-1])
s = s U {m}
devoluciones
}
La versión recursiva es un poco más fácil de razonar acerca de:
uniformsubset (0, n) = {}
uniformSubset (k, n) = uniformSubset (k-1, m-1) U {m}
donde m = uniforme ([k-1, n-1])
Se puede probar que esto se basa de manera uniforme en {s | s ⊆[0n)|s|=k}porinducción[0n)|s|=k}byinduction
A diferencia del muestreo de yacimientos, esto requiere que usted sepa norte antes de tiempo y es O (k) en lugar de O (n).
¿De quién es este algoritmo?