Làm cách nào để tạo phân vùng số nguyên ngẫu nhiên đồng đều?

Question

Một tìm kiếm của Google cho thấy rất nhiều về việc tạo tất cả các phân vùng có thể có của một số nguyên thành phần m, nhưng tôi không tìm thấy bất cứ điều gì về lấy mẫu phân vùng ngẫu nhiên phân bố đồng nhất của n thành phần m.

Answer 1

Dưới đây là một số mã thực hiện. Đây là O (n) lần đầu tiên bạn gọi nó, nhưng nó tạo bộ nhớ cache để các cuộc gọi tiếp theo là O (n).

import random 

cache = {} 

def count_partitions(n, limit): 
    if n == 0: 
     return 1 
    if (n, limit) in cache: 
     return cache[n, limit] 
    x = cache[n, limit] = sum(count_partitions(n-k, k) for k in range(1, min(limit, n) + 1)) 
    return x 

def random_partition(n): 
    a = [] 
    limit = n 
    total = count_partitions(n, limit) 
    which = random.randrange(total) 
    while n: 
     for k in range(1, min(limit, n) + 1): 
      count = count_partitions(n-k, k) 
      if which < count: 
       break 
      which -= count 
     a.append(k) 
     limit = k 
     n -= k 
    return a 

Cách hoạt động: Chúng tôi có thể tính toán có bao nhiêu phân vùng của một số nguyên n có trong thời gian O (n ) thời gian. Là một tác dụng phụ, điều này tạo ra một bảng kích thước O (n) mà chúng tôi sau đó có thể sử dụng để tạo ra các phân vùng k thứ của n, đối với bất kỳ số nguyên k, trong thời gian O (n).

Vì vậy, hãy để tổng số = số lượng phân vùng. Chọn một số ngẫu nhiên k từ 0 đến tổng số - 1. Tạo phân vùng thứ k.

Answer 2

Sau khi một số googling tôi tìm thấy một thuật toán cho điều này trong "Sổ tay thuật toán ứng dụng", which Google Books has indexed. Thuật toán được đưa ra trong phần 1.12.2, trên trang 31.

Answer 3

Chỉ một phiên bản khác trong C#.

using System; 
using System.Collections.Generic; 
using System.Linq; 
using System.Text; 

namespace ConsoleApplication6 
{ 
    class Program 
    { 
     static Random random = new Random(); 

     static void Main(string[] args) 
     { 
      PrintPartition(GetUniformPartition(24, 5)); 
      PrintPartition(GetUniformPartition(24, 5)); 
      PrintPartition(GetUniformPartition(24, 5)); 
      PrintPartition(GetUniformPartition(24, 5)); 
      PrintPartition(GetUniformPartition(24, 5)); 
      Console.ReadKey(); 
     } 

     static int[] GetUniformPartition(int input, int parts) 
     { 
      if(input<= 0 || parts <= 0) 
       throw new ArgumentException("invalid input or parts"); 
      if (input < MinUniformPartition(parts)) 
       throw new ArgumentException("input is to small"); 

      int[] partition = new int[parts]; 
      int sum = 0; 
      for (int i = 0; i < parts-1; i++) 
      { 
       int max = input - MinUniformPartition(parts - i - 1) - sum; 
       partition[i] = random.Next(parts - i, max); 
       sum += partition[i]; 
      } 
      partition[parts - 1] = input - sum; // last 
      return partition; 
     } 

     // sum of 1,2,3,4,..,n 
     static int MinUniformPartition(int n) 
     { 
      return n * n - 1; 
     } 

     static void PrintPartition(int[] p) 
     { 
      for (int i = 0; i < p.Length; i++) 
      { 
       Console.Write("{0},", p[i]); 
      } 
      Console.WriteLine(); 
     } 
    } 
} 

Mã này sẽ sản xuất sản lượng tiếp theo:

5,8,7,2,2, 
6,6,7,2,3, 
5,7,6,2,4, 
6,4,3,2,9, 
7,8,4,4,1, 

Answer 4

tôi đã thực hiện các giải pháp trên và thấy rằng nó hoạt động rất tốt nếu ai muốn để tính toán phân vùng nguyên cho n nhưng không liên quan đến m với. Nếu làm việc với n lớn, giới hạn đệ quy và ngăn xếp cuộc gọi có thể cần phải tăng lên rất nhiều.

Tuy nhiên, bạn không cần hàm đầu tiên vì count_partitions (n, giới hạn) sẽ thực sự bằng số lượng phân vùng của 'n + giới hạn' với số lượng 'giới hạn' các phần. Một số phần mềm toán học có chức năng rất nhanh để tìm số phân vùng n thành phần m.

Gần đây tôi đã lấy một phương pháp chắc chắn không thiên vị, rất đơn giản, và rất nhanh (sử dụng memoization) để giải quyết chính xác câu hỏi của bạn: An algorithm for randomly generating integer partitions of a particular length, in Python?

Nó dựa trên hiểu biết điều gì đó về phân vùng lexically lệnh của n có phần m và sử dụng cách tiếp cận tương tự với các thuật toán được chấp nhận tốt (ví dụ Nijenhuis và Wilf 1978) tìm các phân vùng ngẫu nhiên của n, và khái niệm tương tự như trên.

Tóm lại, nếu có x phân vùng n có phần m, thì chúng ta chọn một số ngẫu nhiên từ 1 đến x. Số ngẫu nhiên đó sẽ mã hóa cho một và chỉ một phân vùng thỏa mãn n và m. Tôi hi vọng cái này giúp được.

Answer 5

Tôi có trình tạo phân vùng đồng đều.

Trong đó n: = số nguyên được phân đoạn, r: = số lượng lát: Thuật toán là phiên bản được vá của phương pháp ngây thơ chỉ đơn giản là chèn các phần ngẫu nhiên. Vấn đề với phương pháp này, như nó xuất hiện với tôi khi tôi nhìn vào đầu ra của nó, là các tình huống mà các phần được đặt trong cùng một vị trí ít có khả năng xảy ra. Chỉ có một cách để có được {1,1,1}, trong khi có 3! cách nhận {2,4,9}, bất kỳ {4,2,9}, {2,4,9}, {9,4,2} ... sẽ dẫn đến cùng một vị trí phân vùng khi được sắp xếp. Điều này đã được sửa đổi bằng cách cung cấp thêm cơ hội rõ ràng để lặp lại. Đối với mỗi lần chia tách, có khả năng vị trí của phần chia sẽ không ngẫu nhiên, nhưng sẽ được chọn làm giá trị lặp lại của giá trị đã chọn trước đó. Điều này cân bằng phân bố xác suất không đồng đều của phương thức ngây thơ ngay lập tức.

Tôi đã chứng minh bằng sự kiệt sức rằng mỗi phân vùng là hoàn toàn bình đẳng có khả năng cho r = 3, n = 2. Tôi cbf chứng minh nó cho giá trị cao hơn nhưng liên doanh healfhearted để làm như vậy chỉ tìm thấy dấu hiệu đầy hứa hẹn. Tôi cũng đã thử nghiệm nó trên đầu vào ngẫu nhiên, thấy rằng nó là ít nhất là khoảng ngay cả đối với mọi giá trị tôi đã thử [nhưng có lẽ hoàn toàn thậm chí].

tại đây nó nằm trong C++ 11: [định dạng đầu ra khác với những gì bạn đang mong đợi, đó là vị trí của các phần thay vì kích thước khoảng trống giữa chúng. Tuy nhiên, chuyển đổi rất dễ dàng]

#include <vector> 
#include <algorithm> 
#include <random> 
#include <cassert> 
template <typename Parting, typename Seed> 
vector<Parting> partitionGen(unsigned nparts, unsigned bandw, Seed seed){//nparts is the number of parts, that is, one greater than the number of dividers listed in the output vector. Bandw is the integer being partitioned. 
    assert(nparts > 0); 
    vector<Parting> out(nparts-1); 
    srand(seed); 
    unsigned genRange = bandw; 
    for(auto i=out.begin(); i<out.end(); ++i, ++genRange){ 
     unsigned gen = rand()%genRange; 
     *i = ((gen<bandw)? 
      gen: 
      *(i-(gen-bandw+1))); 
    } 
    sort(out.begin(), out.end(), less<Parting>()); 
    return out; 
} 

Tôi không thích thực tế là tôi phải sắp xếp nó. Nếu phiên bản của Vlody có phân phối đồng đều, có vẻ như nó sẽ tốt hơn.

Answer 6

Tiêu đề của bài đăng này hơi gây hiểu nhầm. Phân vùng số nguyên ngẫu nhiên theo mặc định là không bị giới hạn, có nghĩa là nó có thể có nhiều phần ở mọi kích thước. Câu hỏi cụ thể được đặt ra là về phân vùng của n thành phần m, là một kiểu phân vùng số nguyên bị giới hạn.

Để tạo phân vùng nguyên không hạn chế, một thuật toán rất nhanh và đơn giản là do Fristedt, trong một giấy gọi là Cấu trúc phân đoạn ngẫu nhiên của số nguyên lớn (1993). Thuật toán như sau:

1. Đặt x = exp (-pi/sqrt (6n)).
2. Tạo các biến ngẫu nhiên độc lập Z (1), Z (2), ..., Z (n), trong đó Z (i) được phân bố hình học với tham số 1-x^i.
3. Nếu tổng i * Z (i) = n, trong đó tổng được tính trên tất cả i = 1,2, ..., n, thì DỪNG.
   ELSE, lặp lại 2.

Khi thuật toán dừng lại, sau đó Z (1) là số của 1s, Z (2) là số của 2s, vv, trong một phân vùng chọn đồng nhất một cách ngẫu nhiên. Xác suất chấp nhận một tập hợp Z được lựa chọn ngẫu nhiên là tiệm cận 1/(94n^3)^(1/4), có nghĩa là người ta sẽ chạy thuật toán này O (n^(3/4)) lần trước khi chấp nhận một mẫu vật.

Lý do tôi dành thời gian giải thích thuật toán này là vì nó áp dụng trực tiếp cho vấn đề tạo phân đoạn n thành chính xác phần m. Trước tiên, quan sát rằng

Số lượng phân đoạn của n thành phần m chính xác bằng với số lượng phân đoạn của n có phần lớn nhất bằng m.

Sau đó, chúng tôi có thể áp dụng thuật toán Fristedt trực tiếp, nhưng thay vì tạo Z (1), Z (2), ..., Z (n), chúng ta có thể tạo Z (1), Z (2),. .., Z (m-1), Z (m) +1 (+1 ở đây đảm bảo rằng phần lớn nhất chính xác là m, và 1 + Z (m) bằng nhau trong phân phối tới Z (m) có điều kiện trên Z (m)> = 1) và thiết lập tất cả Z (m + 1) khác, Z (m + 2), ... bằng 0. Sau đó, khi chúng ta thu được tổng đích ở bước 3, chúng ta cũng được đảm bảo có một mẫu không thiên vị . Để có được một phân vùng n thành chính xác phần m, đơn giản là lấy liên hợp của phân vùng được tạo ra.

Lợi thế này có trên phương pháp đệ quy của Nijenhuis và Wilf là không có yêu cầu bộ nhớ khác ngoài việc lưu trữ các biến ngẫu nhiên Z (1), Z (2), v.v. Ngoài ra, giá trị của x có thể bất cứ điều gì giữa 0 và 1 và thuật toán này vẫn không thiên vị! Tuy nhiên, việc chọn một giá trị tốt của x có thể làm cho thuật toán nhanh hơn nhiều, mặc dù lựa chọn trong Bước 1 gần như tối ưu cho các phân vùng nguyên không hạn chế.

Nếu n thực sự rất lớn và thuật toán của Fristedt mất quá nhiều thời gian (và các phương pháp bảng không có câu hỏi), thì có các tùy chọn khác, nhưng chúng phức tạp hơn một chút; xem luận án của tôi https://sites.google.com/site/stephendesalvo/home/papers để biết thêm thông tin về phân chia và chinh phục theo xác suất và các ứng dụng của nó.

Answer 7

Một thuật toán từ Combinatorial Algorithms trang 52, "ngẫu nhiên Thế hệ của n vào k phần"

1. Chọna1, a2, .., ak-1 một ngẫu nhiên k-1 tập hợp con của {1,2,..,n+k-1} (xem dưới đây 1., 2.)
2. Đặtr1=a1-1; rj=aj-aj-1-1 (j=2..k-1); rk= n+k-1-ak-1
3. Các rj (j=1..k) tạo thành phân vùng ngẫu nhiên của n vào k phần

Thuật toán này cho tác phẩm ngẫu nhiên dựa trên " quả bóng trong tế bào "mô hình.

Tóm lại, chúng tôi chọn các posiitons của ô ranh giới một cách ngẫu nhiên, sau đó bằng cách phân biệt chúng ta tìm ra số quả bóng nằm trong mỗi ô.

Để tạo hiệu quả một tập hợp con ngẫu nhiên của một bộ, nhìn thấy một 1. related answer here và 2. here

cập nhật

Một cách tiếp cận sử dụng một số ngẫu nhiên duy nhất trong [0,1] để thống nhất tạo ra một ngẫu nhiên phân vùng (còn gọi là thành phần) được đưa ra trong IVAN STOJMENOVIC, "ON RANDOM AND ADAPTIVE PARALLEL GENERATION OF COMBINATORIAL OBJECTS" (phần 5, phần 10)