О серии
Во-первых, вы можете относиться к этому, как к любому другому вызову для игры в гольф, и отвечать на него, не беспокоясь о серии вообще. Тем не менее, существует таблица лидеров по всем задачам. Вы можете найти таблицу лидеров вместе с дополнительной информацией о серии в первом посте .
Несмотря на то, что у меня есть ряд идей для этой серии, будущие проблемы еще не заложены. Если у вас есть какие-либо предложения, пожалуйста, сообщите мне об этом в соответствующей песочнице .
Отверстие 3: целочисленные разделы
Время немного увеличить сложность.
Разбиение положительного целого числа n
, определяется как мультимножестве положительных целых чисел, сумма которых равна n
. Например, если n = 5
существуют следующие разделы:
{1,1,1,1,1}
{2,1,1,1}
{2,2,1}
{3,1,1}
{3,2}
{4,1}
{5}
Обратите внимание , что это мультимножествами, так что нет никакого порядка им {3,1,1}
, {1,3,1}
и {1,1,3}
все они считаются идентичными.
Ваша задача состоит в том, n
чтобы создать случайный раздел n
. Вот подробные правила:
Распределение произведенных перегородок должно быть равномерным . То есть в приведенном выше примере каждый раздел должен быть возвращен с вероятностью 1/7.
Конечно, из-за технических ограничений PRNG идеальная однородность будет невозможна. Для оценки единообразия вашего представления следующие операции будут рассматриваться как обеспечивающие абсолютно равномерное распределение:
- Получение номера из PRNG (в любом диапазоне), который задокументирован, чтобы быть (приблизительно) равномерным.
- Отображение равномерного распределения по большому набору чисел в меньший набор по модулю или умножению (или какой-либо другой операции, которая распределяет значения равномерно). Большой набор должен содержать как минимум в 1024 раза больше возможных значений, чем меньший набор.
Поскольку разделы являются мультимножествами, вы можете возвращать их в любом порядке, и этот порядок не обязательно должен быть согласованным. Однако в целях случайного распределения порядок игнорируется. То есть, в приведенном выше примере,
{3,1,1}
,{1,3,1}
и{1,1,3}
вместе должны иметь вероятность 1/7 возвращается.- Ваш алгоритм должен иметь детерминированную среду выполнения. В частности, вы не можете генерировать случайные мультимножества и отклонять их, если они не суммируются
n
. - Временная сложность вашего алгоритма должна быть полиномиальной
n
. В частности, вы не можете просто сгенерировать все разделы и выбрать случайный (так как количество разделов растет в геометрической прогрессииn
). Вы можете предположить, что используемый PRNG может возвращать равномерно распределенные значения в O (1) на значение. - Вы не должны использовать какую-либо встроенную функцию, которая решает эту задачу.
Вы можете написать полную программу или функцию и получить ввод через STDIN или ближайшую альтернативу, аргумент командной строки или аргумент функции и произвести вывод через возвращаемое значение или распечатать в STDOUT (или ближайшую альтернативу).
Вы можете предположить, что n ≤ 65
(например, количество разделов меньше, чем 21 ). Вывод может быть в любом удобном, однозначном списке или строковом формате.
Если вы отправляете функцию, рассмотрите также небольшую тестовую программу, которая вызывает функцию несколько раз и печатает результаты. Ничего страшного, если параметры нужно настроить в коде. Это просто для того, чтобы люди могли проверить, что решение, по крайней мере, приблизительно одинаково.
Это код гольф, поэтому выигрывает самое короткое представление (в байтах). И, конечно же, самая короткая заявка на пользователя также войдет в общую таблицу лидеров серии.
Leaderboard
Первый пост серии генерирует таблицу лидеров.
Чтобы убедиться, что ваши ответы отображаются, начните каждый ответ с заголовка, используя следующий шаблон уценки:
# Language Name, N bytes
где N
размер вашего представления. Если вы улучшите свой счет, вы можете сохранить старые результаты в заголовке, вычеркнув их. Например:
# Ruby, <s>104</s> <s>101</s> 96 bytes
(Язык в настоящее время не отображается, но фрагмент требует и анализирует его, и я могу добавить таблицу лидеров по языкам в будущем.)
источник
u/\. y
ближайшее время?GolfScript, 90 байт
Онлайн демо
Это адаптация моего (более простого) кода подсчета разделов, который вместо простого отслеживания счетчика отслеживает как счетчик, так и равномерно выбранный из подсчитанных элементов.
Совместное сравнение двух:
Отличия:
~
, потому что это программа, а не фрагмент.[1.]
замещающие1
соответствует изменению в том, что это отслеживается.{(\{)}%+}%
увеличивает каждый элемент в этом разделе, и{1+}%
добавляет1
к разделу.0
становится[0]
(гольфом1,
) как часть изменения того, что отслеживается, но потому что оно должно оставаться массивом при добавлении к другому, ему нужно дополнительное[ ]
.{+}*
становится взвешенным выбором из разделов в сочетании с суммированием их количества.(;`
удаляет счетчик из вывода и помещает раздел в хороший формат.Тестовая структура
Настройте начальные 7000, если вы хотите запустить другое количество испытаний. Обратите внимание, что это слишком медленно для онлайн-демонстрации.
источник
Java,
285267 байтЭто тот же метод, что и в ответе TheBestOne, но он использует простой массив вместо карты. Кроме того, вместо того, чтобы возвращать случайный раздел как
List
, он выводит их на консоль.Ниже приведена тестовая программа, которая запускает ее 100000 раз. Например
n=5
, все подходы были в пределах 0,64% от идеальной 1/7 в моем последнем запуске.источник
Math.min
вызов вплоть до(k<n?k:n)
, вы можете пойти дальше, канав его полностью и просто делать две проверки:b<k&b++<n
. Вы также можете легко отказатьсяn>0
от условной части цикла (посколькуn>0&b<n
сводится к тому,b<n
когдаb
гарантированно неотрицательный).int
объявления.CJam,
6456 байтВы можете проверить это с помощью этого скрипта:
объяснение
источник
Pyth, 64 байта
Использует /programming//a/2163753/4230423 за исключением того, что a) нет кэша, поскольку Pyth автоматически запоминает, b) печатает каждый вместо добавления в список, и c) переводится в Pyth.
Я опубликую объяснение этого, когда у меня будет время, но вот соответствующий код Python:
Изменить: я наконец-то нашел время для объяснения:
источник
Октава, 200
Ungolfed:
Постройте квадратную матрицу, где каждая ячейка (m, n) отражает количество разделов
m
, наибольшее число которыхn
, согласно любезно процитированному Knuth extract @feersum. Например,5,2
дает нам 2, потому что есть два допустимых раздела2,2,1
и2,1,1,1
.6,3
дает нам 3 для3,1,1,1
,3,2,1
и3,3
.Теперь мы можем детерминистически найти p-й раздел. Здесь мы генерируем
p
случайное число, но вы можете немного изменить сценарий, такp
что это параметр:Теперь мы можем детерминистически показать, что каждый результат зависит исключительно от p:
Таким образом, возвращаясь к оригиналу, где p генерируется случайным образом, мы можем быть уверены, что каждый результат одинаково вероятен.
источник
(2,2,1)
и(2,1,1,1,1)
(так как у двух перечисленных вами номеров больше, чем2
).2
. Я имел ввиду последнее.R, 198 байт
Ungolfed:
Он следует той же структуре, что и отличное решение @ dcsohl в Octave , и, следовательно, также основан на экстракте Кнута, опубликованном @feersum.
Я отредактирую это позже, если смогу найти более креативное решение в R. Тем временем, любой вклад, конечно, приветствуется.
источник
Java, 392 байта
Позвони с
a(n)
. Возвращает aList
изInteger
sОтступ:
Адаптировано с /programming//a/2163753/4230423 и в гольф
Как это работает: мы можем вычислить, сколько разделов целого числа n существует за O ( n 2 ) времени. В качестве побочного эффекта это приводит к таблице размера O ( n 2 ), которую мы затем можем использовать для генерации k- го раздела n для любого целого числа k за время O ( n ).
Итак, пусть total = количество разделов. Выберите случайное число k от 0 до итога - 1. Сгенерируйте k- й раздел.
Как обычно , предложения приветствуются :)
источник
Python 2, 173 байта
Рекурсивный делает словарь
d
, с ключами ,k
представляющими собой пару(n,m)
путиk=67*n+m
( с помощью гарантированногоn<=65
). Запись является кортежем номера разделаn
вm
части и случайных таких разбиений. Подсчет вычисляется по рекурсивной формуле (спасибо feersum за указание на это)f(n,m) = f(n-1,m-1) + f(n,n-m)
,и случайный раздел обновляется путем выбора одной из двух его ветвей с вероятностью, пропорциональной его количеству. Обновление выполняется путем добавления, добавляя a
1
для первой ветви и увеличивая каждый элемент для второй.У меня было много проблем с получением значений за пределами
m
иn
подсчетом нуля. Сначала я использовал словарь со значением по умолчанию 0 и пустым списком. Здесь я использую список и дополняю его этой записью по умолчанию. Отрицательные индексы приводят к тому, что список читается с его конца, что дает запись по умолчанию, которая не близка к концу, достигнутому когда-либо, а обтекания касаются только области, гдеm>n
.источник
80386 машинный код, 105 байт
Hexdump кода:
В качестве функции C:
void random_partition(int n, int result[]);
. Возвращает результат в виде списка чисел в предоставленном буфере; он не помечает конец списка никоим образом, но пользователь может обнаружить конец, накапливая числа - список заканчивается, когда сумма равнаn
.Как использовать (в Visual Studio):
Пример вывода (с n = 64):
Это требует много объяснений ...
Конечно, я использовал алгоритм, который использовали все остальные; не было никакого выбора с требованием о сложности. Поэтому мне не нужно слишком много объяснять алгоритм. Тем не мение:
Обозначаю
f(n, m)
количество разделенийn
элементов с использованием частей, не превышающееm
. Я храню их в двумерном массиве (объявленном в C какf[65][64]
), где первый индексn
, а второйm-1
. Я решил, что поддержкаn=65
была слишком большой проблемой, поэтому отказался от нее ...Вот код C, который вычисляет эту таблицу:
Этот код имеет некоторый запутанный стиль, поэтому он может быть легко преобразован в язык ассемблера. Он рассчитывает элементы до
f(n, n)
, который является количеством разбиенийn
элементов. Когда этот код завершен, временная переменнаяc
содержит необходимое число, которое можно использовать для выбора случайного разбиения:Позже, это
index
преобразовано в требуемый формат (список чисел), используя сгенерированную таблицу.Этот код также оптимизирован для преобразования на язык ассемблера. Есть небольшая «ошибка»: если разделение не содержит
1
числа в конце, последний цикл встречаетсяn = 0
и выводит ненужный1
элемент. Однако это не повредит, потому что код печати отслеживает сумму числа и не печатает это постороннее число.При преобразовании во встроенную сборку этот код выглядит следующим образом:
Некоторые забавные вещи, чтобы отметить:
rdrand
инструкция)ah
, что дает мне автоматическое умножение на 256. Чтобы воспользоваться этим, я пожертвовал поддержкойn = 65
. Я надеюсь, что я могу быть оправдан за этот грех ...Выделение пространства в стеке осуществляется путем вычитания 0x4100 из регистра указателя стека
esp
. Это 6-байтовая инструкция! При добавлении этого числа обратно мне удалось сделать это за 5 байтов:При отладке этой функции в MS Visual Studio я обнаружил, что происходит сбой при записи данных в пространство, выделенное для стека! Немного покопавшись, я обнаружил какую-то защиту от переполнения стека: ОС, кажется, выделяет для стека только очень ограниченный диапазон виртуальных адресов; если функция обращается к адресу слишком далеко, ОС предполагает, что это переполнение, и убивает программу. Однако, если функция имеет много локальных переменных, ОС делает некоторую дополнительную «магию», чтобы заставить ее работать. Поэтому я должен вызвать пустую функцию с большим массивом, выделенным в стеке. После возврата этой функции выделяются дополнительные страницы VM стека и их можно использовать.
источник