Создать список случайных чисел с условием - numpy - PullRequest
Новая
       32

Создать список случайных чисел с условием - numpy

4 голосов
/ 22 сентября 2019

Я хотел бы создать список из 15 целых чисел с суммой 12, минимальное значение равно 0, а максимальное - 6.

Я пробовал следующий код 

def generate(low,high,total,entity):
   while sum(entity)!=total:
       entity=np.random.randint(low, high, size=15)
   return entity

Но выше функция неработает правильно.Это слишком много времени.Пожалуйста, дайте мне знать эффективный способ генерации таких чисел?

Ответы [ 3 ]

4 голосов
/ 22 сентября 2019

Выше, строго говоря, будет работать.Но для 15 чисел от 0 до 6 вероятность генерации 12 не так велика.Фактически мы можем рассчитать количество возможностей с помощью:

F (s, 1) = 1 для 0≤s≤6 и

F (s, n) = Σ 6 i = 0 F (si, n-1) .

Мы можем рассчитать это с помощьюзначение: 

from functools import lru_cache

@lru_cache()
def f(s, n, mn, mx):
    if n < 1:
        return 0
    if n == 1:
        return int(mn <= s <= mx)
    else:
        if s < mn:
            return 0
        return sum(f(s-i, n-1, mn, mx) for i in range(mn, mx+1))

Это означает, что существует 9'483'280 возможностей из 4'747'561'509'943 общих возможностей для генерации суммы 12, или 0,00019975%.Таким образом, потребуется около 500 624 итераций, чтобы найти такое решение.

Поэтому мы должны лучше стремиться найти прямой способ генерации такой последовательности.Мы можем делать это каждый раз, вычисляя вероятность генерации числа: вероятность генерации i в качестве числа в качестве первого числа в последовательности n чисел, которые суммируют до s - F (si, n-1, 0, 6) / F (s, n, 0, 6) .Это будет гарантировать, что мы сгенерируем единый список по списку возможностей. Если мы будем каждый раз рисовать одинаковое число, то оно не будет соответствовать равномерному распределению по всему списку значений, соответствующих данному условию:

Мы можем сделать это рекурсивно с помощью: 

from numpy import choice

def sumseq(n, s, mn, mx):
    if n > 1:
        den = f(s, n, mn, mx)
        val, = choice(
            range(mn, mx+1),
            1,
            p=[f(s-i, n-1, mn, mx)/den for i in range(mn, mx+1)]
        )
        yield val
        yield from sumseq(n-1, s-val, mn, mx)
    elif n > 0:
        yield s

С помощью вышеуказанной функции мы можем сгенерировать массивы numpy: 

>>> np.array(list(sumseq(15, 12, 0, 6)))
array([0, 0, 0, 0, 0, 4, 0, 3, 0, 1, 0, 0, 1, 2, 1])
>>> np.array(list(sumseq(15, 12, 0, 6)))
array([0, 0, 1, 0, 0, 1, 4, 1, 0, 0, 2, 1, 0, 0, 2])
>>> np.array(list(sumseq(15, 12, 0, 6)))
array([0, 1, 0, 0, 2, 0, 3, 1, 3, 0, 1, 0, 0, 0, 1])
>>> np.array(list(sumseq(15, 12, 0, 6)))
array([5, 1, 0, 0, 0, 0, 1, 1, 0, 0, 1, 1, 1, 0, 1])
>>> np.array(list(sumseq(15, 12, 0, 6)))
array([0, 0, 0, 0, 4, 2, 3, 0, 0, 0, 0, 0, 3, 0, 0])
2 голосов
/ 23 сентября 2019

Ну, есть простое и естественное решение - использовать распределение, которое по определению предоставляет вам массив значений с фиксированной суммой.Самый простой из них - Многокомпонентное распределение .Единственный код, который нужно добавить, - это проверить и отклонить (и повторить выборку), если какое-либо значение выборки превышает максимум.

Вдоль линий 

import numpy as np

def sample_sum_interval(n, p, maxv):
    while True:
        q = np.random.multinomial(n, p)
        v = np.where(q > maxv)
        if len(v[0]) == 0: # if len(v) > 0, some values are outside the range, reject
            return q
    return None

np.random.seed(32345)

k    = 15
n    = 12
maxv = 6
p = np.full((k), np.float64(1.0)/np.float64(k), dtype=np.float64) # probabilities

q = sample_sum_interval(n, p, maxv)
print(q)
print(np.sum(q))

q = sample_sum_interval(n, p, maxv)
print(q)
print(np.sum(q))

q = sample_sum_interval(n, p, maxv)
print(q)
print(np.sum(q))

ОБНОВЛЕНИЕ

Я быстроЯ посмотрел на предложенный @WillemVanOnsem метод, и я считаю, что он отличается от многочлена, используемого мной.

Если мы посмотрим на многочлен PMF и предположим равные вероятности для всех k чисел, p 1 = ... = p k = 1 / k, тогда мы можем записать PMF как

PMF (x 1 , ... x k) = n! / (X 1 ! ... x k !) P 1 x 1 ... p k x k = n! / (X 1 ! ... x k!) K -x 1 ... k -x k = n! / (X 1! ... x k !) K -Сумма i x i = n! / (X 1 ! ... x k !) K -n

Очевидно, вероятности конкретного x 1 ... x k комбинации будут отличаться друг от другадругие из-за факториала в знаменателе (конечно, по модулю перестановок), который отличается от подхода @WillemVanOnsem, где все они будут иметь равные вероятности появления, я полагаю.

Мораль истории - эти методы производят разныераспределения.

2 голосов
/ 22 сентября 2019

Вы можете попробовать реализовать его немного по-другому.

import random
def generate(low,high,goal_sum,size=15):
    output = []
    for i in range(size):
        new_int = random.randint(low,high)
        if sum(output) + new_int <= goal_sum:
            output.append(new_int)
        else:
            output.append(0)
    random.shuffle(output)
    return output

Кроме того, если вы используете np.random.randint, ваш максимум будет на самом деле высоким-1

...