Как создать равномерное случайное целочисленное разбиение?

Question

Поиск Google показывает много о генерации всех возможных разбиений целого числа n на m частей, но я не нашел ничего о выборке равномерно распределенного случайного разбиения n на m частей.

Answer 1

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

Для генерации неограниченных целочисленных разбиений очень быстрый и простой алгоритм принадлежит Фристедту в статье под названием Структура случайных разбиений большого целого числа (1993) . Алгоритм выглядит следующим образом:

1. Установите x = exp (-pi / sqrt (6n)).
2. Генерация независимых случайных величин Z (1), Z (2), ..., Z (n), где Z (i) геометрически распределен с параметром 1-x ^ i.
3. ЕСЛИ сумма i * Z (i) = n, где сумма берется по всем i = 1,2, ..., n, затем STOP.
   В противном случае, повторите 2.

Как только алгоритм останавливается, тогда Z (1) - это число , равное 1 с , Z (2) - это число , равное 2 с и т. Д., В разделе, выбранном равномерно при случайным образом. Вероятность принятия случайно выбранного набора Z равна асимптотически 1 / (94n ^ 3) ^ (1/4), что означает, что можно было бы запустить этот алгоритм O (n ^ (3/4)), прежде чем принять один образец.

Причина, по которой я потратил время на объяснение этого алгоритма, заключается в том, что он напрямую относится к задаче генерации разбиения n на ровно m частей. Во-первых, обратите внимание, что

Количество разбиений n на ровно m частей равно числу разбиений n с наибольшей частью, равной m.

Тогда мы можем напрямую применить алгоритм Фристедта, но вместо генерации Z (1), Z (2), ..., Z (n) мы можем генерировать Z (1), Z (2), ... , Z (m-1), Z (m) +1 (здесь +1 гарантирует, что наибольшая часть в точности равна m, а 1 + Z (m) по распределению равно Z (m), условному для Z (m) > = 1) и установите все остальные Z (m + 1), Z (m + 2), ... равными 0. Затем, как только мы получим целевую сумму на шаге 3, мы также гарантируем несмещенную выборку. Чтобы получить разбиение n на ровно m частей, просто возьмите сопряженное сгенерированное разбиение.

Преимущество этого рекурсивного метода Нидженхуйса и Уилфа в том, что нет никаких требований к памяти, кроме хранения случайных величин Z (1), Z (2) и т. Д. Кроме того, значение х может быть любым между 0 и 1, и этот алгоритм все еще беспристрастен! Однако выбор правильного значения x может сделать алгоритм намного быстрее, хотя выбор на шаге 1 почти оптимален для неограниченных целочисленных разбиений.

Если n действительно велико, а алгоритм Фристедта занимает слишком много времени (и о табличных методах не может быть и речи), то есть другие варианты, но они немного сложнее; см. мой тезис https://sites.google.com/site/stephendesalvo/home/papers для получения дополнительной информации о вероятностных принципах «разделяй и властвуй» и их приложениях.

Answer 2

Вот код, который это делает. Это O ( n ² ) при первом вызове, но он создает кэш, так что последующие вызовы 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

Как это работает: Мы можем вычислить, сколько разделов целого числа n существует в O ( n ² ) времени , В качестве побочного эффекта это приводит к таблице размера O ( n ² ), которую мы можем затем использовать для создания k -го раздела n. , для любого целого числа k , в O ( n ) времени.

Итак, пусть total = количество разделов. Выберите случайное число k от 0 до всего - 1. Сгенерируйте k th раздел.

Answer 3

Другой алгоритм из Комбинаторные алгоритмы стр. 52, "Случайная генерация n в k части"

1. Выберите a1, a2, .., ak-1 случайное k-1 подмножество {1,2,..,n+k-1} (см. ниже 1., 2.)
2. Набор r1 = a1-1; rj = aj - aj-1-1 (j=2..k-1) ; rk = n+k-1- ak-1
3. rj (j=1..k) составляют случайное разбиение n на k части

Этот алгоритм для случайных композиций основан на модель "шары в клетках".

Вкратце выбираем положение клетки границы наугад, то по разности мы узнаем, сколько шаров в каждой клетке.

Для эффективной генерации случайного подмножества набора см. Ответы, связанные с 1. здесь и 2. здесь

обновление

Другой подход, использующий одно случайное число в [0,1] для равномерной генерации случайного разбиения (также называемый композицией), дан в ИВАН СТОЙМЕНОВИЧ, «О СЛУЧАЙНОМ И АДАПТИВНОМ ПАРАЛЛЕЛЬНОМ ГЕНЕРАЦИИ КОМБИНАТОРНЫХ ОБЪЕКТОВ» (раздел 5, раздел 10)

Answer 4

У меня равномерно распределенный генератор разделов.

Где n: = целое число, которое будет разделено, r: = количество срезов: Алгоритм является исправленной версией наивного метода простой вставки разделений наугад. Проблема с этим методом, как мне показалось, когда я посмотрел на его результаты, заключалась в том, что сценарии, в которых расставления расположены в одном месте, менее вероятны. Есть только один способ получить {1,1,1}, а есть 3! способы получения {2,4,9}, любого из {4,2,9}, {2,4,9}, {9,4,2} ... приведут к одинаковому размещению разделов при сортировке. Это было исправлено путем предоставления дополнительных явных возможностей для повторов. Для каждой вставки разделения существует вероятность того, что положение разделения не будет случайным, но будет выбрано как повторение ранее выбранного значения. Это уравновешивает неравномерное распределение вероятностей наивного метода.

Я исчерпывающе доказал, что каждое разделение совершенно одинаково вероятно при r = 3, n = 2. Я доказал это для более высоких значений, но отважные на это попытки нашли только многообещающие признаки. Я также проверил его на случайном вводе, обнаружив, что он, по крайней мере, приблизительно даже для каждого значения, которое я пробовал [но, вероятно, идеально даже].

здесь это в C ++ 11: [формат вывода отличается от того, что вы ожидаете, это позиции разделений, а не размер пространства между ними. Преобразование, однако, легко]

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

Мне не нравится тот факт, что я должен сортировать это все же. Если версия Vlody имеет четный дистрибутив, похоже, что она будет лучше.

Answer 5

Просто еще одна версия в 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();
        }
    }
}

Этот код выдаст следующий вывод:

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 6

Я реализовал вышеупомянутое решение и обнаружил, что оно работает очень хорошо, если нужно вычислить целочисленные разбиения для n, но не относительно m. При работе с большим n, возможно, потребуется значительно увеличить пределы рекурсии и стеки вызовов.

Однако вам не нужна первая функция, потому что count_partitions (n, limit) фактически будет равняться количеству разделов 'n + limit' с количеством 'limit' частей. Некоторые математические программы имеют очень быстрые функции для определения количества разбиений n на m частей.

Недавно я нашел совершенно непредвзятый, очень простой и очень быстрый метод (с использованием напоминаний) для решения вашего точного вопроса : Алгоритм для случайного генерирования целочисленных разбиений определенной длины, в Python?

Он основан на знании кое-чего о лексически упорядоченных разбиениях n, имеющих m частей, и использует аналогичный подход к хорошо принятым алгоритмам (например, Nijenhuis и Wilf 1978), которые находят случайные разбиения n, и концептуально аналогичен вышеописанному.

Короче говоря, если есть x разделов n с m частями, то мы выбираем случайное число от 1 до x. Это случайное число будет кодировать один и только один раздел, удовлетворяющий n и m. Надеюсь, это поможет.

Answer 7

После некоторого поиска в Google я нашел алгоритм для этого в «Справочнике по прикладным алгоритмам» , который Google Books проиндексировал . Алгоритм приведен в разделе 1.12.2 на стр. 31.