Поиск в Google показывает много общего с созданием всех возможных разделов целого числа n на m частей, но я ничего не нашел о выборке равномерно распределенного случайного разбиения n на m частей.
Как создать единый случайный целочисленный раздел?
Ответ 1
Вот какой код это делает. Это O (n 2) при первом вызове, но он создает кеш, чтобы последующие вызовы были 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 2) времени. В качестве побочного эффекта получается таблица размера O (n 2), которую мы можем затем использовать для генерации k -го разбиения n для любого целого k в O (n).
Итак, пусть total = количество разделов. Выберите случайное число k от 0 до total - 1. Создайте k th раздел.
Ответ 2
Название этого сообщения немного вводит в заблуждение. Случайный целочисленный раздел по умолчанию неограниченный, то есть он может иметь столько частей любого размера. Заданный вопрос касается разбиения n на m частей, что является типом ограниченного целочисленного раздела.
Для создания неограниченных целых разделов очень быстрый и простой алгоритм принадлежит Фрестеду в статье под названием Структура случайных разделов большого целого (1993). Алгоритм выглядит следующим образом:
- Установите x = exp (-pi/sqrt (6n)).
- Генерировать независимые случайные величины Z (1), Z (2),..., Z (n), где Z (i) геометрически распределено с параметром 1-x ^ i.
- IF sum я * Z (i) = n, где сумма берется по всем я = 1,2,..., n, тогда STOP.
ELSE, повторите 2.
Как только алгоритм останавливается, тогда Z (1) является числом 1s, Z (2) является числом 2s и т.д. в выбранном разделе равномерно случайным образом. Вероятность принятия случайно выбранного множества 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 частей, просто возьмите сопряженное сгенерированное разбиение.
Преимущество этого метода над рекурсивным методом Nijenhuis и Wilf заключается в том, что нет никаких требований к памяти, кроме как хранить случайные величины Z (1), Z (2) и т.д. Кроме того, значение x может быть любым между 0 и 1, и этот алгоритм все еще несмещен! Однако выбор хорошего значения x может сделать алгоритм намного быстрее, хотя выбор на шаге 1 почти оптимален для неограниченных целых разделов.
Если n действительно велико, а алгоритм Fristedt занимает слишком много времени (и методы таблицы не могут быть и речи), тогда есть другие варианты, но они немного сложнее; см. мой тезис https://sites.google.com/site/stephendesalvo/home/papers для получения дополнительной информации о вероятностном разрыве и победе и его приложениях.
Ответ 3
Только одна версия в С#.
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,
Ответ 4
После некоторого поиска в Google я нашел алгоритм для этого в "Руководстве по прикладным алгоритмам", который Google Books индексировал. Алгоритм приведен в разделе 1.12.2 на стр. 31.
Ответ 5
Я реализовал вышеупомянутое решение и обнаружил, что он работает очень хорошо, если вы хотите вычислить целочисленные разделы для n, но не по m. Если вы работаете с большим n, возможно, потребуется значительно увеличить пределы рекурсии и стеки вызовов.
Тем не менее, вам не нужна первая функция, потому что count_partitions (n, limit) фактически будет равным числу разделов 'n + limit' с числом ограничений 'limit'. Некоторые математические программы имеют очень быстрые функции для нахождения числа разбиений n на m частей.
Недавно я получил определенно беспристрастный, очень простой и очень быстрый метод (используя memoization), чтобы решить ваш точный вопрос: Алгоритм произвольного генерирования целые разделы определенной длины в Python?
Это основано на знании чего-то о лексически упорядоченных разделах n, имеющих m частей, и использует аналогичный подход к хорошо принятым алгоритмам (например, Nijenhuis and Wilf 1978), которые находят случайные разбиения n и концептуально аналогичны приведенным выше.
Короче говоря, если есть x разделов n с m частями, то мы выбираем случайное число между 1 и x. Это случайное число будет кодировать один и только один раздел, удовлетворяющий n и m. Надеюсь, это поможет.
Ответ 6
У меня есть равномерно распределенный генератор разделов.
Где n: = целочисленное целое, r: = количество срезов: Алгоритм - это исправленная версия наивного метода простого вставки фрагментов в случайном порядке. Проблема с этим методом, как мне показалось, когда я посмотрел на его вывод, заключалась в том, что сценарии, в которых расставания размещены в одном и том же месте, с меньшей вероятностью происходят. Существует только один способ получить {1,1,1}, а есть 3! способы получения {2,4,9}, любой из {4,2,9}, {2,4,9}, {9,4,2}... приведет к тому же размещению разделов при сортировке. Это было изменено путем предоставления дополнительных явных возможностей для повторов. Для каждой вставки прорезья существует вероятность того, что положение разлуки не будет случайным, но будет выбрано как повторение ранее выбранного значения. Это уравновешивает неравномерное распределение вероятностей наивного метода.
Я исчерпал себя тем, что каждое разбиение совершенно одинаково вероятно для r = 3, n = 2. я cbf, доказывая это для более высоких значений, но при этом отвратительные предприятия, чтобы сделать это, нашли только многообещающие знаки. Я также тестировал его на случайном входе, обнаружив, что он, по крайней мере, примерно равен даже для всех значений, которые я пытался (но, вероятно, даже совершенно).
здесь он находится в С++ 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 имеет равномерное распределение, кажется, что было бы лучше.
Ответ 7
Другой алгоритм из Комбинаторные алгоритмы, стр. 52, "Случайное поколение n в k части"
- Выберите
a1,a2,..,ak-1случайное подмножествоk-1в{1,2,..,n+k-1}(см. ниже 1., 2.) - Установить
r1=a1-1;rj=aj-aj-1-1(j=2..k-1);rk= n+k-1-ak-1 -
rj(j=1..k) составляют <сильное > случайное разбиениеnнаkчасти
Этот алгоритм для случайных композиций основан на модель "шарики в клетках".
Вкратце выберем поситоны клетки границы случайным образом, то по разности мы узнаем, сколько шаров находятся в каждой ячейке.
Для эффективной генерации случайного подмножества набора см. ответ на здесь и 2. здесь
Обновление
Другой подход, использующий одно случайное число в [0,1] для равномерного генерации случайного разбиения (также называемого композицией), приведен в IVAN STOJMENOVIC, "ON RANDOM И АДАПТИВНОЕ ПАРАЛЛЕЛЬНОЕ ПОКОЛЕНИЕ КОМБИНАТОРНЫХ ОБЪЕКТОВ" (раздел 5, раздел 10)
