Произвольно сгенерировать набор чисел из n общей длиной x

Question

Я работаю над проектом для удовольствия, и мне нужен алгоритм, чтобы сделать следующее: Создайте список чисел длины n, которые в сумме составляют x

Я бы согласился на список целых чисел, но в идеале я бы хотел оставить набор чисел с плавающей точкой.

Я был бы очень удивлен, если бы эта проблема не была тщательно изучена, но я не уверен, что искать.

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

Кто-нибудь знает, как это можно назвать или как к нему подойти? Спасибо всем!

Редактировать: Чтобы уточнить, я имею в виду, что список должен быть длиной N, а сами числа могут быть любого размера.

edit2: Извините за неправильное использование 'set', я использовал его как термин для определения списка или массива. Я понимаю, что это вызывало замешательство, мои извинения.

Answer 1

Вот как это сделать в Python

import random

def random_values_with_prescribed_sum(n, total):
    x = [random.random() for i in range(n)]
    k = total / sum(x)
    return [v * k for v in x]

В основном вы выбираете n случайных чисел, вычисляете их сумму и вычисляете масштабный коэффициент так, чтобы сумма была такой, какой вы хотите.

Обратите внимание, что при таком подходе не будут получаться "однородные" срезы, т. Е. Распределение, которое вы получите, будет иметь тенденцию быть более "равноправным", чем должно быть, если бы оно было выбрано случайным образом среди всего распределения с данной суммой.

Чтобы увидеть причину, вы можете просто представить, что делает алгоритм в случае двух чисел с заданной суммой (например, 1):

Точка P является общей точкой, полученной путем выбора двух случайных чисел, и она будет равномерной внутри квадрата [0,1]x[0,1]. Точка Q - это точка, полученная путем масштабирования P, так что сумма должна быть равна 1. Как видно из рисунка, точки, расположенные близко к центру, имеют более высокую вероятность; например, точный центр квадратов будет найден путем проецирования любой точки по диагонали (0,0)-(1,1), в то время как точка (0, 1) будет найдена, проецируя только точки из (0,0)-(0,1) ... длина диагонали равна sqrt(2)=1.4142..., в то время как квадратная сторона только 1.0.

Answer 2

Если вы хотите произвести равномерную выборку в области N-1 -мерного пространства, определяемого x1 + x2 + ... + xN = x, то вы смотрите на особый случай выборки из распределения Дирихле . Процедура выборки немного сложнее, чем генерация равномерных отклонений для xi. Вот один из способов сделать это в Python:

xs = [random.gammavariate(1,1) for a in range(N)]
xs = [x*v/sum(xs) for v in xs]

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

Answer 3

На самом деле вам нужно создать раздел x на n частей.Обычно это делается следующим образом: Разделение x на n неотрицательных частей может быть представлено следующим образом: резерв n + x свободные места, поместите n границы для некоторых произвольных мест и камни для остальных.Группы камней в сумме составляют x , поэтому число возможных разбиений равно биномиальному коэффициенту ( n + x \ atop n ).

Таким образом, ваш алгоритм может быть следующим: выбрать произвольное n -подмножество ( n + x ), он однозначно определяет разбиение x на n частей.

В TAOCP Кнута в главе 3.4.2 обсуждается случайная выборка.См. Алгоритм S там.

---

Алгоритм S: (выберите n произвольных записей из общего числа N)

1. t = 0, m = 0;
2. u = случайный, равномерно распределенный по (0, 1)
3. , если (N - t) * u> = n - m, пропустить t-ю запись и увеличить t на 1;в противном случае включите t-ю запись в выборку, увеличьте m и t на 1
4. , если M

---

Решение длянецелые числа алгоритмически тривиальны: вы просто выбираете произвольные n чисел, которые не суммируют до 0, и нормируете их по сумме.

Answer 4

Вот версия вышеупомянутого алгоритма в Javascript

    function getRandomArbitrary(min, max) {
        return Math.random() * (max - min) + min;
    };
    function getRandomArray(min, max, n) {
        var arr = [];
        for (var i = 0, l = n; i < l; i++) {
            arr.push(getRandomArbitrary(min, max))
        };
        return arr;
    };
    function randomValuesPrescribedSum(min, max, n, total) {
        var arr = getRandomArray(min, max, n);
        var sum = arr.reduce(function(pv, cv) { return pv + cv; }, 0);
        var k = total/sum;
        var delays = arr.map(function(x) { return k*x; })
        return delays;
    };

Вы можете вызвать его с помощью

var myarray = randomValuesPrescribedSum(0,1,3,3);

И затем проверить его с помощью

var sum = myarray.reduce(function(pv, cv) { return pv + cv;},0);

Answer 5

В питоне:

a: создать список из (случайных # от 0 до 1) раз; добавить 0 и всего к списку

b: сортировка списка, измерение расстояния между каждым элементом

c: округлить элементы списка

import random
import time

TOTAL       = 15
PARTS       = 4
PLACES      = 3

def random_sum_split(parts, total, places):

    a = [0, total] + [random.random()*total for i in range(parts-1)]
    a.sort()
    b = [(a[i] - a[i-1]) for i in range(1, (parts+1))]
    if places == None:
        return b
    else:    
        b.pop()
        c = [round(x, places) for x in b]  
        c.append(round(total-sum(c), places))
        return c

def tick():

    if info.tick == 1:

        start = time.time()
        alpha = random_sum_split(PARTS, TOTAL, PLACES)
        end = time.time()  

        log('alpha: %s' % alpha)
        log('total: %.7f' % sum(alpha))
        log('parts: %s' % PARTS)
        log('places: %s' % PLACES)
        log('elapsed: %.7f' % (end-start))

выходы:

[2014-06-13 01:00:00] alpha: [0.154, 3.617, 6.075, 5.154]
[2014-06-13 01:00:00] total: 15.0000000
[2014-06-13 01:00:00] parts: 4
[2014-06-13 01:00:00] places: 3
[2014-06-13 01:00:00] elapsed: 0.0005839

Насколько мне известно, это распределение равномерно

Answer 6

Этот код делает разумную работу. Я думаю, что это производит распределение, отличное от ответа 6502, но я не уверен, что лучше или более естественно. Конечно, его код яснее / приятнее.

import random

def parts(total_sum, num_parts):
  points = [random.random() for i in range(num_parts-1)]
  points.append(0)
  points.append(1)
  points.sort()

  ret = []
  for i in range(1, len(points)):
    ret.append((points[i] - points[i-1]) * total_sum)
  return ret

def test(total_sum, num_parts):
  ans = parts(total_sum, num_parts)
  assert abs(sum(ans) - total_sum) < 1e-7
  print ans

test(5.5, 3)
test(10, 1)
test(10, 5)