Ответ 1

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

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

• Это время O(f+k) и память O(f+k). Очевидно, что это самая быстрая вещь без требований к формату forbid (отсортировано/установлено). Я думаю, что это делает этот победитель каким-то образом ^^.
• Если 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(n-i-1, n-i-1)
        state[x] = t
        track[t] = x
        state.pop(n-i-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()

Ответ 2

Если вы заранее знаете, что хотите получить несколько образцов без перекрытий, проще всего сделать 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 @Хронический ответ достаточно эффективен.

Ответ 3

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

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

Длинный путь

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

Здесь секрет:

• Квадратичные вычеты 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). Фактически, если вы используете galloping, вы можете довести это до 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()

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

Требования:

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

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

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

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

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

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

• прохлады.

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

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

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

Здесь rundown (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 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 и multiplier более распространены, чем идеальные генератор для них.

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

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 уходит с линейным конгруэнтным генератором (хотя он использует только младшие биты), я ожидал бы, что моя версия будет более чем достаточной.

Ответ 4

Хорошо, здесь мы идем. Это должен быть самый быстрый возможный невариантный алгоритм. Он имеет время выполнения 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). Это легко исправить, заменив этот список списком рассылок blist.

Я также добавил некоторые комментарии, потому что этот алгоритм смехотворно сложный. Часть lin выполняет то же самое, что и часть log, но требует s вместо 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 в методе Veedracs.

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

Вы можете опасаться дисперсии числа повторений. Как отмечено выше, это следует за геометрическим распределением с p=n-f/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) является абсолютно доминирующей частью во время выполнения.

Ответ 5

Вот способ, который явно не создает разницу. Но он использует форму логики "принимать/отклонять" @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)

Ответ 6

ОК, одна последняя попытка;-) За счет мутации базовой последовательности это не занимает дополнительного места и требует времени, пропорционального 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 не уничтожается, а перестраивается.

Ответ 7

Вы можете реализовать генератор перетасовки, основанный на Википедии "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]

Ответ 8

Изменить: см. более чистые версии ниже @TimPeters и @Chronial. Небольшое редактирование переместило это вверх.

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

Ниже показана демонстрационная реализация. По сравнению с другими решениями:

• нет циклов (нет стандартного Python/Veedrac hack; общий кредит между Python impl и Veedrac)
• сложность времени O(log(number_previously_sampled))
• сложность пространства 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)

Ответ 9

Это перезаписанная версия @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 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

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

Ответ 10

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

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

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))

Ответ 11

Довольно быстрый однострочный (O(n + m), n = range, m = old samplesize):

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