Алгоритм случайного генерации целых разделов определенной длины в Python?

Question

Я использовал функцию random_element(), предоставленную SAGE, для генерации случайных целых разделов для заданного целого числа (N), которые являются определенной длиной (S). Я пытаюсь создать несмещенные случайные выборки из набора всех разделов для заданных значений N и S. Функция SAGE быстро возвращает случайные разделы для N (то есть Partitions(N).random_element()).

Однако при добавлении S (т. Е. Partitions(N,length=S).random_element()) он значительно замедляется. Аналогично, отбор случайных разделов N, имеющих длину S, невероятно медленный.

Однако, и я надеюсь, что это поможет кому-то, я обнаружил, что в случае, когда функция возвращает разбиение N не соответствует длине S, что сопряженное разбиение часто длины S. То есть:

S = 10 
N = 100 
part = list(Partitions(N).random_element()) 
    if len(part) != S: 
     SAD = list(Partition(part).conjugate()) 
     if len(SAD) != S: 
      continue 

Это увеличивает скорость, при которой разбиение длины S найдено и, как представляется, производить объективные образцы (я рассмотрел результаты против целых наборов разделов для различных значений N и S).

Однако я использую значения N (например, 10,000) и S (например, 300), которые делают этот подход непрактично медленным. Комментарий, связанный с функцией SAGE random_element(), допускает, что существует множество возможностей для оптимизации. Итак, есть ли способ быстрее генерировать несмещенные (то есть случайные равномерные) выборки целых разделов, соответствующие заданным значениям N и S, возможно, не генерируя разделы, которые не соответствуют S? Кроме того, использование сопряженных разделов во многих случаях хорошо работает для создания несмещенных образцов, но я не могу сказать, что я точно понимаю, почему.

Answer 1

Наконец, у меня окончательно несмещенный метод, который имеет нулевую скорость отклонения. Конечно, я проверил его, чтобы убедиться, что результаты являются репрезентативными образцами всех возможных наборов. Это очень быстро и совершенно беспристрастно. Наслаждаться.

from sage.all import * 
import random 

Во-первых, функция, чтобы найти наименьшее максимальное слагаемого для разбиения п с ы частей

def min_max(n,s): 

    _min = int(floor(float(n)/float(s))) 
    if int(n%s) > 0: 
     _min +=1 

    return _min 

Далее, функция, которая использует кэш и memoiziation, чтобы найти число перегородки из n с s частями, имеющими x как самую большую часть. Это быстро, но я думаю, что есть более элегантное решение. например, часто: P (N, S, макс = K) = P (NK, S-1) Благодаря анте (https://stackoverflow.com/users/494076/ante) за помощь мне с этим: Finding the number of integer partitions given a total, a number of parts, and a maximum summand

D = {} 
def P(n,s,x): 
    if n > s*x or x <= 0: return 0 
    if n == s*x: return 1 
    if (n,s,x) not in D: 
     D[(n,s,x)] = sum(P(n-i*x, s-i, x-1) for i in xrange(s)) 
    return D[(n,s,x)] 

Наконец, функция для нахождения равномерных случайных разбиений n с s частями, без скорости отклонения! Каждый случайно выбранный номер кодов для конкретного разбиения n, имеющего s частей.

def random_partition(n,s): 
    S = s 
    partition = [] 
    _min = min_max(n,S) 
    _max = n-S+1 

    total = number_of_partitions(n,S) 
    which = random.randrange(1,total+1) # random number 

    while n: 
     for k in range(_min,_max+1): 
      count = P(n,S,k) 
      if count >= which: 
       count = P(n,S,k-1) 
       break 

     partition.append(k) 
     n -= k 
     if n == 0: break 
     S -= 1 
     which -= count 
     _min = min_max(n,S) 
     _max = k 

    return partition 

Answer 2

Простой подход: случайным образом присваивать целые числа:

def random_partition(n, s): 
    partition = [0] * s 
    for x in range(n): 
     partition[random.randrange(s)] += 1 
    return partition 

Answer 3

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

Во-первых, функция разделения взрывается при задании только небольшого количества чисел. Вы будете получать много информации. Независимо от того, какой метод вы используете N = 10000 и S = ​​300, генерирует нелепые объемы данных. Это будет медленно. Скорее всего, любая чистая реализация python, которую вы используете, будет одинаково медленной или медленной. Посмотрите на создание CModule.

Если вы хотите попробовать python подход, который я взял в качестве комбинации itertools и генераторов, чтобы сохранить использование памяти. Я, кажется, не имеют свой код под рукой больше, но вот хороший impementation:

http://wordaligned.org/articles/partitioning-with-python

EDIT:

Найдено мой код:

def partition(a, b=-1, limit=365): 
    if (b == -1): 
    b = a 
    if (a == 2 or a == 3): 
    if (b >= a and limit): 
     yield [a] 
    else: 
     return 
    elif (a > 3): 
    if (a <= b): 
     yield [a] 
    c = 0 
    if b > a-2: 
     c = a-2 
    else: 
     c = b 
    for i in xrange(c, 1, -1): 
     if (limit): 
     for j in partition(a-i, i, limit-1): 
      yield [i] + j