Algorytm losowego generowania partycji całkowitych o określonej długości, w języku Python?

Question

Używam funkcji random_element() dostarczonej przez SAGE do generowania losowych partycji całkowitych dla danej liczby całkowitej (N), które są określonej długości (S). Próbuję generować nieobciążonych losowych próbek ze zbioru wszystkich partycji dla danych wartości N i S. Funkcja SAGE szybko zwraca losowe partycje dla N (to jest Partitions(N).random_element()).

Powoduje jednak znaczne spowolnienie po dodaniu S (tj. Partitions(N,length=S).random_element()). Podobnie, filtrowanie losowych partycji N, które mają długość S, jest niesamowicie wolne.

jednak, i mam nadzieję, że to pomoże komuś, Znalazłem, że w przypadku, gdy funkcja zwraca rozbiór N nie dopasowując długość S, że partycja jest sprzężony często długości S. czyli:

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

zwiększa to szybkość, z jaką zostały znalezione partycje długości S i wydaje się produkować bezstronne próbek (mam badanie wyników wobec całych zestawów partycji dla różnych wartości N i S).

Jednak używam wartości N (np. 10,000) i S (np. 300), które powodują, że nawet to podejście jest niepraktycznie wolne. Komentarz związany z funkcją SAGE o random_element() przyznaje, że jest mnóstwo miejsca na optymalizację. Czy istnieje sposób na szybsze generowanie bezstronnych (tj. Losowych) próbek partycji całkowitych pasujących do podanych wartości N i S, być może, nie generując partycji, które nie pasują do S? Dodatkowo używanie sprzężonych partycji działa dobrze w wielu przypadkach w celu tworzenia bezstronnych próbek, ale nie mogę powiedzieć, że dokładnie rozumiem dlaczego.

Answer 1

Wreszcie mam definitywnie bezstronna metoda, która ma zerowy współczynnik odrzucenia. Oczywiście przetestowałem to, aby upewnić się, że wyniki są reprezentatywnymi próbkami całych możliwych zestawów. Jest bardzo szybki i całkowicie bezstronny. Cieszyć się.

from sage.all import * 
import random 

początku, funkcja znaleźć najmniejszą maksymalną składnikiem sumy dla partycji n z y części

def min_max(n,s): 

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

    return _min 

Następnie funkcyjnych wykorzystuje pamięć i memoiziation znaleźć szereg partycje nz częściami s zawierającymi x jako największą część. Jest to szybkie, ale myślę, że jest bardziej eleganckie rozwiązanie. na przykład, często P (N, S, max = K) = P (NK, S-1) Dzięki ante (https://stackoverflow.com/users/494076/ante) za pomoc z tym: 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)] 

Wreszcie funkcja wyszukiwania jednolitych losowych partycji nz częściami s, bez współczynnika odrzucania! Każda losowo wybrana liczba kodu dla określonego podziału n mającego części.

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

Proste podejście: losowo przypisać liczby całkowite:

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

Answer 3

wpadłem na podobny problem, kiedy starałem się obliczyć prawdopodobieństwo silnego problemu urodzinowy.

Po pierwsze, funkcja podziału eksploduje, gdy zostanie podana tylko skromna liczba liczb. Otrzymasz dużo informacji. Bez względu na to, z której metody korzystasz N = 10000, a S = 300 generuje absurdalne ilości danych. Będzie wolno. Jest szansa, że ​​dowolna implementacja czystego Pythona będzie równie powolna lub wolniejsza. Spójrz na tworzenie modemu.

Jeśli chcesz wypróbować Pythona podejście, które wziąłem jako połączenie itertools i generatorów, aby zmniejszyć zużycie pamięci. Nie wydaje się, że mój kod poręczny już, ale tutaj jest to dobry impementation:

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

EDIT:

Znaleziony mój kod:

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