Поиск всех перестановок для заданного количества футбольных игр в ocaml

Question

Мне нужно написать ряд функций: int -> int -> list list list, поэтому первое int для количества игр и второе int для заработанных очков.

Я уже думал об эмпирическом решении, создавая все перестановки и фильтруя список, но я думаю, что это будет очень грязное решение с большим количеством строк кода. И я не могу найти другой способ решить эту проблему.

Даны следующие типы

type result = Win (* 3 points *)
| Draw (* 1 point *)
| Loss (* 0 points *)

так что если я позвоню

series 3 4

решение должно быть:

[[Win ;Draw ;Loss]; [Win ;Loss ;Draw]; [Draw ;Win ;Loss];
[Draw ;Loss ;Win]; [Loss ;Win ;Draw]; [Loss ;Draw ;Win]]

Может быть, кто-то может дать мне подсказку или пример кода, как начать.

Answer 1

Простое рекурсивное решение могло бы пойти по этому пути:

• , если есть 0 игр, в которые нужно играть, и 0 очков, чтобы заработать, то существует ровно одно (пустое) решение
• , еслиесть 0 игр, чтобы играть и 1 или более очков, чтобы заработать, нет решения.
• в противном случае, p очков должны быть заработаны в g играх: любое решение для p очков в g-1Игра может быть расширена до решения, добавив Loss перед ним.Если p>=1, вы также можете добавить Draw к любому решению для p-1 в g-1 играх, а если p>=3, возможны также варианты, начинающиеся с Win.

.

Answer 2

Рассмотрим вызовы вида series n (n / 2) и рассмотрим случаи, когда все игры были Draw или Loss.При этих ограничениях количество ответов пропорционально 2^n/sqrt(n).(Ребята онлайн получают это от приближения Стирлинга.)

Это не включает серию, где кто-нибудь выигрывает игру.Таким образом, фактические списки результатов в целом будут длиннее.

Я заключаю, что число возможных ответов гигантское, и, следовательно, ваши реальные дела будут небольшими.

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

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

Вы можетелегко написать функцию для перечисления всех возможных последовательностей длиной n, взятых из Win, Lose, Draw.Затем вы можете отфильтровать их для правильной суммы.Асимптотически это, вероятно, лишь немного хуже, чем самый быстрый алгоритм, из-за почти экспоненциального поведения, описанного выше.