генерации случайных элементов списка с правилами

Question

Пусть список л состоит из п элементов, где

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

Пример:

Given n = 5, r = 4, m = 10 

l = [4, 3, 2, 0, 1] 

Легко выполнить правило (1), но мне интересно, есть ли какая-либо хорошая идея/алгоритм для выполнения обоих правил?

Answer 1

Разумная интерпретация будет заключаться в том, чтобы (i) находить и подсчитывать все уникальные списки, удовлетворяющие правилам; и (ii) выбрать один из этих списков случайным образом с равной вероятностью. Проблема с этим методом заключается в том, что сложно скопировать список списков.

Простой способ сделать это (меньше кода) состоит в том, чтобы выставить каждый правильный список с той же вероятностью, что и выбрано. Этот алгоритм является:

1. проверить, что m<=nr Если нет, возвращать None или вызвать ошибку.
2. Петля: многократно генерирует списки со случайными числами в [0, r]. Перерыв петля и возвращение первый список сумм м.

Примечание: компромисс здесь за меньший код является потенциально более длительным временем выполнения. если r велико, или m - невероятная сумма, это может занять некоторое время. Мы можем немного смягчить это, проверив пределы, где ответ может быть только нулями или r-1.

from numpy.random import randint 

def known_sum_random_list(size,limitint,knownsum): 
    if knownsum>size*(limitint-1): 
     return None 
    if knownsum==size*(limitint-1): 
     return size*[limitint-1] 
    s=0 
    l = size*[0] 
    while (s!=knownsum): 
     l = randint(0,limitint,size) 
     s = sum(l) 
    return l 

for t in xrange(10): 
    print known_sum_random_list(5,4,10) 

выход:

[3 2 1 2 2] 
[1 1 2 3 3] 
[3 0 3 1 3] 
[3 2 0 3 2] 
[2 2 0 3 3] 
[1 3 2 3 1] 
[3 3 0 3 1] 
[2 0 2 3 3] 
[3 1 2 3 1] 
[3 2 0 3 2] 

Answer 2

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

import numpy as np 

def rand_with_rules(n, r, m): 
    if n*(r-1) < m: 
     raise ValueError 
    while True: 
     l = np.random.randint(0, r, size=(n)) 
     if l.sum() == m: 
      return l 

Обратите внимание, что отклонение образцов обязательно приведет к смещению ваших «случайных» чисел. Из-за ваших ограничений вы не можете иметь чисто набор случайных и определенных, как правило, более или недопредставленных.

Возьмем, к примеру, случай n, r, m = 2, 3, 4. Единственная серия, которая соответствует этим критериям, равна (2, 2), поэтому вероятность рисования 2 равна 100% и 0% для другие значения.

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

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

Answer 3

без проверки, что все правила могут быть встретиться сразу, я предлагаю следующее решение

import random 

def dis(n,m,r): 
    l = [0] * n 

    for inc in range(1,m): 
    l.sort() 
    for ind_less_r, less_r in enumerate(l): 
     if less_r > r: 
      break 
    l[random.randint(0,ind_less_r-1)] += 1 

    random.shuffle(l) 
    return l 


for i in range(1,10): 
    print dis(10,50,9) 

результат

[7, 7, 6, 1, 6, 3, 5, 4, 4, 6] 
[5, 6, 7, 5, 4, 7, 4, 4, 4, 3] 
[4, 3, 2, 4, 7, 7, 5, 7, 5, 5] 
[4, 4, 5, 6, 4, 6, 6, 4, 5, 5] 
[6, 6, 4, 6, 5, 6, 2, 5, 4, 5] 
[2, 8, 4, 2, 6, 5, 4, 4, 6, 8] 
[6, 6, 3, 4, 5, 5, 5, 5, 6, 4] 
[6, 4, 5, 6, 7, 3, 1, 5, 6, 6] 
[4, 5, 4, 7, 6, 6, 3, 2, 6, 6] 

Answer 4

Поскольку вы ответили в комментариях, что он может иметь много 0s и числа могут повторяться , Я полагаю, что это не должно быть все это случайным. Имея это в виду, вот базовое решение без каких-либо циклов или включений. Он предполагает, что n, r и m имеют действительные значения и типы. Но такие проверки достаточно просты, чтобы добавить, я отредактирую их по запросу.

def create_list(n, r, m): 
    output = [r] * (m/r) 
    remainder = m - r * len(output) 
    if remainder != 0: 
     output += [m - r * len(output)] 
    output += [0] * (n - len(output)) 
    return output 

output = create_list(5, 4, 10) # gives [4, 4, 2, 0, 0] 
output = create_list(5, 2, 10) # gives [2, 2, 2, 2, 2] 

P.S. - запрос был для значений менее r, но пример показал значение, равное r, так что это происходит на примере