valores morales eticos etica definicion algorithm combinations

algorithm - morales - valores eticos



Algoritmo para seleccionar una combinación de valores individual y aleatoria (7)

Digamos que tengo valores distintos y quiero seleccionar x de ellos al azar. ¿Qué es un algoritmo eficiente para hacer esto? Podría simplemente llamar a rand() x veces, pero el rendimiento sería pobre si x , y fueran grandes.

Tenga en cuenta que aquí se necesitan combinaciones : cada valor debe tener la misma probabilidad de ser seleccionado, pero su orden en el resultado no es importante. Claro, cualquier algoritmo que genere permutations calificaría, pero me pregunto si es posible hacerlo de manera más eficiente sin el requisito de orden aleatorio.

¿Cómo se genera eficientemente una lista de enteros K no repetitivos entre 0 y un límite superior N cubre este caso para las permutaciones.

Aquí hay una manera simple de hacerlo que solo es ineficiente si Y es mucho más grande que X

void randomly_select_subset( int X, int Y, const int * inputs, int X, int * outputs ) { int i, r; for( i = 0; i < X; ++i ) outputs[i] = inputs[i]; for( i = X; i < Y; ++i ) { r = rand_inclusive( 0, i+1 ); if( r < i ) outputs[r] = inputs[i]; } }

Básicamente, copie la primera X de sus valores distintos en su matriz de salida y luego, para cada valor restante, decida aleatoriamente si incluir ese valor o no.

El número aleatorio se usa para elegir un elemento de nuestra matriz de salida (mutable) para reemplazar.

El truco es usar una variación de shuffle o, en otras palabras, un shuffle parcial.

function random_pick( a, n ) { N = len(a); n = min(n, N); picked = array_fill(0, n, 0); backup = array_fill(0, n, 0); // partially shuffle the array, and generate unbiased selection simultaneously // this is a variation on fisher-yates-knuth shuffle for (i=0; i<n; i++) // O(n) times { selected = rand( 0, --N ); // unbiased sampling N * N-1 * N-2 * .. * N-n+1 value = a[ selected ]; a[ selected ] = a[ N ]; a[ N ] = value; backup[ i ] = selected; picked[ i ] = value; } // restore partially shuffled input array from backup // optional step, if needed it can be ignored for (i=n-1; i>=0; i--) // O(n) times { selected = backup[ i ]; value = a[ N ]; a[ N ] = a[ selected ]; a[ selected ] = value; N++; } return picked; }

NOTA: el algoritmo es estrictamente O(n) tanto en tiempo como en espacio , produce selecciones imparciales (es una mezcla imparcial parcial ) y no destructivo en la matriz de entrada (como una mezcla parcial sería) pero esto es opcional

adaptado desde here

actualizar

otro enfoque que utiliza una sola llamada a PRNG (generador de números pseudoaleatorios) en [0,1] de IVAN STOJMENOVIC, "SOBRE LA GENERACIÓN EN PARALELO ALEATORIA Y ALEATORIA DE OBJETOS COMBINATORIALES" (sección 3 ), de O(N) (peor caso) complejidad

Robert Floyd inventó un algoritmo de muestreo para tales situaciones. Por lo general, es superior a mezclar y agarrar los primeros x elementos, ya que no requiere almacenamiento O (y). Como se escribió originalmente, asume valores de 1..N, pero es trivial producir 0..N y / o usar valores no contiguos simplemente tratando los valores que produce como subíndices en un vector / matriz / lo que sea.

En pseuocode, el algoritmo se ejecuta así (robo de la columna Programming Pearls de Jon Bentley "Una muestra de Brilliance").

initialize set S to empty for J := N-M + 1 to N do T := RandInt(1, J) if T is not in S then insert T in S else insert J in S

Ese último bit (insertar J si T ya está en S) es la parte difícil. La conclusión es que asegura la probabilidad matemática correcta de insertar J para que produzca resultados imparciales.

Es O (x) 1 y O (1) con respecto al almacenamiento de y , O (x) .

Tenga en cuenta que, de acuerdo con la etiqueta de combinations en la pregunta, el algoritmo solo garantiza la misma probabilidad de que cada elemento ocurra en el resultado, no de su orden relativo en él.

1 O (x 2 ) en el peor de los casos para el mapa hash involucrado que puede ser descuidado ya que es un caso patológico prácticamente inexistente donde todos los valores tienen el mismo hash

Si realmente solo necesita generar combinations , donde el orden de los elementos no importa, puede usar combinadics tal como se implementan, por ejemplo, aquí por James McCaffrey .

Contraste esto con k-permutations , donde el orden de los elementos sí importa.

En el primer caso (1,2,3) , (1,3,2) , (2,1,3) , (2,3,1) , (3,1,2) , (3,2,1 ) se consideran los mismos; en este último, se consideran distintos, aunque contienen los mismos elementos.

En caso de que necesite combinaciones, puede que solo necesite generar un número aleatorio (aunque puede ser un poco grande), que puede usarse directamente para encontrar la mésima combinación. Como este número aleatorio representa el índice de una combinación particular, se deduce que su número aleatorio debe estar entre 0 y combinations . Cálculo de combinadics también puede llevar algo de tiempo.

Puede que no valga la pena, además de la respuesta de Jerry y Federico es ciertamente más simple que la implementación de combinadics. Sin embargo, si realmente solo necesita una combinación, se le preguntará si desea generar la cantidad exacta de bits aleatorios que se necesitan y ninguno más ... ;-)

Si bien no está claro si desea combinaciones o k-permutaciones, aquí hay un código C # para este último (sí, podríamos generar solo un complemento si x> y / 2, pero entonces nos habría quedado una combinación que debe ser barajado para obtener una k-permutación real):

static class TakeHelper { public static IEnumerable<T> TakeRandom<T>( this IEnumerable<T> source, Random rng, int count) { T[] items = source.ToArray(); count = count < items.Length ? count : items.Length; for (int i = items.Length - 1 ; count-- > 0; i--) { int p = rng.Next(i + 1); yield return items[p]; items[p] = items[i]; } } } class Program { static void Main(string[] args) { Random rnd = new Random(Environment.TickCount); int[] numbers = new int[] { 1, 2, 3, 4, 5, 6, 7 }; foreach (int number in numbers.TakeRandom(rnd, 3)) { Console.WriteLine(number); } } }

Otra implementación más elaborada que genera k-permutaciones , que tenía por ahí y creo que es de alguna manera una mejora con respecto a los algoritmos existentes si solo necesitas iterar sobre los resultados. Si bien también necesita generar x números aleatorios, solo utiliza la memoria O (min (y / 2, x)) en el proceso:

/// <summary> /// Generates unique random numbers /// <remarks> /// Worst case memory usage is O(min((emax-imin)/2, num)) /// </remarks> /// </summary> /// <param name="random">Random source</param> /// <param name="imin">Inclusive lower bound</param> /// <param name="emax">Exclusive upper bound</param> /// <param name="num">Number of integers to generate</param> /// <returns>Sequence of unique random numbers</returns> public static IEnumerable<int> UniqueRandoms( Random random, int imin, int emax, int num) { int dictsize = num; long half = (emax - (long)imin + 1) / 2; if (half < dictsize) dictsize = (int)half; Dictionary<int, int> trans = new Dictionary<int, int>(dictsize); for (int i = 0; i < num; i++) { int current = imin + i; int r = random.Next(current, emax); int right; if (!trans.TryGetValue(r, out right)) { right = r; } int left; if (trans.TryGetValue(current, out left)) { trans.Remove(current); } else { left = current; } if (r > current) { trans[r] = left; } yield return right; } }

La idea general es hacer un barajado de Fisher-Yates y k-permutations . No se publicó en ninguna parte ni recibió ninguna revisión por pares. Creo que es una curiosidad en lugar de tener algún valor práctico. No obstante, estoy muy abierto a las críticas y, en general, me gustaría saber si encuentra algo erróneo en él. Tenga en cuenta esto (y agregue un comentario antes de la votación a favor).

Si, por ejemplo, tiene 2 ^ 64 valores distintos, puede usar un algoritmo de clave simétrica (con un bloque de 64 bits) para reorganizar rápidamente todas las combinaciones. (por ejemplo Blowfish).

for(i=0; i<x; i++) e[i] = encrypt(key, i)

Esto no es aleatorio en el sentido puro, pero puede ser útil para su propósito. Si desea trabajar con un número arbitrario de valores distintos siguiendo técnicas criptográficas, puede hacerlo, pero es más complejo.

Suponiendo que quieras que la orden sea aleatoria también (o no te importe que sea aleatoria), solo usaría una mezcla truncada de Fisher-Yates. Inicie el algoritmo de mezcla, pero deténgalo una vez que haya seleccionado los primeros valores x , en lugar de "seleccionar al azar" todos y de ellos.

Fisher-Yates funciona de la siguiente manera:

  • seleccione un elemento al azar e instálelo con el elemento al final de la matriz.
  • Recurse (o iteración más probable) en el resto de la matriz, excluyendo el último elemento.

Los pasos posteriores al primero no modifican el último elemento de la matriz. Los pasos posteriores a los dos primeros no afectan a los dos últimos elementos. Los pasos posteriores a la primera x no afectan a los últimos x elementos. Entonces, en ese punto puede detenerse: la parte superior de la matriz contiene datos seleccionados aleatoriamente de manera uniforme. La parte inferior de la matriz contiene elementos un tanto aleatorizados, pero la permutación que obtienes de ellos no está uniformemente distribuida.

Por supuesto, esto significa que has destruido la matriz de entrada; si esto significa que necesitarías tomar una copia antes de comenzar, y x es pequeña en comparación con y, entonces copiar toda la matriz no es muy eficiente. Sin embargo, tenga en cuenta que si todo lo que va a utilizar en el futuro es más selecciones, entonces el hecho de que esté en un orden algo aleatorio no importa, puede usarlo de nuevo. Si realiza la selección varias veces, por lo tanto, es posible que solo pueda hacer una copia al comienzo y amortizar el costo.

Una pequeña sugerencia: si x >> y / 2, probablemente sea mejor seleccionar al azar y - x elementos, luego elegir el conjunto complementario.