Генерация последовательности чисел фиксированной длины, ограниченных k, которые складываются в n - PullRequest
0 голосов
/ 06 июля 2018

Учитывая положительные целые числа l, k и n, я заинтересован в написании функции f(l, k, n), которая возвращает случайно сгенерированную последовательность длины l целых чисел в -k, -k + 1, ..., -1, 0, 1, ..., k - 1, k, которые складываются в n.

Есть идеи, как этого достичь?

РЕДАКТИРОВАТЬ: повторение разрешено. В идеале распределение вероятностей должно быть равномерным на множестве решений, но меня это не очень беспокоит: меня больше интересует получение уникальных решений при каждом вызове функции.

1 Ответ

0 голосов
/ 06 июля 2018

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

Как я и подразумевал в своем комментарии, возможно, что нет никакой желаемой последовательности. Например, невозможно получить последовательность 3 чисел из -2, -1, 0, 1, 2, чтобы сложить до 7. Вы должны проверить это в первую очередь. Даже если есть возможные последовательности, могут быть ограничения на первый номер в последовательности. Если вы хотите, чтобы последовательность 3 чисел от -2, -1, 0, 1, 2 складывалась до 5, первое число не может быть -2. Минимум для вашего первого номера равен 1, а максимум - 2.

Итак, вот алгоритм, после вашей начальной проверки, что любая последовательность возможна. Найдите минимальные и максимальные возможные значения для первого числа в последовательности. Выберите случайное число между этими двумя значениями - используйте randint или randrange из модуля random. Затем вычтите это число из вашего значения n и вычтите 1 из k (количество чисел, все еще необходимое в вашей последовательности). Повторяйте это до тех пор, пока последовательность не будет завершена (число нужных чисел равно нулю).

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

...