Một thuật toán để tạo ngẫu nhiên các phân đoạn nguyên của một chiều dài cụ thể, bằng Python?

Question

Tôi đã sử dụng chức năng random_element() do SAGE cung cấp để tạo phân vùng số nguyên ngẫu nhiên cho một số nguyên nhất định (N) có độ dài cụ thể (S). Tôi đang cố tạo các mẫu ngẫu nhiên không thiên vị từ tập hợp tất cả các phân vùng cho các giá trị đã cho là N và S. Hàm SAGE nhanh chóng trả về các phân vùng ngẫu nhiên cho N (tức là Partitions(N).random_element()).

Tuy nhiên, nó chậm vô cùng khi thêm S (ví dụ: Partitions(N,length=S).random_element()). Tương tự, lọc ra các phân vùng ngẫu nhiên của N có chiều dài S cực kỳ chậm.

Tuy nhiên, và tôi hy vọng điều này sẽ giúp ai đó, tôi đã tìm thấy rằng trong trường hợp khi hàm trả về một phân vùng của N không phù hợp với độ dài S, mà phân vùng liên hợp thường có độ dài S. Đó là:

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

Điều này làm tăng tốc độ mà các phân vùng có độ dài S được tìm thấy và dường như để sản xuất mẫu không thiên vị (tôi đã kiểm tra kết quả chống lại cả một tập hợp các phân vùng cho các giá trị khác nhau của N và S).

Tuy nhiên, tôi đang sử dụng các giá trị của N (ví dụ: 10,000) và S (ví dụ: 300) làm cho phương pháp này thậm chí còn chậm một cách không chính xác. Nhận xét liên quan đến chức năng random_element() của SAGE thừa nhận có rất nhiều chỗ để tối ưu hóa. Vì vậy, có cách nào để tạo nhanh hơn các phân vùng số nguyên không thiên vị (ví dụ: ngẫu nhiên) các giá trị đã cho của N và S, có lẽ, bằng cách không tạo phân vùng không khớp với S? Ngoài ra, việc sử dụng phân vùng liên hợp hoạt động tốt trong nhiều trường hợp để tạo ra các mẫu không thiên vị, nhưng tôi không thể nói rằng tôi hiểu chính xác lý do tại sao.

Answer 1

Cuối cùng, tôi có một cách dứt khoát phương pháp không thiên vị có tỷ lệ từ chối không. Tất nhiên, tôi đã thử nghiệm nó để đảm bảo kết quả là mẫu đại diện của toàn bộ các bộ khả thi. Nó rất nhanh và hoàn toàn không thiên vị. Thưởng thức.

from sage.all import * 
import random 

Thứ nhất, một chức năng để tìm ra phụ chú tối đa nhỏ nhất cho một phân vùng của n với s phần

def min_max(n,s): 

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

    return _min 

Tiếp theo, Một chức năng có sử dụng một bộ nhớ cache và memoiziation để tìm số phân vùng của n với phần s có x là phần lớn nhất. Đây là nhanh, nhưng tôi nghĩ rằng có một giải pháp thanh lịch hơn để có được. ví dụ: Thông thường: P (N, S, max = K) = P (NK, S-1) Nhờ ante (https://stackoverflow.com/users/494076/ante) vì đã giúp tôi với điều này: 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)] 

Cuối cùng, một chức năng để tìm phân vùng ngẫu nhiên thống nhất của n với phần s, không có tỷ lệ từ chối! Mỗi mã số được chọn ngẫu nhiên cho một phân vùng cụ thể của n có phầ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

cách tiếp cận đơn giản: Sử dụng một cách ngẫu nhiên các số nguyên:

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

Answer 3

Tôi chạy vào một vấn đề tương tự khi tôi đã cố gắng để tính toán xác suất của vấn đề sinh nhật mạnh mẽ.

Trước hết, chức năng phân vùng phát nổ khi chỉ cho số lượng khiêm tốn. Bạn sẽ trả lại rất nhiều thông tin. Không có vấn đề gì phương pháp bạn đang sử dụng N = 10000 và S = 300 sẽ tạo ra vô số lượng dữ liệu. Nó sẽ chậm. Cơ hội là bất kỳ việc thực thi trăn thuần túy nào mà bạn sử dụng sẽ đều chậm hoặc chậm hơn. Hãy tìm cách tạo một CModule.

Nếu bạn muốn thử python cách tiếp cận tôi đã thực hiện như là một sự kết hợp của itertools và máy phát điện để giảm mức sử dụng bộ nhớ. Tôi dường như không có mã của tôi có ích nữa, nhưng đây là một impementation tốt:

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

EDIT:

Tìm thấy mã của tôi:

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