<h2>算法</h2>
<pre><code>import random
def randoms():
while True:
yield random.randint(0,9)
def no_repeat(source_iter, length):
seen = set()
cycle_pos = 0
while True:
n = next(source_iter)
if n not in seen:
yield n
cycle_pos += 1
seen.add(n)
if cycle_pos == length:
seen.clear()
cycle_pos = 0
rep = no_repeat(randoms(), 10)
print([next(rep) for i in range(100)]) # take 100 items from the `rep` iterator and put them into a list
</code></pre>
<p><code>randoms</code>函数是一个生成器,它给出无限个随机数。
<code>no_repeat</code>函数是一个生成器,它将生成器作为参数并对其进行过滤,以便长度为10的每个部分都没有重复</p>
<p>通过组合这些生成器,可以生成一个迭代器,该迭代器在每个长度为10的序列中生成无重复的随机数</p>
<h2>复杂性</h2>
<p>如果您假设可能的随机数的范围远大于“周期长度”,则生成<code>O(n)</code>个数是<code>n</code>,因为每次迭代都会生成一个随机数,生成它,并将其添加到集合中。假设集合是一个哈希表,那么这个加法是<code>O(1)</code>(检查它是否在集合中也是如此)。如果清除一个集合是<code>O(n)</code>,那么如果每10个操作执行一次,并且所需时间与10成比例,那么这将分摊到每次迭代的<code>O(1)</code></p>
<p>如果要考虑更小范围的可能数字,那么对于循环长度<code>k</code>,在循环开始时,每次迭代<code>O(1)</code>,则存在冲突的<code>1/k</code>概率,然后对于下一次迭代<code>2/k</code>概率等,直到在<code>k</code>迭代后重置。
因此它是<code>O(k^2 n)</code>,但是这个<code>k</code>是固定的(在你的例子中它总是10),所以实际上它可以被认为是一个常数因子,使得它等价于<code>O(n)</code></p>