从List <E>中取n个随机元素？

我如何从一个ArrayList<E>获取n个随机元素？ 理想情况下，我希望能够连续调用take()方法来获得另一个x元素，而不需要replace。

两种主要方式。

  1. 使用Random#nextInt(int) ： 

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

    但是不能保证连续的n调用返回唯一的元素。

  2. 使用Collections#shuffle() ： 

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

    它使您能够通过递增的索引获取n唯一元素（假设列表本身包含唯一元素）。

如果您想知道是否有Java 8 Stream方法; 不，没有一个内置的。 在标准API中没有Comparator#randomOrder()这样的东西（还有吗？）。 你可以尝试像下面这样的东西，同时仍然满足严格的Comparator合同（虽然分配是非常可怕的）： 

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

更好地使用Collections#shuffle()来代替。

到目前为止，大多数提出的解决scheme都是通过检查唯一性来build议完整列表随机select或者连续随机select，如果需要的话可以重试。

但是，我们可以利用Durstenfeld的algorithm（当今最stream行的Fisher-Yates变种）。

Durstenfeld的解决scheme是通过将每个迭代中的最后一个未使用的数字交换到列表中，将“已触发”的数字移动到列表的末尾。

由于上述原因， 我们不需要洗牌整个列表 ，而是循环执行与返回所需元素数量相同的步骤。 如果我们使用完美的随机函数，algorithm确保列表末尾的最后N个元素是100％随机的。

在许多现实世界的场景中，我们需要从arrays/列表中select预定（最大）的随机元素，这种优化的方法对于各种纸牌游戏（如德州扑克）非常有用，您先前知道的数字每场比赛使用的牌数; 甲板上通常只需要有限数量的卡片。 

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

如果你想连续从列表中selectn个元素，并且能够在不重复的情况下进行replace，那么你可能是随机排列元素的最好方法，然后以n个块为单位closures块。 如果你随机排列列表，你保证每个块的统计随机性，你挑出。 也许最简单的方法是使用Collections.shuffle 。

一个公平的方法是通过列表，在第n次迭代计算是否select第n个元素的概率，这基本上是你仍然需要挑选的元素数量的一小部分在列表的其余部分可用。 例如： 

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

（这个代码是从我刚才写的一个从列表中选取一个随机样本的页面复制的。）

简单明了 

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

使用以下课程： 

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

继续select一个随机元素，并确保你不再select相同的元素： 

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

理论上这可能会无休止地运行，但在实践中它是好的。 越接近整个原始列表，运行时间越慢，但是这不是select随机子列表的重点，是吗？

Interesting Posts