¿Cuál es el nombre de este algoritmo de muestreo?

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?