positivos - numeros aleatorios en java netbeans

Tome n elementos aleatorios de una lista<E>?

Question

¿Cómo puedo tomar n elementos aleatorios de una ArrayList<E> ? Idealmente, me gustaría poder hacer llamadas sucesivas al método take() para obtener otros x elementos, sin reemplazo.

Answer 1

Dos formas principales.

1. Use Random#nextInt(int) :

   List<Foo> list = createItSomehow();
   Random random = new Random();
   Foo foo = list.get(random.nextInt(list.size()));

   Sin embargo, no se garantiza que las n llamadas sucesivas devuelvan elementos únicos.

2. Usar Collections#shuffle() :

   List<Foo> list = createItSomehow();
   Collections.shuffle(list);
   Foo foo = list.get(0);

   Le permite obtener n elementos únicos mediante un índice incrementado (suponiendo que la lista misma contenga elementos únicos).

En caso de que se pregunte si hay un enfoque Java 8 Stream; no, no hay uno incorporado. No existe el Comparator#randomOrder() en la API estándar (¿todavía?). Podrías probar algo como lo que se muestra a continuación sin dejar de cumplir el estricto contrato de Comparator (aunque la distribución es bastante terrible):

List<Foo> list = createItSomehow();
int random = new Random().nextInt();
Foo foo = list.stream().sorted(Comparator.comparingInt(o -> System.identityHashCode(o) ^ random)).findFirst().get();

Mejor use Collections#shuffle() lugar.

Answer 2

La mayoría de las soluciones propuestas hasta ahora sugieren una lista completa aleatoria o una selección aleatoria sucesiva al verificar la exclusividad y volver a intentarlo si es necesario.

Pero podemos aprovechar el algoritmo de Durstenfeld (la variante Fisher-Yates más popular en nuestros días).

La solución de Durstenfeld es mover los números "golpeados" al final de la lista intercambiándolos con el último número sin tocar en cada iteración.

Debido a lo anterior, no es necesario barajar toda la lista , sino ejecutar el ciclo para obtener tantos pasos como la cantidad de elementos necesarios para devolver. El algoritmo asegura que los últimos N elementos al final de la lista son 100% aleatorios si utilizamos una función aleatoria perfecta.

Entre los muchos escenarios del mundo real donde tenemos que elegir una cantidad predeterminada (máxima) de elementos aleatorios de matrices / listas, este método optimizado es muy útil para varios juegos de cartas, como Texas Poker, donde a priori conoce el número de cartas que se utilizarán por juego; solo se requiere un número limitado de cartas del mazo.

public static <E> List<E> pickNRandomElements(List<E> list, int n, Random r) {
    int length = list.size();

    if (length < n) return null;

    //We don''t need to shuffle the whole list
    for (int i = length - 1; i >= length - n; --i)
    {
        Collections.swap(list, i , r.nextInt(i + 1));
    }
    return list.subList(length - n, length);
}

public static <E> List<E> pickNRandomElements(List<E> list, int n) {
    return pickNRandomElements(list, n, ThreadLocalRandom.current());
}

Answer 3

La siguiente clase recupera N elementos de una lista de cualquier tipo. Si proporciona una semilla, en cada ejecución devolverá la misma lista; de lo contrario, los elementos de la nueva lista cambiarán en cada ejecución. Puedes verificar su comportamiento al ejecutar los métodos principales.

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.List;
import java.util.Random;

public class NRandomItem<T> {
    private final List<T> initialList;

    public NRandomItem(List<T> list) {
        this.initialList = list;
    }

    /**
     * Do not provide seed, if you want different items on each run.
     * 
     * @param numberOfItem
     * @return
     */
    public List<T> retrieve(int numberOfItem) {
        int seed = new Random().nextInt();
        return retrieve(seed, numberOfItem);
    }

    /**
     * The same seed will always return the same random list.
     * 
     * @param seed,
     *            the seed of random item generator.
     * @param numberOfItem,
     *            the number of items to be retrieved from the list
     * @return the list of random items
     */
    public List<T> retrieve(int seed, int numberOfItem) {
        Random rand = new Random(seed);

        Collections.shuffle(initialList, rand);
        // Create new list with the number of item size
        List<T> newList = new ArrayList<>();
        for (int i = 0; i < numberOfItem; i++) {
            newList.add(initialList.get(i));
        }
        return newList;
    }

    public static void main(String[] args) {
        List<String> l1 = Arrays.asList("Foo", "Bar", "Baz", "Qux");
        int seedValue = 10;
        NRandomItem<String> r1 = new NRandomItem<>(l1);

        System.out.println(String.format("%s", r1.retrieve(seedValue, 2)));
    }
}

Answer 4

Si desea elegir sucesivamente n elementos de la lista y puede hacerlo sin reemplazo una y otra vez, probablemente sea mejor permutar aleatoriamente los elementos, y luego eliminar fragmentos en bloques de n. Si permutas aleatoriamente la lista, garantizas la aleatoriedad estadística para cada bloque que elijas. Quizás la forma más fácil de hacer esto sería usar Collections#shuffle() .

Answer 5

Sigue seleccionando un elemento aleatorio y asegúrate de no volver a elegir el mismo elemento:

public static <E> List<E> selectRandomElements(List<E> list, int amount)
{
    // Avoid a deadlock
    if (amount >= list.size())
    {
        return list;
    }

    List<E> selected = new ArrayList<>();
    Random random = new Random();
    int listSize = list.size();

    // Get a random item until we got the requested amount
    while (selected.size() < amount)
    {
        int randomIndex = random.nextInt(listSize);
        E element = list.get(randomIndex);

        if (!selected.contains(element))
        {
            selected.add(element);
        }
    }

    return selected;
}

En teoría, esto podría funcionar interminablemente, pero en la práctica está bien. Cuanto más cerca se encuentre la lista original, más lento será el tiempo de ejecución, pero ese no es el punto de seleccionar una sublista aleatoria, ¿o sí?

Answer 6

Simple y claro

   // define ArrayList to hold Integer objects
    ArrayList<Integer> arrayList = new ArrayList<>();

    for (int i = 0; i < maxRange; i++) {
        arrayList.add(i + 1);
    }

    // shuffle list
    Collections.shuffle(arrayList);

    // adding defined amount of numbers to target list
    ArrayList<Integer> targetList = new ArrayList<>();
    for (int j = 0; j < amount; j++) {
        targetList.add(arrayList.get(j)); 
    }

    return targetList;

Answer 7

Una manera justa de hacer esto es revisar la lista, en la enésima iteración, calculando la probabilidad de elegir o no el elemento n-ésimo, que es esencialmente la fracción de la cantidad de elementos que aún debe elegir sobre la cantidad de elementos disponible en el resto de la lista. Por ejemplo:

public static <T> T[] pickSample(T[] population, int nSamplesNeeded, Random r) {
  T[] ret = (T[]) Array.newInstance(population.getClass().getComponentType(),
                                    nSamplesNeeded);
  int nPicked = 0, i = 0, nLeft = population.length;
  while (nSamplesNeeded > 0) {
    int rand = r.nextInt(nLeft);
    if (rand < nSamplesNeeded) {
      ret[nPicked++] = population[i];
      nSamplesNeeded--;
    }
    nLeft--;
    i++;
  }
  return ret;
}

(Este código fue copiado de una página que escribí hace un tiempo para elegir una muestra aleatoria de una lista ).

Answer 8

Use la siguiente clase:

import java.util.Enumeration;
import java.util.Random;

public class RandomPermuteIterator implements Enumeration<Long> {
    int c = 1013904223, a = 1664525;
    long seed, N, m, next;
    boolean hasNext = true;

    public RandomPermuteIterator(long N) throws Exception {
        if (N <= 0 || N > Math.pow(2, 62)) throw new Exception("Unsupported size: " + N);
        this.N = N;
        m = (long) Math.pow(2, Math.ceil(Math.log(N) / Math.log(2)));
        next = seed = new Random().nextInt((int) Math.min(N, Integer.MAX_VALUE));
    }

    public static void main(String[] args) throws Exception {
        RandomPermuteIterator r = new RandomPermuteIterator(100);
        while (r.hasMoreElements()) System.out.print(r.nextElement() + " ");
    }

    @Override
    public boolean hasMoreElements() {
        return hasNext;
    }

    @Override
    public Long nextElement() {
        next = (a * next + c) % m;
        while (next >= N) next = (a * next + c) % m;
        if (next == seed) hasNext = false;
        return  next;
    }
}