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

Question

我如何从一个ArrayList<E>？理想情况下,我希望能够连续调用该take()方法来获取另一个x元素,而无需替换.

Answer 1

两种主要方式.

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方法; 不,没有内置的.Comparator#randomOrder()标准API中没有这样的东西(但是？).您可以尝试类似下面的东西,同时仍然满足严格的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().

Answer 2

到目前为止,大多数提议的解决方案建议通过检查唯一性来进行完整列表随机选择或连续随机选择,并在需要时重试.

但是,我们可以利用Durstenfeld的算法(我们这个时代最受欢迎的Fisher-Yates变体).

Durstenfeld的解决方案是通过在每次迭代时使用最后一个未敲击的数字交换它们,将"已敲击"的数字移动到列表的末尾.

由于上述原因,我们不需要对整个列表进行混洗,而是运行循环,以获得返回所需元素数量的步骤.如果我们使用完美的随机函数,该算法确保列表末尾的最后N个元素是100%随机的.

在我们需要从阵列/列表中选择预定(最大)量的随机元素的众多现实场景中,这种优化的方法对于各种纸牌游戏非常有用,例如德州扑克,在那里你先验知道这个数字每场比赛使用的牌数; 从甲板上通常只需要有限数量的卡片.

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

如果你想连续从列表中选择n个元素并且无需一遍又一遍地进行替换,那么最好随机置换元素,然后以n块为单位取出块.如果您随机置换列表,则可以保证您选择的每个块的统计随机性.也许最简单的方法就是使用Collections.shuffle.

Answer 4

简单明了

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

正如其他答案中所述，Collections.shuffle当源列表很大时，由于复制，效率不是很高。这是 Java 8 的单行代码：

• 如果您不需要源中的许多元素，那么在像 ArrayList 这样的随机访问列表上足够高效
• 不修改源
• 如果它对您来说不是非常重要，则不保证唯一性。如果您从一百个元素中挑选五个，那么这些元素很有可能是独一无二的。

代码：

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

然而，对于没有快速随机访问的列表（如 LinkedList），复杂度将为n*O(list_size)。

Answer 6

一个公平的方法是通过列表,在第n次迭代计算是否选择第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;
}

(此代码是从我之前写的一个页面中复制的,从列表中选择一个随机样本.)