una simetrica siguiente programar primero manejo interseccion ejemplos diferencia conjuntos conjunto comparar colecciones arreglos java algorithm collections random subset

simetrica - programar una interseccion de conjuntos en java



La mejor forma de elegir un subconjunto aleatorio de una colección? (10)

Tengo un conjunto de objetos en un Vector del cual me gustaría seleccionar un subconjunto aleatorio (por ejemplo, 100 elementos regresan, elija 5 aleatoriamente). En mi primer pase (muy apresurado) hice una solución extremadamente simple y tal vez demasiado inteligente:

Vector itemsVector = getItems(); Collections.shuffle(itemsVector); itemsVector.setSize(5);

Si bien esto tiene la ventaja de ser bueno y simple, sospecho que no va a escalar muy bien, es decir, Collections.shuffle () debe ser O (n) al menos. Mi alternativa menos inteligente es

Vector itemsVector = getItems(); Random rand = new Random(System.currentTimeMillis()); // would make this static to the class List subsetList = new ArrayList(5); for (int i = 0; i < 5; i++) { // be sure to use Vector.remove() or you may get the same item twice subsetList.add(itemsVector.remove(rand.nextInt(itemsVector.size()))); }

¿Alguna sugerencia sobre mejores formas de extraer un subconjunto aleatorio de una Colección?

¿Cuánto cuesta eliminar? Porque si eso necesita reescribir la matriz en una nueva porción de memoria, entonces ha realizado O (5n) operaciones en la segunda versión, en lugar de la O (n) que quería antes.

Puede crear una matriz de booleanos configurados en falso y luego:

for (int i = 0; i < 5; i++){ int r = rand.nextInt(itemsVector.size()); while (boolArray[r]){ r = rand.nextInt(itemsVector.size()); } subsetList.add(itemsVector[r]); boolArray[r] = true; }

Este enfoque funciona si su subconjunto es más pequeño que su tamaño total por un margen significativo. A medida que esos tamaños se acerquen el uno al otro (es decir, 1/4 del tamaño o algo así), obtendría más colisiones en ese generador de números aleatorios. En ese caso, haré una lista de enteros del tamaño de su matriz más grande, y luego mezclaré esa lista de enteros, y extraeré los primeros elementos para obtener los indeces (no colisionantes). De esta forma, tiene el costo de O (n) en la construcción de la matriz de enteros, y otra O (n) en la mezcla, pero no hay colisiones de un comprobador interno mientras que es menor que el potencial O (5n) que puede costar.

@Jonathan,

Creo que esta es la solución de la que estás hablando:

void genknuth(int m, int n) { for (int i = 0; i < n; i++) /* select m of remaining n-i */ if ((bigrand() % (n-i)) < m) { cout << i << "/n"; m--; } }

Está en la página 127 de Programming Pearls por Jon Bentley y se basa en la implementación de Knuth.

EDITAR: Acabo de ver una nueva modificación en la página 129:

void genshuf(int m, int n) { int i,j; int *x = new int[n]; for (i = 0; i < n; i++) x[i] = i; for (i = 0; i < m; i++) { j = randint(i, n-1); int t = x[i]; x[i] = x[j]; x[j] = t; } sort(x, x+m); for (i = 0; i< m; i++) cout << x[i] << "/n"; }

Esto se basa en la idea de que "... necesitamos mezclar solo los primeros m elementos de la matriz ..."

Escribí una implementación eficiente de esto hace unas semanas. Está en C # pero la traducción a Java es trivial (esencialmente el mismo código). El lado positivo es que también es completamente imparcial (que algunas de las respuestas existentes no lo son), una forma de probar que está aquí .

Se basa en una implementación de Durstenfeld de la mezcla aleatoria de Fisher-Yates.

Jon Bentley discute esto en ''Programming Pearls'' o ''More Programming Pearls''. Debe tener cuidado con su proceso de selección N de M, pero creo que el código mostrado funciona correctamente. En lugar de barajar aleatoriamente todos los elementos, puede hacer la mezcla aleatoria solo arrastrando las primeras N posiciones, lo que es un ahorro útil cuando N << M.

Knuth también discute estos algoritmos, creo que sería Vol 3 "Ordenando y Buscando", pero mi set está empacado a la espera de un cambio de casa, así que no puedo verificarlo formalmente.

No creo que aparezcan dos soluciones aquí: el corresponsal es bastante largo y contiene algunos enlaces, sin embargo, no creo que todas las publicaciones se relacionen con el problema de elegir un subst de K elemetns entre un conjunto de N elementos . [Por "conjunto", me refiero al término matemático, es decir, todos los elementos aparecen una vez, el orden no es importante].

Sol 1:

//Assume the set is given as an array: Object[] set ....; for(int i=0;i<K; i++){ randomNumber = random() % N; print set[randomNumber]; //swap the chosen element with the last place temp = set[randomName]; set[randomName] = set[N-1]; set[N-1] = temp; //decrease N N--; }

Esto se parece a la respuesta que dio Daniel, pero en realidad es muy diferente. Es de O (k) tiempo de ejecución.

Otra solución es utilizar algunas matemáticas: considere los índices de matriz como Z_n y así podemos elegir aleatoriamente 2 números, x que es coprima a n, es decir, chhose gcd (x, n) = 1, y otra, a, que es "punto de partida" - luego la serie: a% n, a + x% n, a + 2 * x% n, ... a + (k-1) * x% n es una secuencia de números distintos (siempre que k <= n).

Si está tratando de seleccionar k elementos distintos de una lista de n, los métodos que proporcionó anteriormente serán O (n) u O (kn), porque eliminar un elemento de un Vector hará que una matriz elimine todos los elementos .

Ya que está preguntando cuál es la mejor manera, depende de lo que se le permita hacer con su lista de entrada.

Si es aceptable modificar la lista de entrada, como en los ejemplos, puede simplemente intercambiar k elementos aleatorios al principio de la lista y devolverlos en tiempo O (k) como este:

public static <T> List<T> getRandomSubList(List<T> input, int subsetSize) { Random r = new Random(); int inputSize = input.size(); for (int i = 0; i < subsetSize; i++) { int indexToSwap = i + r.nextInt(inputSize - i); T temp = input.get(i); input.set(i, input.get(indexToSwap)); input.set(indexToSwap, temp); } return input.subList(0, subsetSize); }

Si la lista debe terminar en el mismo estado en que comenzó, puede realizar un seguimiento de las posiciones que intercambió y luego devolver la lista a su estado original después de copiar la lista secundaria seleccionada. Esta sigue siendo una solución O (k).

Sin embargo, si no puede modificar la lista de entrada yk es mucho menor que n (como 5 de 100), sería mucho mejor no eliminar los elementos seleccionados cada vez, sino simplemente seleccionar cada elemento, y si alguna vez obtiene un duplicado, tirarlo y volver a seleccionarlo. Esto le dará O (kn / (nk)) que todavía está cerca de O (k) cuando n domina k. (Por ejemplo, si k es menor que n / 2, entonces se reduce a O (k)).

Si k no está dominado por n, y no puede modificar la lista, también puede copiar su lista original y usar su primera solución, porque O (n) será tan buena como O (k).

Como han notado otros, si dependes de una fuerte aleatoriedad donde cada sublista es posible (e imparcial), definitivamente necesitarás algo más fuerte que java.util.Random . Ver java.security.SecureRandom .

Sin embargo, su segunda solución para usar el elemento Aleatorio para seleccionar parece sólida:

Yo personalmente optaría por su implementación inicial: muy conciso. Las pruebas de rendimiento mostrarán qué tan bien se escala. Implementé un bloque de código muy similar en un método decentemente abusado y escalado lo suficiente. El código particular también se basa en matrices que contienen> 10.000 elementos.

This es una pregunta muy similar en .

Para resumir mis respuestas favoritas de esa página (furst one del usuario Kyle):

  • Solución O (n) : itere a través de su lista, y copie un elemento (o referencia al mismo) con probabilidad (#needed / #remaining). Ejemplo: si k = 5 yn = 100, entonces toma el primer elemento con prob 5/100. Si copias eso, entonces eliges el siguiente con prob 4/99; pero si no tomó el primero, el problema es 5/99.
  • O (k log k) o O (k 2 ) : construya una lista ordenada de índices k (números en {0, 1, ..., n-1}) eligiendo aleatoriamente un número <n, luego elija aleatoriamente un número <n-1, etc. En cada paso, necesita volver a calibrar su elección para evitar colisiones y mantener las probabilidades incluso. Como ejemplo, si k = 5 yn = 100, y su primera opción es 43, su próxima opción está en el rango [0, 98], y si es> = 43, entonces usted agrega 1 a ella. Entonces, si su segunda opción es 50, entonces usted agrega 1 a ella, y usted tiene {43, 51}. Si su próxima opción es 51, agregue 2 para obtener {43, 51, 53}.

Aquí hay algo de pseudopython:

# Returns a container s with k distinct random numbers from {0, 1, ..., n-1} def ChooseRandomSubset(n, k): for i in range(k): r = UniformRandom(0, n-i) # May be 0, must be < n-i q = s.FirstIndexSuchThat( s[q] - q > r ) # This is the search. s.InsertInOrder(q ? r + q : r + len(s)) # Inserts right before q. return s

Estoy diciendo que la complejidad del tiempo es O (k 2 ) u O (k log k) porque depende de qué tan rápido pueda buscar e insertar en su contenedor para s. Si s es una lista normal, una de esas operaciones es lineal, y obtienes k ^ 2. Sin embargo, si está dispuesto a construir s como un árbol binario equilibrado, puede obtener el tiempo O (k log k).

Set<Integer> s = new HashSet<Integer>() // add random indexes to s while(s.size() < 5) { s.add(rand.nextInt(itemsVector.size())) } // iterate over s and put the items in the list for(Integer i : s) { out.add(itemsVector.get(i)); }