Примечание для читателей от OP: Пожалуйста, рассмотрите первоначально принятый ответ, чтобы понять логику, а затем понять этот ответ.

Aaaaaand для полноты: это концепция ответа no_answer_not_upvoted , но адаптирована, поэтому в качестве входных данных требуется список запрещенных чисел. Это тот же код, что и в моем предыдущем ответе , но мы строим состояние от forbid , прежде чем будем генерировать числа.

• Это время O(f+k) и память O(f+k) . Очевидно, что это самая быстрая вещь без требований к формату forbid (sorted / set). Я думаю, что это делает это победителем в некотором роде ^^.
• Если forbid является множеством, метод повторной угадывания быстрее с O(k⋅n/(n-(f+k))) , который очень близок к O(k) для f+k не очень близкого к n .
• Если forbid сортируется, мой смешной алгоритм выполняется быстрее:
  

 import random def sample_gen(n, forbid): state = dict() track = dict() for (i, o) in enumerate(forbid): x = track.get(o, o) t = state.get(ni-1, ni-1) state[x] = t track[t] = x state.pop(ni-1, None) track.pop(o, None) del track for remaining in xrange(n-len(forbid), 0, -1): i = random.randrange(remaining) yield state.get(i, i) state[i] = state.get(remaining - 1, remaining - 1) state.pop(remaining - 1, None) 

Применение:

 gen = sample_gen(10, [1, 2, 4, 8]) print gen.next() print gen.next() print gen.next() print gen.next() 

Если вы заранее знаете, что хотите получить несколько выборок без перекрытий, проще всего сделать random.shuffle() в list(range(100)) (Python 3 – может пропустить list() в Python 2), затем отделите ломтики по мере необходимости.

 s = list(range(100)) random.shuffle(s) first_sample = s[-10:] del s[-10:] second_sample = s[-10:] del s[-10:] # etc 

Ответ Else @ Chronial достаточно эффективен.

Хорошо, здесь мы идем. Это должен быть самый быстрый возможный невариантный алгоритм. Он имеет время выполнения O(k⋅log²(s) + f⋅log(f)) ⊂ O(k⋅log²(f+k) + f⋅log(f))) и пространство O(k+f) . f – количество запрещенных номеров, s – длина самой длинной полосы запрещенных номеров. Ожидание этого более сложно, но, очевидно, связано с f . Если вы предположите, что s^log₂(s) больше f или просто недовольны тем фактом, что s снова вероятностен, вы можете изменить лог-часть на поиск пополам в forbidden[pos:] чтобы получить O(k⋅log(f+k) + f⋅log(f)) .

Фактическая реализация здесь O(k⋅(k+f)+f⋅log(f)) , поскольку вложение в список forbid O(n) . Это легко исправить, заменив этот список списком рассылок .

Я также добавил некоторые комментарии, потому что этот алгоритм смехотворно сложный. lin часть выполняет то же самое, что и log часть, но требует времени вместо log²(s) .

 import bisect import random def sample(k, end, forbid): forbidden = sorted(forbid) out = [] # remove the last block from forbidden if it touches end for end in reversed(xrange(end+1)): if len(forbidden) > 0 and forbidden[-1] == end: del forbidden[-1] else: break for i in xrange(k): v = random.randrange(end - len(forbidden) + 1) # increase v by the number of values < v pos = bisect.bisect(forbidden, v) v += pos # this number might also be already taken, find the # first free spot ##### linear #while pos < len(forbidden) and forbidden[pos] <=v: # pos += 1 # v += 1 ##### log while pos < len(forbidden) and forbidden[pos] <= v: step = 2 # when this is finished, we know that: # • forbidden[pos + step/2] <= v + step/2 # • forbidden[pos + step] > v + step # so repeat until (checked by outer loop): # forbidden[pos + step/2] == v + step/2 while (pos + step <= len(forbidden)) and \ (forbidden[pos + step - 1] <= v + step - 1): step = step << 1 pos += step >> 1 v += step >> 1 if v == end: end -= 1 else: bisect.insort(forbidden, v) out.append(v) return out 

Теперь, чтобы сравнить это с «взломом» (и реализацией по умолчанию в python), которую предложил Veedrac, который имеет пространство O(f+k) и ( n/(n-(f+k)) – ожидаемое количество «догадок» " ) Время:

Я просто построил это для k=10 и достаточно большой n=10000 (он становится более экстремальным для большего n ). И я должен сказать: я только реализовал это, потому что мне показалось, что это интересная задача, но даже я удивлен, насколько это экстремально:

Давайте увеличим масштаб, чтобы увидеть, что происходит:

Да – догадки еще быстрее для 9998-го числа, которое вы создаете. Обратите внимание, что, как вы можете видеть на первом графике, даже мой однострочный шрифт, вероятно, быстрее для больших f/n (но все еще имеет довольно ужасные требования к пространству для большого n ).

Чтобы проехать домой: единственное, что вы тратите на это, – это генерировать набор, так как это фактор f в методе Veedrac.

Поэтому я надеюсь, что мое время здесь не пропало даром, и мне удалось убедить вас, что метод Видрака – это просто путь. Я могу понять, почему эта вероятностная часть вас беспокоит, но, может быть, подумайте о том, что хэшмапы (= python dict s) и тонны других алгоритмов работают с подобными методами, и они, кажется, все в порядке.

Вы можете бояться разницы в количестве повторений. Как отмечалось выше, это следует за геометрическим распределением с p=nf/n . Таким образом, стандартное отклонение (= сумма, которую вы «должны ожидать», чтобы результат отклонился от ожидаемого среднего)

Это в основном то же самое, что и среднее ( √f⋅n < √n² = n ).

****редактировать**:
Я просто понял, что s на самом деле также n/(n-(f+k)) . Таким образом, более точное время выполнения для моего алгоритма – O(k⋅log²(n/(n-(f+k))) + f⋅log(f)) . Что хорошо, поскольку с учетом приведенных выше графиков, это доказывает мою интуицию, что это довольно быстро, чем O(k⋅log(f+k) + f⋅log(f)) . Но будьте уверены, что это также ничего не меняет о результатах выше, поскольку f⋅log(f) является абсолютно доминирующей частью во время выполнения.

Короткий путь

Если число, отобранное, намного меньше, чем население, просто выберите образец, проверьте, было ли оно выбрано, и повторите, пока это так. Это может показаться глупым, но у вас есть экспоненциально разлагающаяся возможность выбора одного и того же числа, поэтому он намного быстрее, чем O(n) если у вас есть даже небольшой процент unchosen.

---

Длинный путь

Python использует Mersenne Twister в качестве своего PRNG, что является хорошим адекватным . Мы можем использовать что-то еще, чтобы иметь возможность генерировать непересекающиеся числа предсказуемым образом.

Вот секрет:

• Квадратичные вычеты, x² mod p , являются единственными, когда 2x < p и p – простое число.

• Если вы «переверните» остаток, p - (x² % p) , учитывая это время также, что p = 3 mod 4 , результаты будут остальными.

• Это не очень убедительное числовое распространение, поэтому вы можете увеличить мощность, добавить некоторые константы выдумки, а затем распределение довольно хорошее.

---

Сначала нам нужно генерировать простые числа:

 from itertools import count from math import ceil from random import randrange def modprime_at_least(number): if number <= 2: return 2 number = (number // 4 * 4) + 3 for number in count(number, 4): if all(number % factor for factor in range(3, ceil(number ** 0.5)+1, 2)): return number 

Вы можете беспокоиться о стоимости генерации простых чисел. Для 10⁶ элементов это занимает десятую часть миллисекунды. Запуск [None] * 10**6 занимает больше времени, и, поскольку он вычисляется только один раз, это не проблема.

Кроме того, алгоритм не нуждается в точном значении для простого; требуется только то, что не более, чем постоянный множитель, больший, чем входной. Это возможно, сохраняя список значений и их поиск. Если вы выполняете линейное сканирование, это O(log number) и если вы выполняете двоичный поиск, это O(log number of cached primes) . Фактически, если вы используете галопирование, вы можете довести это до O(log log number) , который в основном постоянный ( log log googol = 2 ).

Затем мы реализуем генератор

 def sample_generator(up_to): prime = modprime_at_least(up_to+1) # Fudge to make it less predictable fudge_power = 2**randrange(7, 11) fudge_constant = randrange(prime//2, prime) fudge_factor = randrange(prime//2, prime) def permute(x): permuted = pow(x, fudge_power, prime) return permuted if 2*x <= prime else prime - permuted for x in range(prime): res = (permute(x) + fudge_constant) % prime res = permute((res * fudge_factor) % prime) if res < up_to: yield res 

И убедитесь, что он работает:

 set(sample_generator(10000)) ^ set(range(10000)) #>>> set() 

Теперь самое замечательное в том, что если вы проигнорируете тест primacy, который приблизительно равен O(√n) где n – количество элементов, этот алгоритм имеет временную сложность O(k) , где k – размер выборки и O(1) использование памяти! Технически это O(√n + k) , но практически это O(k) .

---

Требования:

1. Вам не требуется проверенный PRNG. Этот PRNG намного лучше, чем линейный конгруэнтный генератор (который пользуется популярностью, Java использует его ), но это не так доказано, как Mersenne Twister.

2. Вы не генерируете первые элементы с другой функцией. Это позволяет избежать дублирования посредством математики, а не проверки. В следующем разделе я покажу, как удалить это ограничение.

3. Короткий метод должен быть недостаточным ( k должен приближаться к n ). Если k – только половина n , просто пойдите с моим первоначальным предложением.

Преимущества:

1. Экономия памяти. Это занимает постоянную память … даже O(k) !

2. Постоянное время для создания следующего элемента. Это на самом деле довольно быстро и в постоянном выражении: это не так быстро, как встроенный Mersenne Twister, но он находится в 2 раза.

3. Прохлада.

---

Чтобы удалить это требование:

Вы не генерируете первые элементы с другой функцией. Это позволяет избежать дублирования посредством математики, а не проверки.

Я сделал наилучший алгоритм во времени и пространстве, который является простым расширением моего предыдущего генератора.

Вот краткое изложение ( n – длина пула чисел, k – количество «иностранных» ключей):

Время инициализации O(√n) ; O(log log n) для всех разумных входов

Это единственный фактор моего алгоритма, который технически не идеален в отношении алгоритмической сложности, благодаря стоимости O(√n) . На самом деле это не будет проблематичным, поскольку предварительная калькуляция сводит его до O(log log n) которая неизмеримо близка к постоянному времени.

Стоимость амортизируется бесплатно, если вы исчерпаете итерируемый какой-либо фиксированный процент.

Это не практическая проблема.

Амортизированное время генерации ключа O(1)

Очевидно, это невозможно улучшить.

Время генерации ключа наихудшего случая O(k)

Если у вас есть ключи, созданные снаружи, только с требованием, чтобы он не был ключом, который этот генератор уже произвел, их следует называть «внешними ключами». Внешние ключи считаются полностью случайными. Таким образом, любая функция, которая может выбирать элементы из пула, может это сделать.

Потому что может быть любое количество внешних ключей, и они могут быть абсолютно случайными, худшим случаем для идеального алгоритма является O(k) .

Сложная пространственная сложность O(k)

Если внешние ключи считаются полностью независимыми, каждый представляет собой отдельный элемент информации. Следовательно, все ключи должны быть сохранены. Алгоритм отбрасывает ключи всякий раз, когда видит один, поэтому стоимость памяти будет снижаться в течение всего срока службы генератора.

Алгоритм

Ну, это оба моих алгоритма. На самом деле это довольно просто:

 def sample_generator(up_to, previously_chosen=set(), *, prune=True): prime = modprime_at_least(up_to+1) # Fudge to make it less predictable fudge_power = 2**randrange(7, 11) fudge_constant = randrange(prime//2, prime) fudge_factor = randrange(prime//2, prime) def permute(x): permuted = pow(x, fudge_power, prime) return permuted if 2*x <= prime else prime - permuted for x in range(prime): res = (permute(x) + fudge_constant) % prime res = permute((res * fudge_factor) % prime) if res in previously_chosen: if prune: previously_chosen.remove(res) elif res < up_to: yield res 

Это изменение так же просто, как добавление:

 if res in previously_chosen: previously_chosen.remove(res) 

Вы можете добавить в previously_chosen в любое время, добавив в set который вы передали. Фактически вы также можете удалить из набора, чтобы добавить обратно в потенциальный пул, хотя это будет работать, только если sample_generator еще не дал его или пропустить его с помощью prune=False .

Так есть. Легко видеть, что он выполняет все требования, и легко видеть, что требования являются абсолютными. Обратите внимание: если у вас нет набора, он по-прежнему удовлетворяет наихудшим случаям, преобразовывая вход в набор, хотя он увеличивает накладные расходы.

---

Проверка качества RNG

Мне стало интересно, насколько хорош этот PRNG на самом деле, статистически.

Некоторые быстрые поиски привели меня к созданию этих трех тестов, которые, похоже, показывают хорошие результаты!

Во-первых, некоторые случайные числа:

 N = 1000000 my_gen = list(sample_generator(N)) target = list(range(N)) random.shuffle(target) control = list(range(N)) random.shuffle(control) 

Это «перетасованные» списки из 10⁶ чисел от 0 до 10⁶-1 , один из которых использует наш веселый PRUG, а другой – Mersenne Twister в качестве базовой линии. Третий – это контроль.

---

Вот тест, который рассматривает среднее расстояние между двумя случайными числами вдоль линии. Различия сравниваются с контролем:

 from collections import Counter def birthdat_calc(randoms): return Counter(abs(r1-r2)//10000 for r1, r2 in zip(randoms, randoms[1:])) def birthday_compare(randoms_1, randoms_2): birthday_1 = sorted(birthdat_calc(randoms_1).items()) birthday_2 = sorted(birthdat_calc(randoms_2).items()) return sum(abs(n1 - n2) for (i1, n1), (i2, n2) in zip(birthday_1, birthday_2)) print(birthday_compare(my_gen, target), birthday_compare(control, target)) #>>> 9514 10136 

Это меньше, чем разница.

---

Вот тест, который поочередно занимает 5 номеров и видит, в каком порядке находятся элементы. Они должны быть равномерно распределены между всеми 120 возможными заказами.

 def permutations_calc(randoms): permutations = Counter() for items in zip(*[iter(randoms)]*5): sorteditems = sorted(items) permutations[tuple(sorteditems.index(item) for item in items)] += 1 return permutations def permutations_compare(randoms_1, randoms_2): permutations_1 = permutations_calc(randoms_1) permutations_2 = permutations_calc(randoms_2) keys = sorted(permutations_1.keys() | permutations_2.keys()) return sum(abs(permutations_1[key] - permutations_2[key]) for key in keys) print(permutations_compare(my_gen, target), permutations_compare(control, target)) #>>> 5324 5368 

Это опять же меньше, чем разница.

---

Вот тест, который видит, как долго «работает», ака. разделы последовательного увеличения или уменьшения.

 def runs_calc(randoms): runs = Counter() run = 0 for item in randoms: if run == 0: run = 1 elif run == 1: run = 2 increasing = item > last else: if (item > last) == increasing: run += 1 else: runs[run] += 1 run = 0 last = item return runs def runs_compare(randoms_1, randoms_2): runs_1 = runs_calc(randoms_1) runs_2 = runs_calc(randoms_2) keys = sorted(runs_1.keys() | runs_2.keys()) return sum(abs(runs_1[key] - runs_2[key]) for key in keys) print(runs_compare(my_gen, target), runs_compare(control, target)) #>>> 1270 975 

Дисперсия здесь очень велика, и в нескольких исполнениях я кажусь равномерным распространением обоих. Таким образом, этот тест передается.

---

Линейный конгруэнтный генератор был упомянут мне, возможно, «более плодотворным». Я сделал плохо реализованный LCG, чтобы узнать, является ли это точным заявлением.

LCG, AFAICT, как обычные генераторы, так как они не являются циклическими . Поэтому большинство ссылок я смотрел, ака. Википедия, охватывала только то, что определяет период, а не как сделать сильный LCG определенного периода. Это может повлиять на результаты.

Вот оно:

 from operator import mul from functools import reduce # Credit http://stackoverflow.com/a/16996439/1763356 # Meta: Also Tobias Kienzler seems to have credit for my # edit to the post, what's up with that? def factors(n): d = 2 while d**2 <= n: while not n % d: yield d n //= d d += 1 if n > 1: yield n def sample_generator3(up_to): for modulier in count(up_to): modulier_factors = set(factors(modulier)) multiplier = reduce(mul, modulier_factors) if not modulier % 4: multiplier *= 2 if multiplier < modulier - 1: multiplier += 1 break x = randrange(0, up_to) fudge_constant = random.randrange(0, modulier) for modfact in modulier_factors: while not fudge_constant % modfact: fudge_constant //= modfact for _ in range(modulier): if x < up_to: yield x x = (x * multiplier + fudge_constant) % modulier 

Мы больше не проверяем простые числа, но нам нужно делать некоторые странные вещи с факторами.

• modulier ≥ up_to > multiplier, fudge_constant > 0
• a - 1 должен быть делимым каждым фактором в modulier …
• … тогда как fudge_constant должен быть взаимно прост с modulier

Обратите внимание, что это не правила для LCG, а LCG с полным периодом, который, очевидно, равен mod ulier.

Я сделал это как таковой:

• Попробуйте каждый modulier по крайней мере, up_to , останавливаясь при выполнении условий
  • Составьте набор его факторов, 𝐅
  • Пусть multiplier является произведением 𝐅 с удаленными дубликатами
  • Если multiplier не меньше, чем modulier , продолжайте со следующего modulier
  • Пусть fudge_constant будет меньше, чем modulier , выбранный случайным образом
  • Удалите факторы из fudge_constant которые находятся в 𝐅

Это не очень хороший способ его генерации, но я не понимаю, почему это когда-либо будет влиять на качество чисел, кроме того, что низкие fudge_constant s и multiplier более распространены, чем идеальный генератор для этих fudge_constant .

Во всяком случае, результаты ужасающие :

 print(birthday_compare(lcg, target), birthday_compare(control, target)) #>>> 22532 10650 print(permutations_compare(lcg, target), permutations_compare(control, target)) #>>> 17968 5820 print(runs_compare(lcg, target), runs_compare(control, target)) #>>> 8320 662 

Таким образом, мой RNG хорош, а линейный конгруэнтный генератор – нет. Учитывая, что Java уходит с линейным конгруэнтным генератором (хотя он использует только младшие разряды), я ожидаю, что моя версия будет более чем достаточной.

Вот способ, который не создает явно установленную разницу. Но он использует форму логики «принять / отклонить» Veedrac. Если вы не хотите мутировать базовую последовательность по ходу дела, я боюсь, что это неизбежно:

 def sample(n, base, forbidden): # base is iterable, forbidden is a set. # Every element of forbidden must be in base. # forbidden is updated. from random import random nusable = len(base) - len(forbidden) assert nusable >= n result = [] if n == 0: return result for elt in base: if elt in forbidden: continue if nusable * random() < n: result.append(elt) forbidden.add(elt) n -= 1 if n == 0: return result nusable -= 1 assert False, "oops!" 

Вот небольшой драйвер:

 base = list(range(100)) forbidden = set() for i in range(10): print sample(10, base, forbidden) 

ОК, одна последняя попытка 😉 За счет мутации базовой последовательности это не занимает дополнительного места и требует времени, пропорционального n для каждого вызова sample(n) :

 class Sampler(object): def __init__(self, base): self.base = base self.navail = len(base) def sample(self, n): from random import randrange if n < 0: raise ValueError("n must be >= 0") if n > self.navail: raise ValueError("fewer than %s unused remain" % n) base = self.base for _ in range(n): i = randrange(self.navail) self.navail -= 1 base[i], base[self.navail] = base[self.navail], base[i] return base[self.navail : self.navail + n] 

Маленький водитель:

 s = Sampler(list(range(100))) for i in range(9): print s.sample(10) print s.sample(1) print s.sample(1) 

По сути, это реализует возобновляемую random.shuffle() , приостанавливая после того, как было выбрано n элементов. base не разрушается, а перестраивается.

Вы можете реализовать генератор перетасовки, основанный на википедии «Fisher – Yates shuffle # Modern method»

 def shuffle_gen(src): """ yields random items from base without repetition. Clobbers `src`. """ for remaining in xrange(len(src), 0, -1): i = random.randrange(remaining) yield src[i] src[i] = src[remaining - 1] 

Которая может быть нарезана с помощью itertools.islice :

 >>> import itertools >>> sampler = shuffle_gen(range(100)) >>> sample1 = list(itertools.islice(sampler, 10)) >>> sample1 [37, 1, 51, 82, 83, 12, 31, 56, 15, 92] >>> sample2 = list(itertools.islice(sampler, 80)) >>> sample2 [79, 66, 65, 23, 63, 14, 30, 38, 41, 3, 47, 42, 22, 11, 91, 16, 58, 20, 96, 32, 76, 55, 59, 53, 94, 88, 21, 9, 90, 75, 74, 29, 48, 28, 0, 89, 46, 70, 60, 73, 71, 72, 93, 24, 34, 26, 99, 97, 39, 17, 86, 52, 44, 40, 49, 77, 8, 61, 18, 87, 13, 78, 62, 25, 36, 7, 84, 2, 6, 81, 10, 80, 45, 57, 5, 64, 33, 95, 43, 68] >>> sample3 = list(itertools.islice(sampler, 20)) >>> sample3 [85, 19, 54, 27, 35, 4, 98, 50, 67, 69] 

Это переписанная версия замечательного решения @ no_answer_not_upvoted. Обертывает его в классе, чтобы сделать его намного проще в использовании, и использует больше методов dict для сокращения строк кода.

 from random import randrange class Sampler: def __init__(self, n): self.n = n # number remaining from original range(n) # i is a key iff i < n and i already returned; # in that case, state[i] is a value to return # instead of i. self.state = dict() def get(self): n = self.n if n <= 0: raise ValueError("range exhausted") result = i = randrange(n) state = self.state # Most of the fiddling here is just to get # rid of state[n-1] (if it exists). It's a # space optimization. if i == n - 1: if i in state: result = state.pop(i) elif i in state: result = state[i] if n - 1 in state: state[i] = state.pop(n - 1) else: state[i] = n - 1 elif n - 1 in state: state[i] = state.pop(n - 1) else: state[i] = n - 1 self.n = n-1 return result 

Вот основной драйвер:

 s = Sampler(100) allx = [s.get() for _ in range(100)] assert sorted(allx) == list(range(100)) from collections import Counter c = Counter() for i in range(6000): s = Sampler(3) one = tuple(s.get() for _ in range(3)) c[one] += 1 for k, v in sorted(c.items()): print(k, v) 

и выборки:

 (0, 1, 2) 1001 (0, 2, 1) 991 (1, 0, 2) 995 (1, 2, 0) 1044 (2, 0, 1) 950 (2, 1, 0) 1019 

С глазным яблоком это распределение прекрасное (запустите тест на квадрат, если вы скептически настроены). Некоторые из решений здесь не дают каждой перестановки с равной вероятностью (даже при random.sample() что они возвращают каждое k-подмножество n с равной вероятностью), так что они отличаются от random.sample() в этом отношении.

Это моя версия Knuth shuffle, которая была впервые опубликована Тимом Петерсом , приукрашенная Эриком, а затем красиво оптимизированная по пространству no_answer_not_upvoted .

Это основано на версии Эрика, так как я действительно нашел его код очень красивым :).

 import random def shuffle_gen(n): # this is used like a range(n) list, but we don't store # those entries where state[i] = i. state = dict() for remaining in xrange(n, 0, -1): i = random.randrange(remaining) yield state.get(i,i) state[i] = state.get(remaining - 1,remaining - 1) # Cleanup – we don't need this information anymore state.pop(remaining - 1, None) 

Применение:

 out = [] gen = shuffle_gen(100) for n in range(100): out.append(gen.next()) print out, len(set(out)) 

Edit: see cleaner versions below by @TimPeters and @Chronial. A minor edit pushed this to the top.

Here is what I believe is the most efficient solution for incremental sampling. Instead of a list of previously sampled numbers, the state to be maintained by the caller comprises a dictionary that is ready for use by the incremental sampler, and a count of numbers remaining in the range.

The following is a demonstrative implementation. По сравнению с другими решениями:

• no loops (no Standard Python/Veedrac hack; shared credit between Python impl and Veedrac)
• time complexity is O(log(number_previously_sampled))
• space complexity is O(number_previously_sampled)

Код:

 import random def remove (i, n, state): if i == n - 1: if i in state: t = state[i] del state[i] return t else: return i else: if i in state: t = state[i] if n - 1 in state: state[i] = state[n - 1] del state[n - 1] else: state[i] = n - 1 return t else: if n - 1 in state: state[i] = state[n - 1] del state[n - 1] else: state[i] = n - 1 return i s = dict() for n in range(100, 0, -1): print remove(random.randrange(n), n, s) 

Reasonably fast one-liner ( O(n + m) , n=range,m=old samplesize):

 next_sample = random.sample(set(range(100)).difference(my_sample), 10)