N zufällige Elemente aus einer Liste <E> nehmen?

Wie kann ich n zufällige Elemente aus einem nehmen ArrayList<E>? Im Idealfall möchte ich in der Lage sein, die take()Methode nacheinander aufzurufen , um ersatzlos weitere x-Elemente zu erhalten.

Zwei Hauptwege.

1. Verwendung Random#nextInt(int):

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

   Es kann jedoch nicht garantiert werden, dass aufeinanderfolgende nAufrufe eindeutige Elemente zurückgeben.

2. Verwendung Collections#shuffle():

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

   Sie können neindeutige Elemente durch einen inkrementierten Index abrufen (vorausgesetzt, die Liste selbst enthält eindeutige Elemente).

Falls Sie sich fragen, ob es einen Java 8 Stream-Ansatz gibt; Nein, es gibt keine eingebaute. Es gibt Comparator#randomOrder()(noch?) Keine Standard-API. Sie könnten etwas wie das Folgende versuchen, während Sie den strengen ComparatorVertrag erfüllen (obwohl die Verteilung ziemlich schrecklich ist):

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

Besser Collections#shuffle()stattdessen verwenden.

Die meisten der bisher vorgeschlagenen Lösungen schlagen entweder eine vollständige Listenmischung oder eine sukzessive zufällige Auswahl vor, indem die Eindeutigkeit überprüft und bei Bedarf erneut versucht wird.

Wir können jedoch den Durstenfeld-Algorithmus (die derzeit beliebteste Fisher-Yates-Variante) nutzen.

Durstenfelds Lösung besteht darin, die "getroffenen" Zahlen an das Ende der Liste zu verschieben, indem sie bei jeder Iteration gegen die letzte nicht getroffene Zahl ausgetauscht werden.

Aus diesem Grund müssen wir nicht die gesamte Liste mischen , sondern die Schleife für so viele Schritte ausführen, wie die Anzahl der Elemente erforderlich ist, um zurückzukehren. Der Algorithmus stellt sicher, dass die letzten N Elemente am Ende der Liste 100% zufällig sind, wenn wir eine perfekte Zufallsfunktion verwendet haben.

Unter den vielen realen Szenarien, in denen wir eine vorgegebene (maximale) Anzahl zufälliger Elemente aus Arrays / Listen auswählen müssen, ist diese optimierte Methode sehr nützlich für verschiedene Kartenspiele wie Texas Poker, bei denen Sie die Anzahl a priori kennen Anzahl der pro Spiel zu verwendenden Karten; Normalerweise wird nur eine begrenzte Anzahl von Karten aus dem Stapel benötigt.

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());
}

Wenn Sie nacheinander n Elemente aus der Liste auswählen möchten und dies immer und immer wieder ohne Ersetzung tun können, ist es wahrscheinlich am besten, die Elemente zufällig zu permutieren und dann Blöcke in Blöcken von n zu entfernen. Wenn Sie die Liste zufällig permutieren, garantieren Sie statistische Zufälligkeit für jeden Block, den Sie auswählen. Der einfachste Weg, dies zu tun, wäre vielleicht die Verwendung Collections.shuffle.

Einfach und klar

   // 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;

Ein fairer Weg, dies zu tun, besteht darin, bei der n-ten Iteration die Liste durchzugehen und die Wahrscheinlichkeit zu berechnen, ob das n-te Element ausgewählt werden soll oder nicht. Dies ist im Wesentlichen der Bruchteil der Anzahl der Elemente, die Sie noch über die Anzahl der Elemente auswählen müssen im Rest der Liste verfügbar. Zum Beispiel:

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;
}

(Dieser Code wurde von einer Seite kopiert, die ich vor einiger Zeit geschrieben habe , als ich eine zufällige Stichprobe aus einer Liste ausgewählt habe .)

Verwenden Sie die folgende Klasse:

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;
    }
}

Wählen Sie weiterhin ein zufälliges Element aus und stellen Sie sicher, dass Sie nicht dasselbe Element erneut auswählen:

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;
}

Theoretisch könnte dies endlos laufen, aber in der Praxis ist es in Ordnung. Je näher Sie der gesamten Originalliste kommen, desto langsamer wird die Laufzeit offensichtlich, aber das ist nicht der Punkt, an dem Sie eine zufällige Unterliste auswählen, oder?

Wie in anderen Antworten erwähnt, Collections.shuffleist es aufgrund des Kopierens nicht sehr effizient, wenn die Quellliste groß ist. Hier ist ein Java 8 Einzeiler, der:

• Effizient genug für Listen mit wahlfreiem Zugriff wie ArrayList, wenn Sie nicht viele Elemente aus der Quelle benötigen
• ändert die Quelle nicht
• Garantiert KEINE Einzigartigkeit, wenn es für Sie nicht besonders wichtig ist. Wenn Sie 5 von 100 auswählen, besteht eine sehr gute Chance, dass die Elemente einzigartig sind.

Code:

private static <E> List<E> pickRandom(List<E> list, int n) {
  return new Random().ints(n, 0, list.size()).mapToObj(list::get).collect(Collectors.toList());
}

Für eine Liste ohne schnellen Direktzugriff (wie LinkedList) wäre die Komplexität jedoch hoch n*O(list_size).

Die folgende Klasse ruft N Elemente aus einer Liste eines beliebigen Typs ab. Wenn Sie einen Startwert angeben, wird bei jedem Lauf dieselbe Liste zurückgegeben. Andernfalls ändern sich die Elemente der neuen Liste bei jedem Lauf. Sie können das Verhalten überprüfen, indem Sie die Hauptmethoden ausführen.

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)));
    }
}

Diese Lösung ändert weder die ursprüngliche Liste noch skaliert sie die Komplexität mit der Listengröße.

Um eine Stichprobe von 4 aus einer Liste von 7 zu erhalten, wählen wir einfach ein zufälliges Element aus allen 7 aus, wählen dann ein zufälliges Element aus den verbleibenden 6 aus und so weiter. Wenn wir bereits die Indizes 4, 0, 3 ausgewählt haben, generieren wir als nächstes eine Zufallszahl aus 0, 1, 2, 3, die jeweils den Index 1, 2, 5, 6 darstellt.

static Random rand = new Random();

static <T> List<T> randomSample(List<T> list, int size) {
    List<T> sample = new ArrayList<>();

    for (int sortedSampleIndices[] = new int[size], i = 0; i < size; i++) {
        int index = rand.nextInt(list.size() - i);

        int j = 0;
        for (; j < i && index >= sortedSampleIndices[j]; j++)
            index++;
        sample.add(list.get(index));

        for (; j <= i; j++) {
            int temp = sortedSampleIndices[j];
            sortedSampleIndices[j] = index;
            index = temp;
        }
    }

    return sample;
}

Alle diese Antworten erfordern eine veränderbare Liste oder führen zu einer Leistungsabgabe

Hier ist ein schnelles Snippet, das zusätzlichen Speicherplatz für O (k) benötigt und garantiert in O (k) -Zeit ausgeführt wird und kein modifizierbares Array benötigt. (Führt Shuffles in einer Karte durch)

  func getRandomElementsFrom(array: [Int], count: Int = 8) -> [Int] {
    if array.count <= count {
        return array
    }

    var mapper = [Int: Int]()
    var results = [Int]()

    for i in 0..<count {
        let randomIndex = Int.random(in: 0..<array.count - i)

        if let existing = mapper[randomIndex] {
            results.append(array[existing])
        } else {
            let element = array[randomIndex]
            results.append(element)
        }

        let targetIndex = array.count - 1 - i
        mapper[randomIndex] = mapper[targetIndex] ?? targetIndex 
    }

    return results
}

Die folgende Methode gibt eine neue Liste von Min (n, list.size ()) zufälligen Elementen zurück, die aus der Liste der Parameterlisten entnommen wurden. Beachten Sie, dass die Listenliste nach jedem Anruf geändert wird. Daher "verbraucht" jeder Aufruf die ursprüngliche Liste und gibt n zufällige Elemente zurück:

public static <T> List<T> nextRandomN(List<T> list, int n) {
  return new ArrayList<>(list).stream()
    .map(unused -> list.remove((int) (list.size() * Math.random())))
    .limit(n)
    .collect(Collectors.toList());
}

Beispielnutzung:

List<Integer> list = new ArrayList<>(Arrays.asList(1, 2, 3, 4, 5, 6, 7, 8, 9, 10));

System.out.println(nextRandomN(list, 3).toString());
System.out.println(nextRandomN(list, 3).toString());
System.out.println(nextRandomN(list, 3).toString());
System.out.println(nextRandomN(list, 3).toString());

Beispielausgabe:

[8, 2, 3]
[4, 10, 7]
[1, 5, 9]
[6]