你如何有效地生成一个介于 0 和上限 N 之间的 K 个非重复整数的列表 [英] How do you efficiently generate a list of K non-repeating integers between 0 and an upper bound N

问题描述

问题给出了所有必要的数据:在给定区间内生成K个非重复整数序列的有效算法是什么[0,N-1].如果 K 很大且足够接近 N.

The question gives all necessary data: what is an efficient algorithm to generate a sequence of K non-repeating integers within a given interval [0,N-1]. The trivial algorithm (generating random numbers and, before adding them to the sequence, looking them up to see if they were already there) is very expensive if K is large and near enough to N.

中提供的算法来自链表的一组随机元素 似乎比必要的更复杂，需要一些实现.我刚刚找到了另一种算法，它似乎可以很好地完成这项工作，只要您一次性了解所有相关参数即可.

The algorithm provided in Efficiently selecting a set of random elements from a linked list seems more complicated than necessary, and requires some implementation. I've just found another algorithm that seems to do the job fine, as long as you know all the relevant parameters, in a single pass.

推荐答案

random 模块 使它变得非常简单和有效:

The random module from Python library makes it extremely easy and effective:

from random import sample
print sample(xrange(N), K)

sample 函数返回从给定序列中选择的 K 个唯一元素的列表.
xrange 是一个列表模拟器"，即它的行为就像一个连续数字的列表，而无需在内存中创建它，这使得它对于此类任务的速度非常快.

sample function returns a list of K unique elements chosen from the given sequence.
xrange is a "list emulator", i.e. it behaves like a list of consecutive numbers without creating it in memory, which makes it super-fast for tasks like this one.

这篇关于你如何有效地生成一个介于 0 和上限 N 之间的 K 个非重复整数的列表的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！