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

问题描述

的问题给出了所有必要的数据：什么是一个有效的算法，以产生K个不重复一个给定的时间间隔内的整数序列。平凡算法（产生随机数，并把它们添加到所述序列，找起来，看他们是否已经有之前）是非常昂贵的，如果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. 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.

中提供的算法<一href="http://stackoverflow.com/questions/54059/efficiently-selecting-a-set-of-random-elements-from-a-linked-list">here似乎比必要更复杂，并且需要一些实施。我刚刚发现了另一种算法，似乎做的工作很好，只要你知道所有的相关参数，在一个单一的通行证。

The algorithm provided here 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.

推荐答案

从Python中的随机模块库使得它非常容易和有效的：

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

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

样品函数返回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.

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