Какое подмножество вы получите, во многом будет зависеть от критерия, который вы указываете для включения или исключения элементов.Если у вас есть функция criterion, которая принимает элемент и возвращает логическое значение для указания включения в подмножество, фактический процесс создания становится просто
from random import randrange
def random_subset(s, criterion=lambda x: randrange(2)):
return set(filter(criterion, s))
filter создает ленивый генератор, поэтому возвращаемое подмножествоэто единственное место, где хранится выбор.Критерий по умолчанию очень прост и имеет равномерное распределение.randrange аналогично randint за исключением того, что оно является исключительным в правой части.По крайней мере, в Python 3.2+ обе функции выдают довольно однородные результаты независимо от размера диапазона.
Вы можете дополнительно уточнить критерий, используя random:
from random import random
criterion = lambda x: random() < 0.5
Применение такого порога может показаться излишним, но оно позволяет вам настроить распределение.У вас может быть функция, которая генерирует критерии для любого порога, который вам нравится:
def make_criterion(threshold=0.5):
return lambda x: random() < threshold
Вы можете использовать его, чтобы получить меньшее подмножество:
random_subset(s, make_criterion(0.1))
Фактически, вы можете сделать критерийтак сложно, как хотелось бы.Следующий пример - это надуманный вызываемый класс, который работает с наборами строк.Если строка с соответствующим первым символом уже добавлена, она автоматически отклоняет текущий элемент.Если вторая буква уже была замечена, она устанавливает вероятность включения в 0,25.В противном случае он подбрасывает монету:
class WeirdCriterion:
def __init__(self):
self.first = set()
self.second = set()
def __call__(self, x):
n = len(x)
if n > 0:
if x[0] in self.first:
return False
self.first.add(x[0])
if n > 1:
if x[1] in self.second:
return not randrange(4)
self.second.add(x[1])
return randrange(2)
Этот пример не очень хорош на практике, поскольку множества неупорядочены и могут давать разные порядки итераций между различными запусками одного и того же сценария.Однако он показывает метод создания критерия, который является случайным, но настраивается в ответ на элементы, которые уже находятся в подмножестве.
Избегание Numpy
Теперь, когда я лучше понимаю ваше первоначальное намерение, вы можете использовать тот факт, что Python 3 имеет целые числа бесконечной длины и что choices принимает параметр длины для получения правильной длины.Однако я не рекомендую такой подход:
from random import choices, sample
from math import factorial
def random_subset(s):
n = len(s)
nf = factorial(n)
# yes, there are better ways of doing this, even in pure python
weights = [nf / (factorial(k) * factorial(n - k)) for k in range(n + 1)]
length = choices(range(n + 1), weights, k=1)[0]
return sample(s, length)
Лучшим решением для вычисления биномиальных коэффициентов может быть что-то вроде:
def pascal(n):
result = [1] * (n + 1)
if n < 2:
return result
for i in range(2, n + 1):
for j in range(i - 1, 0, -1):
result[j] += result[j - 1]
return result