Как я генерирую универсальный случайный целочисленный раздел?
Поиск Google показывает много о генерации всех возможных разделов целого числа n в m части, но я ничего не нашел о выборке равномерно распределенного случайного раздела n в m части.
3 ответа
Вот код, который это делает. Это O(n2) при первом вызове, но он строит кэш так, чтобы последующие вызовы были 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(n2). В качестве побочного эффекта получается таблица размера O(n2), которую мы можем использовать для создания kth раздела n, для любого целого k, во времени O(n).
Пусть насчитывает = количество разделов. Выберите случайное число k от 0 до итого - 1. Сгенерируйте k раздел.
После некоторого поиска в Google я нашел алгоритм для этого в «Руководстве по прикладным алгоритмам» , который Google Книги проиндексировал . Алгоритм приведен в разделе 1.12.2 на странице 31.
Еще одна версия на 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,