Pick multiple random elements from a list in Java

问题:

So say I have

List<String> teamList = new LinkedList<String>()
teamList.add("team1");
teamList.add("team2");
teamList.add("team3");
teamList.add("team4");
teamList.add("team5");
teamList.add("team6");

Is there a simple way of picking... say 3 out the 6 elements in this list in a randomized way without picking the same element twice (or more times)?

回答1:

Try this:

public static List<String> pickNRandom(List<String> lst, int n) {
    List<String> copy = new LinkedList<String>(lst);
    Collections.shuffle(copy);
    return copy.subList(0, n);
}

I'm assuming that there are no repeated elements in the input list, also I take the precaution of shuffling a copy for leaving the original list undisturbed. It's called like this:

List<String> randomPicks = pickNRandom(teamList, 3);

回答2:

Create a set of ints, and put random numbers between 0 and list's length minus one into it in a loop, while the size of the set is not equal the desired number of random elements. Go through the set, and pick list elements as indicated by the numbers in the set. This way would keep your original list intact.

回答3:

The shuffle approach is the most idiomatic: after that, first K elements are exactly what you need.

If K is much less than the length of the list, you may want to be faster. In this case, iterate through the list, randomly exchanging the current element with itself or any of the elements after it. After the K-th element, stop and return the K-prefix: it will be already perfectly shuffled, and you don't need to care about the rest of the list.

(obviously, you'd like to use ArrayList here)

回答4:

You can also use reservoir sampling.

It has the advantage that you do not need to know the size of the source list in advance (e.g. if you are given an Iterable instead of a List.) Also it is efficient even when the source list is not random-access, like the LinkedList in your example.

回答5:

Use

Collections.shuffle(teamList);

to randomize the list, then remove teams one at a time from the list via teamList.remove(0);

For example:

  List<String> teamList = new LinkedList<String>();
  teamList.add("team1");
  teamList.add("team2");
  teamList.add("team3");
  teamList.add("team4");
  teamList.add("team5");
  teamList.add("team6");

  java.util.Collections.shuffle(teamList);

  String[] chosen3 = new String[3];
  for (int i = 0; i < chosen3.length && teamList.size() > 0; i++) {
     chosen3[i] = teamList.remove(0);
  }

回答6:

All good ideas but shuffling is expensive. The more efficient method (IMO) would be doing a count controlled loop and picking a random int between 0 and n; where n initially is equal to the length of your list.

In each iteration of the loop you swap the selected item with the item at n-1 on the list and decrement n by one. This way you avoid picking the same element two times and don't have to keep a separate list of selected items.

回答7:

Here is a way of doing it using Java streams, without having to create a copy of the original list or shuffling it:

public static List<String> pickRandom(List<String> list, int n) {
    if (n > list.size()) {
        throw new IllegalArgumentException("not enough elements");
    }
    Random random = new Random();
    return IntStream
            .generate(() -> random.nextInt(list.size()))
            .distinct()
            .limit(n)
            .mapToObj(list::get)
            .collect(Collectors.toList());
}

Note: It can become inefficient when n is too close to the list size for huge lists.

回答8:

int[] getRandoms(int[] ranges, int n, int[] excepts) {
    int min = ranges[0];
    int max = ranges[1];

    int[] results = new int[n];
    for (int i = 0; i < n; i++) {
        int randomValue = new Random().nextInt(max - min + 1) + min;
        if (ArrayUtils.contains(results, randomValue) || ArrayUtils.contains(excepts, randomValue)) {
            i--;
        } else {
            results[i] = randomValue;
        }
    }
    return results;
}

util class

public static class ArrayUtils {

    public static boolean contains(int[] array, int elem) {
        return getArrayIndex(array, elem) != -1;
    }

    /** Return the index of {@code needle} in the {@code array}, or else {@code -1} */
    public static int getArrayIndex(int[] array, int needle) {
        if (array == null) {
            return -1;
        }
        for (int i = 0; i < array.length; ++i) {
            if (array[i] == needle) {
                return i;
            }
        }
        return -1;
    }
}

using

int[] randomPositions = getRandoms(new int[]{0,list.size()-1}, 3, new int[]{0,1});

it will random 3 items in your list except item 0 and item 1