Pertanyaan Bagaimana cara menghasilkan partisi integer acak seragam?


Pencarian Google mengungkapkan banyak tentang menghasilkan semua partisi yang mungkin dari sebuah integer n ke bagian m, tetapi saya belum menemukan apa-apa tentang sampling partisi acak terdistribusi acak dari n ke bagian m.


17
2018-01-29 10:57


asal


Jawaban:


Berikut ini beberapa kode yang melakukannya. Ini adalah O (n2) saat pertama kali Anda memanggilnya, tetapi ia membangun cache sehingga panggilan selanjutnya adalah 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

Bagaimana ini bekerja: Kita dapat menghitung berapa banyak partisi dari sebuah integer n ada di O (n2) waktu. Sebagai efek samping, ini menghasilkan tabel ukuran O (n2) yang kemudian dapat kita gunakan untuk menghasilkan kpartisi th dari n, untuk bilangan bulat apa pun k, saya tidak(n) waktu.

Jadi biarkan total = jumlah partisi. Pilih nomor acak k dari 0 hingga total - 1. Hasilkan kpartisi th.


8
2018-01-29 17:24



Judul posting ini agak menyesatkan. Sebuah partisi bilangan bulat acak secara default tidak dibatasi, artinya dapat memiliki banyak bagian dari berbagai ukuran. Pertanyaan spesifik yang ditanyakan adalah tentang partisi n menjadi bagian m, yang merupakan jenis partisi bilangan bulat yang terbatas.

Untuk menghasilkan partisi integer yang tidak terbatas, algoritma yang sangat cepat dan sederhana adalah karena Fristedt, dalam sebuah makalah yang disebut Struktur Partisi Acak Integer Besar (1993). Algoritenya adalah sebagai berikut:

  1. Setel x = exp (-pi / sqrt (6n)).
  2. Hasilkan variabel acak independen Z (1), Z (2), ..., Z (n), di mana Z (i) terdistribusi secara geometrik dengan parameter 1-x ^ i.
  3. JIKA jumlah i * Z (i) = n, di mana jumlah diambil alih semua i = 1,2, ..., n, lalu STOP.
    LAIN, ulangi 2.

Setelah algoritme berhenti, maka Z (1) adalah jumlah 1s, Z (2) adalah jumlah 2s, dll., dalam partisi yang dipilih secara seragam secara acak. Probabilitas menerima kumpulan Z yang dipilih secara acak adalah asimtotik 1 / (94n ^ 3) ^ (1/4), yang berarti orang akan berharap untuk menjalankan algoritma ini O (n ^ (3/4)) kali sebelum menerima satu mencicipi.

Alasan saya mengambil waktu untuk menjelaskan algoritma ini adalah karena ini berlaku langsung untuk masalah menghasilkan partisi n menjadi bagian m tepat. Pertama, amati itu

Jumlah partisi n ke dalam bagian m persis sama dengan jumlah partisi n dengan bagian terbesar sama dengan m.

Kemudian kita dapat menerapkan algoritma Fristedt secara langsung, tetapi bukannya menghasilkan Z (1), Z (2), ..., Z (n), kita dapat menghasilkan Z (1), Z (2), ..., Z ( m-1), Z (m) +1 (+1 di sini memastikan bahwa bagian terbesar adalah persis m, dan 1 + Z (m) sama dalam distribusi ke Z (m) bersyarat pada Z (m)> = 1 ) dan mengatur semua Z lainnya (m + 1), Z (m + 2), ... sama dengan 0. Kemudian setelah kami mendapatkan jumlah target dalam langkah 3 kami juga dijamin memiliki sampel yang tidak bias. Untuk mendapatkan partisi dari n ke bagian m tepatnya ambil konjugat dari partisi yang dihasilkan.

Keuntungan ini memiliki lebih dari metode rekursif Nijenhuis dan Wilf adalah bahwa tidak ada persyaratan memori selain untuk menyimpan variabel acak Z (1), Z (2), dll. Juga, nilai x dapat berupa apa saja antara 0 dan 1 dan algoritma ini masih bias! Memilih nilai yang baik dari x, bagaimanapun, dapat membuat algoritma lebih cepat, meskipun pilihan pada Langkah 1 hampir optimal untuk partisi integer yang tidak terbatas.

Jika n benar-benar besar dan algoritma Fristedt terlalu lama (dan metode tabel tidak sesuai), maka ada pilihan lain, tetapi mereka sedikit lebih rumit; lihat tesis saya https://sites.google.com/site/stephendesalvo/home/papers untuk info lebih lanjut tentang pembagian probabilistik dan penaklukan dan penerapannya.


11
2017-11-07 06:46



Hanya satu versi lagi di 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();
        }
    }
}

Kode ini akan menghasilkan output berikutnya:

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,

1
2018-06-26 03:45



Algoritma lain dari Algoritma Combinatorial halaman 52, "Generasi Acak dari n ke k bagian "

  1. Memilih  a1, a2, .., ak-1 acak k-1 bagian dari {1,2,..,n+k-1} (lihat di bawah 1., 2.)
  2. Set  r1  =  a1-1; rj  =  aj  -  aj-1-1 (j=2..k-1); rk  = n+k-1-  ak-1
  3. Itu rj (j=1..k) merupakan partisi acak dari n ke k bagian

Algoritma ini untuk komposisi acak didasarkan pada   model "bola-in-sel".

Secara singkat kita memilih posiitons sel   batasan secara acak, maka dengan membedakan kita mencari tahu berapa banyak bola   ada di setiap sel.

Untuk secara efisien menghasilkan subset acak dari satu set, lihat 1. jawaban terkait di sini dan 2. sini

memperbarui

Pendekatan lain menggunakan nomor acak tunggal di [0,1] untuk secara seragam menghasilkan partisi acak (juga disebut komposisi) diberikan dalam IVAN STOJMENOVIC, "ON RANDOM DAN ADAPTIF PARALLEL GENERASI DARI OBJEK KOMBINATORIAL" (bagian 5, bagian 10)

enter image description here


1
2017-08-27 02:30



Setelah beberapa googling saya menemukan algoritma untuk ini di "Handbook of Applied Algorithms," yang diindeks oleh Google Buku. Algoritma ini diberikan pada bagian 1.12.2, di halaman 31.


0
2018-01-29 17:19



Saya telah mengimplementasikan solusi di atas dan menemukan bahwa itu bekerja sangat baik jika seseorang ingin menghitung partisi integer untuk n tetapi tidak berkenaan dengan m. Jika bekerja dengan n besar, batas rekursif dan tumpukan panggilan mungkin perlu ditingkatkan banyak.

Namun, Anda tidak memerlukan fungsi pertama karena count_partitions (n, limit) akan benar-benar sama dengan jumlah partisi 'n + limit' dengan 'limit' jumlah bagian. Beberapa perangkat lunak matematika memiliki fungsi yang sangat cepat untuk menemukan jumlah partisi n menjadi bagian m.

Saya baru-baru ini memperoleh metode yang tidak bias, sangat sederhana, dan sangat cepat (menggunakan memoisasi) untuk memecahkan pertanyaan tepat Anda: Algoritma untuk secara acak menghasilkan partisi integer dengan panjang tertentu, dengan Python?

Ini didasarkan pada mengetahui sesuatu tentang leksikal memerintahkan partisi dari n memiliki bagian m dan menggunakan pendekatan yang mirip dengan algoritma yang diterima dengan baik (misalnya Nijenhuis dan Wilf 1978) yang menemukan partisi acak n, dan secara konseptual mirip dengan di atas.

Singkatnya, jika ada x partisi n dengan bagian m, maka kita memilih nomor acak antara 1 dan x. Nomor acak itu akan mengkodekan satu dan hanya satu partisi yang memenuhi n dan m. Saya harap ini membantu.


0
2018-04-25 07:04



Saya memiliki generator partisi yang didistribusikan secara merata.

Di mana n: = bilangan bulat yang akan dipartisi, r: = jumlah irisan: Algoritma ini adalah versi patch dari metode naif hanya memasukkan bagian secara acak. Masalah dengan metode ini, seperti yang tampak bagi saya ketika saya melihat outputnya, adalah bahwa skenario di mana bagian ditempatkan di tempat yang sama kurang mungkin terjadi. Hanya ada satu cara untuk mendapatkan {1,1,1}, sementara ada 3! cara mendapatkan {2,4,9}, salah satu dari {4,2,9}, {2,4,9}, {9,4,2} ... akan mengarah ke penempatan partisi yang sama ketika disortir. Ini telah diubah dengan memberikan tambahan peluang eksplisit untuk pengulangan. Untuk setiap penyisipan perpisahan, ada kemungkinan bahwa posisi perpisahan tidak akan acak, tetapi akan dipilih sebagai pengulangan dari nilai yang sebelumnya dipilih. Ini menyeimbangkan distribusi probabilitas yang tidak merata dari metode naif.

Saya telah membuktikan dengan kelelahan bahwa setiap partisi sama-sama memiliki kemungkinan yang sama untuk r = 3, n = 2. Saya cbf membuktikannya untuk nilai yang lebih tinggi tetapi usaha sepenuh hati untuk melakukannya hanya menemukan tanda-tanda yang menjanjikan. Saya juga mengujinya pada input acak, menemukan bahwa itu setidaknya kira-kira bahkan untuk setiap nilai yang saya coba [tapi mungkin bahkan sempurna].

di sini adalah di C + + 11: [format output berbeda dengan apa yang Anda harapkan, itu adalah posisi dari bagian daripada ukuran ruang di antara mereka. Konversi itu mudah, meskipun]

#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;
}

Saya tidak suka fakta bahwa saya harus mengatasinya. Jika versi Vlody memiliki distribusi yang merata, tampaknya akan lebih baik.


0
2018-05-26 00:33