22

Tantangan Anda adalah sederhana: Mengingat integer N , ouput setiap daftar bilangan bulat positif yang jumlah untuk N . Misalnya, jika inputnya 5, Anda harus output

[1, 1, 1, 1, 1]
[1, 1, 1, 2]
[1, 1, 3]
[1, 2, 2]
[1, 4]
[2, 3]
[5]

Daftar ini tidak harus berupa output dalam urutan tertentu, juga angka-angka di dalam setiap daftar. Misalnya, ini juga akan menjadi output yang dapat diterima untuk '5':

[1, 1, 1, 2]
[5]
[3, 1, 1]
[2, 1, 2]
[4, 1]
[1, 1, 1, 1, 1]
[2, 3]

Anda dapat dengan aman berasumsi bahwa input akan menjadi bilangan bulat positif, dan Anda dapat mengambil nomor ini dalam format apa pun yang masuk akal.

Anda tidak boleh menggunakan fungsi bawaan apa pun yang melakukan ini.

Jika program Anda gagal atau terlalu lama untuk N besar ini OK, tetapi Anda harus paling tidak menghasilkan output yang benar untuk 15 pertama.

Celah standar berlaku, dan jawaban tersingkat dalam byte menang!

Tes IO

1:
[[1]]

2:
[[1, 1], [2]]

3:
[[1, 1, 1], [1, 2], [3]]

4:
[[1, 1, 1, 1], [1, 1, 2], [1, 3], [2, 2], [4]]

5:
[[1, 1, 1, 1, 1], [1, 1, 1, 2], [1, 1, 3], [1, 2, 2], [1, 4], [2, 3], [5]]

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

10:
[[1, 1, 1, 1, 1, 1, 1, 1, 1, 1], [1, 1, 1, 1, 1, 1, 1, 1, 2], [1, 1, 1, 1, 1, 1, 1, 3], [1, 1, 1, 1, 1, 1, 2, 2], [1, 1, 1, 1, 1, 1, 4], [1, 1, 1, 1, 1, 2, 3], [1, 1, 1, 1, 1, 5], [1, 1, 1, 1, 2, 2, 2], [1, 1, 1, 1, 2, 4], [1, 1, 1, 1, 3, 3], [1, 1, 1, 1, 6], [1, 1, 1, 2, 2, 3], [1, 1, 1, 2, 5], [1, 1, 1, 3, 4], [1, 1, 1, 7], [1, 1, 2, 2, 2, 2], [1, 1, 2, 2, 4], [1, 1, 2, 3, 3], [1, 1, 2, 6], [1, 1, 3, 5], [1, 1, 4, 4], [1, 1, 8], [1, 2, 2, 2, 3], [1, 2, 2, 5], [1, 2, 3, 4], [1, 2, 7], [1, 3, 3, 3], [1, 3, 6], [1, 4, 5], [1, 9], [2, 2, 2, 2, 2], [2, 2, 2, 4], [2, 2, 3, 3], [2, 2, 6], [2, 3, 5], [2, 4, 4], [2, 8], [3, 3, 4], [3, 7], [4, 6], [5, 5], [10]]

Kasing uji super besar: 15 harus menampilkan ini

[[1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1], [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2], [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 3], [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 2], [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 4], [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 3], [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 5], [1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 2, 2], [1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 4], [1, 1, 1, 1, 1, 1, 1, 1, 1, 3, 3], [1, 1, 1, 1, 1, 1, 1, 1, 1, 6], [1, 1, 1, 1, 1, 1, 1, 1, 2, 2, 3], [1, 1, 1, 1, 1, 1, 1, 1, 2, 5], [1, 1, 1, 1, 1, 1, 1, 1, 3, 4], [1, 1, 1, 1, 1, 1, 1, 1, 7], [1, 1, 1, 1, 1, 1, 1, 2, 2, 2, 2], [1, 1, 1, 1, 1, 1, 1, 2, 2, 4], [1, 1, 1, 1, 1, 1, 1, 2, 3, 3], [1, 1, 1, 1, 1, 1, 1, 2, 6], [1, 1, 1, 1, 1, 1, 1, 3, 5], [1, 1, 1, 1, 1, 1, 1, 4, 4], [1, 1, 1, 1, 1, 1, 1, 8], [1, 1, 1, 1, 1, 1, 2, 2, 2, 3], [1, 1, 1, 1, 1, 1, 2, 2, 5], [1, 1, 1, 1, 1, 1, 2, 3, 4], [1, 1, 1, 1, 1, 1, 2, 7], [1, 1, 1, 1, 1, 1, 3, 3, 3], [1, 1, 1, 1, 1, 1, 3, 6], [1, 1, 1, 1, 1, 1, 4, 5], [1, 1, 1, 1, 1, 1, 9], [1, 1, 1, 1, 1, 2, 2, 2, 2, 2], [1, 1, 1, 1, 1, 2, 2, 2, 4], [1, 1, 1, 1, 1, 2, 2, 3, 3], [1, 1, 1, 1, 1, 2, 2, 6], [1, 1, 1, 1, 1, 2, 3, 5], [1, 1, 1, 1, 1, 2, 4, 4], [1, 1, 1, 1, 1, 2, 8], [1, 1, 1, 1, 1, 3, 3, 4], [1, 1, 1, 1, 1, 3, 7], [1, 1, 1, 1, 1, 4, 6], [1, 1, 1, 1, 1, 5, 5], [1, 1, 1, 1, 1, 10], [1, 1, 1, 1, 2, 2, 2, 2, 3], [1, 1, 1, 1, 2, 2, 2, 5], [1, 1, 1, 1, 2, 2, 3, 4], [1, 1, 1, 1, 2, 2, 7], [1, 1, 1, 1, 2, 3, 3, 3], [1, 1, 1, 1, 2, 3, 6], [1, 1, 1, 1, 2, 4, 5], [1, 1, 1, 1, 2, 9], [1, 1, 1, 1, 3, 3, 5], [1, 1, 1, 1, 3, 4, 4], [1, 1, 1, 1, 3, 8], [1, 1, 1, 1, 4, 7], [1, 1, 1, 1, 5, 6], [1, 1, 1, 1, 11], [1, 1, 1, 2, 2, 2, 2, 2, 2], [1, 1, 1, 2, 2, 2, 2, 4], [1, 1, 1, 2, 2, 2, 3, 3], [1, 1, 1, 2, 2, 2, 6], [1, 1, 1, 2, 2, 3, 5], [1, 1, 1, 2, 2, 4, 4], [1, 1, 1, 2, 2, 8], [1, 1, 1, 2, 3, 3, 4], [1, 1, 1, 2, 3, 7], [1, 1, 1, 2, 4, 6], [1, 1, 1, 2, 5, 5], [1, 1, 1, 2, 10], [1, 1, 1, 3, 3, 3, 3], [1, 1, 1, 3, 3, 6], [1, 1, 1, 3, 4, 5], [1, 1, 1, 3, 9], [1, 1, 1, 4, 4, 4], [1, 1, 1, 4, 8], [1, 1, 1, 5, 7], [1, 1, 1, 6, 6], [1, 1, 1, 12], [1, 1, 2, 2, 2, 2, 2, 3], [1, 1, 2, 2, 2, 2, 5], [1, 1, 2, 2, 2, 3, 4], [1, 1, 2, 2, 2, 7], [1, 1, 2, 2, 3, 3, 3], [1, 1, 2, 2, 3, 6], [1, 1, 2, 2, 4, 5], [1, 1, 2, 2, 9], [1, 1, 2, 3, 3, 5], [1, 1, 2, 3, 4, 4], [1, 1, 2, 3, 8], [1, 1, 2, 4, 7], [1, 1, 2, 5, 6], [1, 1, 2, 11], [1, 1, 3, 3, 3, 4], [1, 1, 3, 3, 7], [1, 1, 3, 4, 6], [1, 1, 3, 5, 5], [1, 1, 3, 10], [1, 1, 4, 4, 5], [1, 1, 4, 9], [1, 1, 5, 8], [1, 1, 6, 7], [1, 1, 13], [1, 2, 2, 2, 2, 2, 2, 2], [1, 2, 2, 2, 2, 2, 4], [1, 2, 2, 2, 2, 3, 3], [1, 2, 2, 2, 2, 6], [1, 2, 2, 2, 3, 5], [1, 2, 2, 2, 4, 4], [1, 2, 2, 2, 8], [1, 2, 2, 3, 3, 4], [1, 2, 2, 3, 7], [1, 2, 2, 4, 6], [1, 2, 2, 5, 5], [1, 2, 2, 10], [1, 2, 3, 3, 3, 3], [1, 2, 3, 3, 6], [1, 2, 3, 4, 5], [1, 2, 3, 9], [1, 2, 4, 4, 4], [1, 2, 4, 8], [1, 2, 5, 7], [1, 2, 6, 6], [1, 2, 12], [1, 3, 3, 3, 5], [1, 3, 3, 4, 4], [1, 3, 3, 8], [1, 3, 4, 7], [1, 3, 5, 6], [1, 3, 11], [1, 4, 4, 6], [1, 4, 5, 5], [1, 4, 10], [1, 5, 9], [1, 6, 8], [1, 7, 7], [1, 14], [2, 2, 2, 2, 2, 2, 3], [2, 2, 2, 2, 2, 5], [2, 2, 2, 2, 3, 4], [2, 2, 2, 2, 7], [2, 2, 2, 3, 3, 3], [2, 2, 2, 3, 6], [2, 2, 2, 4, 5], [2, 2, 2, 9], [2, 2, 3, 3, 5], [2, 2, 3, 4, 4], [2, 2, 3, 8], [2, 2, 4, 7], [2, 2, 5, 6], [2, 2, 11], [2, 3, 3, 3, 4], [2, 3, 3, 7], [2, 3, 4, 6], [2, 3, 5, 5], [2, 3, 10], [2, 4, 4, 5], [2, 4, 9], [2, 5, 8], [2, 6, 7], [2, 13], [3, 3, 3, 3, 3], [3, 3, 3, 6], [3, 3, 4, 5], [3, 3, 9], [3, 4, 4, 4], [3, 4, 8], [3, 5, 7], [3, 6, 6], [3, 12], [4, 4, 7], [4, 5, 6], [4, 11], [5, 5, 5], [5, 10], [6, 9], [7, 8], [15]]

Katalog

Cuplikan Stack di bagian bawah posting ini menghasilkan katalog dari jawaban a) sebagai daftar solusi terpendek per bahasa dan b) sebagai leaderboard keseluruhan.

Untuk memastikan bahwa jawaban Anda muncul, silakan mulai jawaban Anda dengan tajuk utama, menggunakan templat Penurunan harga berikut:

## Language Name, N bytes

di mana Nukuran kiriman Anda. Jika Anda meningkatkan skor Anda, Anda dapat menyimpan skor lama di headline, dengan mencoretnya. Contohnya:

## Ruby, <s>104</s> <s>101</s> 96 bytes

Tampilkan cuplikan kode

<style>body { text-align: left !important} #answer-list { padding: 10px; width: 290px; float: left; } #language-list { padding: 10px; width: 290px; float: left; } table thead { font-weight: bold; } table td { padding: 5px; }</style><script src="https://ajax.googleapis.com/ajax/libs/jquery/2.1.1/jquery.min.js"></script> <link rel="stylesheet" type="text/css" href="//cdn.sstatic.net/codegolf/all.css?v=83c949450c8b"> <div id="language-list"> <h2>Shortest Solution by Language</h2> <table class="language-list"> <thead> <tr><td>Language</td><td>User</td><td>Score</td></tr> </thead> <tbody id="languages"> </tbody> </table> </div> <div id="answer-list"> <h2>Leaderboard</h2> <table class="answer-list"> <thead> <tr><td></td><td>Author</td><td>Language</td><td>Size</td></tr> </thead> <tbody id="answers"> </tbody> </table> </div> <table style="display: none"> <tbody id="answer-template"> <tr><td>{{PLACE}}</td><td>{{NAME}}</td><td>{{LANGUAGE}}</td><td>{{SIZE}}</td><td><a href="{{LINK}}">Link</a></td></tr> </tbody> </table> <table style="display: none"> <tbody id="language-template"> <tr><td>{{LANGUAGE}}</td><td>{{NAME}}</td><td>{{SIZE}}</td><td><a href="{{LINK}}">Link</a></td></tr> </tbody> </table><script>var QUESTION_ID = 84165; var ANSWER_FILTER = "!t)IWYnsLAZle2tQ3KqrVveCRJfxcRLe"; var COMMENT_FILTER = "!)Q2B_A2kjfAiU78X(md6BoYk"; var OVERRIDE_USER = 31716; var answers = [], answers_hash, answer_ids, answer_page = 1, more_answers = true, comment_page; function answersUrl(index) { return "https://api.stackexchange.com/2.2/questions/" + QUESTION_ID + "/answers?page=" + index + "&pagesize=100&order=desc&sort=creation&site=codegolf&filter=" + ANSWER_FILTER; } function commentUrl(index, answers) { return "https://api.stackexchange.com/2.2/answers/" + answers.join(';') + "/comments?page=" + index + "&pagesize=100&order=desc&sort=creation&site=codegolf&filter=" + COMMENT_FILTER; } function getAnswers() { jQuery.ajax({ url: answersUrl(answer_page++), method: "get", dataType: "jsonp", crossDomain: true, success: function (data) { answers.push.apply(answers, data.items); answers_hash = []; answer_ids = []; data.items.forEach(function(a) { a.comments = []; var id = +a.share_link.match(/\d+/); answer_ids.push(id); answers_hash[id] = a; }); if (!data.has_more) more_answers = false; comment_page = 1; getComments(); } }); } function getComments() { jQuery.ajax({ url: commentUrl(comment_page++, answer_ids), method: "get", dataType: "jsonp", crossDomain: true, success: function (data) { data.items.forEach(function(c) { if (c.owner.user_id === OVERRIDE_USER) answers_hash[c.post_id].comments.push(c); }); if (data.has_more) getComments(); else if (more_answers) getAnswers(); else process(); } }); } getAnswers(); var SCORE_REG = /<h\d>\s*([^\n,<]*(?:<(?:[^\n>]*>[^\n<]*<\/[^\n>]*>)[^\n,<]*)*),.*?(\d+)(?=[^\n\d<>]*(?:<(?:s>[^\n<>]*<\/s>|[^\n<>]+>)[^\n\d<>]*)*<\/h\d>)/; var OVERRIDE_REG = /^Override\s*header:\s*/i; function getAuthorName(a) { return a.owner.display_name; } function process() { var valid = []; answers.forEach(function(a) { var body = a.body; a.comments.forEach(function(c) { if(OVERRIDE_REG.test(c.body)) body = '<h1>' + c.body.replace(OVERRIDE_REG, '') + '</h1>'; }); var match = body.match(SCORE_REG); if (match) valid.push({ user: getAuthorName(a), size: +match[2], language: match[1], link: a.share_link, }); else console.log(body); }); valid.sort(function (a, b) { var aB = a.size, bB = b.size; return aB - bB }); var languages = {}; var place = 1; var lastSize = null; var lastPlace = 1; valid.forEach(function (a) { if (a.size != lastSize) lastPlace = place; lastSize = a.size; ++place; var answer = jQuery("#answer-template").html(); answer = answer.replace("{{PLACE}}", lastPlace + ".") .replace("{{NAME}}", a.user) .replace("{{LANGUAGE}}", a.language) .replace("{{SIZE}}", a.size) .replace("{{LINK}}", a.link); answer = jQuery(answer); jQuery("#answers").append(answer); var lang = a.language; lang = jQuery('<a>'+lang+'</a>').text(); languages[lang] = languages[lang] || {lang: a.language, lang_raw: lang.toLowerCase(), user: a.user, size: a.size, link: a.link}; }); var langs = []; for (var lang in languages) if (languages.hasOwnProperty(lang)) langs.push(languages[lang]); langs.sort(function (a, b) { if (a.lang_raw > b.lang_raw) return 1; if (a.lang_raw < b.lang_raw) return -1; return 0; }); for (var i = 0; i < langs.length; ++i) { var language = jQuery("#language-template").html(); var lang = langs[i]; language = language.replace("{{LANGUAGE}}", lang.lang) .replace("{{NAME}}", lang.user) .replace("{{SIZE}}", lang.size) .replace("{{LINK}}", lang.link); language = jQuery(language); jQuery("#languages").append(language); } }</script>

Expand snippet

code-golf math number-theory combinatorics integer-partitions DJMcMayhem
sumber

1

Terkait: codegolf.stackexchange.com/questions/46991/…

DJMcMayhem

2

Bisakah Anda mengklarifikasi apa yang Anda maksud dengan pegangan ?

Dennis

@ flawr Saya tidak setuju - menemukan semua partisi cukup berbeda dari menemukan partisi ketat. Namun, yang satu ini mungkin merupakan target penipuan.

Mego

Saya pikir mencari partisi yang tidak teratur dan tidak membatasi jumlah bagian membuat ini cukup berbeda.

xnor

Bisakah Anda menjelaskan apa yang Anda maksud dengan buitin ?

Leaky Nun

6

Pyth, 10 9 byte

{SMlMM./U

Tidak terlalu yakin apakah ini tidak curang, tetapi aturan hanya mengatakan seseorang tidak dapat menggunakan partisi integer (itu tidak dinyatakan dengan jelas dalam pertanyaan itu sendiri, tetapi komentar oleh OP dalam pertanyaan mengatakan integer partisi). Saya menggunakan partisi daftar ~~string~~ , yang membuat irisan daftar yang menyambung hingga daftar "ibu". Saya percaya saya harus berterima kasih kepada @Maltysen untuk gagasan menggunakan daftar daripada string.

n = 15 membutuhkan waktu kurang dari satu detik di mesin saya.

Dalam pseudocode dataflow:

              input       // initial data
        U     range       // makes a list of length equal to input
      ./      partition   // partitions string
   lMM        length      // length of each substring in each way to partition
 SM           sort        // sort each way to partition
{             deduplicate // removes all duplicate after sorting
              print       // implicit, output final result

Cobalah online di sini.

busukxuan
sumber

{mSlMd./*Nmenghemat satu byte

Leaky Nun

Anda bisa menggunakan 7 byte jika Anda menggunakan daftar partisi daripada partisi string: pyth.herokuapp.com/?code=sMM.%2Fm1&input=5&debug=0

Maltysen

@ LeakyNun Yah aku benar-benar mencoba dan itu tidak menghemat satu byte. Ketika saya melihat komentar Anda, saya menemukan bahwa jawaban saya sebenarnya 10 byte, jadi saya benar-benar salah hitung (lupa blok gedit mulai dari 1).

busukxuan

@Maltysen Anda perlu mengurutkan setiap sub-daftar, dan kemudian deduplicate.

busukxuan

@Maltysen Anda benar, menggunakan daftar tidak mempersingkatnya. Saya mencoba menambahkan pengurutan dan deduplikat ke kode yang Anda tautkan dan itu tidak membantu, tapi itu semua berkat Anda bahwa saya mendapat ide untuk mengganti * N dengan U. Terima kasih!

busukxuan

6

Pyth, 18 byte

L?b{SM+R-bsdsyMb]Y

Cobalah online! (The ypada akhirnya digunakan untuk memanggil fungsi)

Ini cukup cepat.

Ini menggunakan rekursi. Jika input b, metode saya akan menghasilkan partisi dari 0ke b-1, dan kemudian menghasilkan partisi yang benar dari masing-masing.

Misalnya ketika b=4:

b=0 memberi [[]]
b=1 memberi [[1]]
b=2 memberi [[2], [1, 1]]
b=3 memberi [[3], [1, 2], [1, 1, 1]]

Kemudian, untuk setiap partisi b=0, tambahkan 4(untuk membuat jumlah 4); untuk setiap partisi b=1, tambahkan 3(untuk membuat jumlah 4); dll.

Ini terutama cara kerjanya.

L?b{SM+R-bsdsyMb]Y

L                    define a function called "y" which takes an argument: "b"
 ?b                  test for truthiness of b (in this case, test if b>0).


   {SM+R-bsdsyMb     if truthy:

             yMb         call this function from 0 to b-1.
            s            unpack each list of partitions, generating only partitions.
      +R                 to each partition (d), append:
        -                    the difference of
         b                   b (the argument) and
          sd                 the sum of d (the partition).
    SM                   sort each partition.
   {                     remove duplicates.


                ]Y   if falsey:

                 Y       yield [].
                ]        yield [[]].

Biarawati Bocor
sumber

5

MATL , 20 byte

:"0Gq:@XNG3$Yc!dS!Xu

Cobalah online!

Untuk input 15dibutuhkan sekitar 2 detik dalam kompiler online.

Penjelasan

Ini berfungsi dengan menghasilkan titik partisi dan kemudian mengonversi ke panjang partisi . Yang saya maksud dengan ini adalah sebagai berikut. Diberikan input N = 5, kemungkinan partisi adalah [2 2 1]. Ini diwakili oleh titik partisi [0 2 4 5], sehingga perbedaan (atau panjang) titik partisi yang berurutan memberikan hasil partisi dari nomor input.

Semua array poin partisi dimulai dengan 0 dan diakhiri dengan N . Jumlah k titik tengah bervariasi dari 0 hingga N -1. Untuk N dan k yang diberikan, titik-titik perantara dapat dihasilkan sebagai kombinasi angka [1, 2, ..., N -1] yang diambil k pada suatu waktu.

Beberapa array titik partisi dapat menimbulkan hasil yang sama dalam urutan yang berbeda. Misalnya, titik partisi [0 1 3 5] akan memberikan panjang partisi [1 2 2], yaitu sama dengan yang sebelumnya [2 2 1] hanya dalam urutan yang berbeda. Ini harus diperhitungkan dengan menyortir setiap larik panjang partisi dan menghapus duplikat .

:        % Implicitly input N. Push [1 2 ... N]. These are the possible values of k,
         % except with N instead of 0
"        % For each
  0      %   Push 0
  Gq:    %   Push [1 ... N-1]. These the possible intermediate points
  @XN    %   Push k and produce the combinations. Each k produces a 2D array with
         %   each combination on a row. The value k=N produces an empty array
  G      %   Push N
  3$Yc   %   Prepend a column of zeros and append a column of N to the array
  !d     %   Transpose. Consecutive differences of each column
  S!     %   Sort each column. Transpose
  Xu     %   Keep only unique rows
         % Implicitly end for and display all arrays in the stack

Luis Mendo
sumber

1

Bagus, konsep titik partisi adalah cara yang sangat cerdas untuk menyelesaikan ini.

Nick

@Nick, terima kasih! Dan selamat datang (aktif di) situs ini! :-)

Luis Mendo

5

Haskell, 53 byte

p=[[]]:[map(1:)q++[a+1:b|a:b<-q,all(a<)b]|q<-p]
(p!!)

Anders Kaseorg
sumber

5

J, 49 42 36 35 32 byte

a:1&([:~.@,(,;}./:~@,(+{.))&>)~]

Ini diam-diam sekarang!

Membangun partisi integer dari n dengan membangun partisi integer dari 1 ke n . Menghitung hasil untuk n = 15 dalam milidetik.

Dimulai dengan partisi integer awal [[1]]yang sesuai dengan n = 1, buat partisi integer berikutnya dengan menggabungkan hasil dari dua operasi: menambahkan 1 untuk setiap partisi; menambah nilai terkecil dengan 1 di setiap partisi. Tentu saja, partisi duplikat akan dihapus. Untuk mendapatkan partisi integer n = 2 dan seterusnya,

Partition for n = 1
[[1]]

Partition for n = 2
[[1, 1]] join [[2]]
= [[1, 1], [2]]

Partition for n = 3
[[1, 2], [1, 1, 1]] join [[3], [1, 2]]
= [[3], [1, 2], [1, 1, 1]]

... and so on

Pemakaian

   f =: a:1&([:~.@,(,;}./:~@,(+{.))&>)~]
   f 1
┌─┐
│1│
└─┘
   f 2
┌───┬─┐
│1 1│2│
└───┴─┘
   f 3
┌─────┬───┬─┐
│1 1 1│1 2│3│
└─────┴───┴─┘
   f 5
┌─────────┬───────┬─────┬───┬─────┬───┬─┐
│1 1 1 1 1│1 1 1 2│1 2 2│2 3│1 1 3│1 4│5│
└─────────┴───────┴─────┴───┴─────┴───┴─┘
   # f 15
176

Penjelasan

Karena J tidak mendukung array yang tidak rata, setiap partisi harus dikotak sehingga mereka tidak akan menjadi nol saat ditambahkan ke partisi lain.

a:1&([:~.@,(,;}./:~@,(+{.))&>)~]  Input: n
a:                                The empty box
                               ]  Get the input n
  1&(                        )~   Repeat n times with an initial array of one empty box
           (              )&>       Operate on each partition
                     (   )            Hook a partition
                       {.               Get its head (the smallest value)
  1                   +                 Add 1 to it
  1           }.                      Drop the first value in each partition
                    ,                 Join the previous two results
                /:~@                  Sort it
  1         ,                         Prepend a 1 to the initial partition
             ;                        Box the last two results and join them
     [:   ,                         Flatten the pairs of boxes
       ~.@                          Remove duplicates and return
                                  Return the final result where each box
                                  is a partition of n

mil
sumber

4

Python, 65 byte

Python 3

def f(n,i=1,l=[]):n or print(l);i>n or[f(n-i,i,[i]+l),f(n,i+1,l)]

Fungsi ini mengakumulasi partisi dan mencetak output, bercabang pada pilihan. Ini memutuskan berapa banyak 1 untuk dimasukkan ke dalam partisi, berapa banyak 2, dan seterusnya. Untuk setiap nilai i, itu baik

Menambahkan sebagian ukuran i, dan berkurangn menjadi n-i, atau
Pindah ke i+1

Jika i>n, maka tidak ada lagi bagian yang dapat dibuat, sehingga berhenti. Jika njatuh ke0 , partisi berhasil dan dicetak.

Python 2

f=lambda n,i=1:n/i and[l+[i]for l in f(n-i,i)]+f(n,i+1)or[[]][n:]

Metode rekursif yang menampilkan daftar partisi. Seperti dengan kode Python 3, itu menghitung ukuran bagiani dan memutuskan pada setiap langkah apakah akan menambah bagian lain ukuran iatau berhenti.

Keduanya melakukan n=15hampir secara instan.

Tidak
sumber

3

Javascript, 194 byte

p=n=>{var a=[];for(var i=1;i<=n-i;i+=1){for(v of p(n-i)){v.push(i);a.push(v.sort())}}a.push([n]);return a};n=5;s=p(n).map(v=>JSON.stringify(v));s=s.filter((v,i)=>s.indexOf(v)==i);console.log(s);

Non-minified

Menemukan keunikan dengan menyortir dan membandingkan ke suatu string adalah suatu peretasan, tetapi mungkin menghemat ruang.

p = n => {
    var a = [];

    for (var i = 1; i <= n-i; i++)
    {
        for (v of p(n-i)) {
            v.push(i);
            a.push(v.sort());
        }
    }

    a.push([n]);

    return a;
}

n = 5;
s = p(n).map(v =>  JSON.stringify(v));
s = s.filter((v,i) => s.indexOf(v) == i);
console.log(s);

Nick
sumber

4

Quite a hack but saves spaceItulah tepatnya tentang situs ini. : D

DJMcMayhem

2

Python 3.5, 82 72 byte

f=lambda n:{(*sorted([*p,i]),)for i in range(1,n)for p in f(n-i)}|{(n,)}

Mengembalikan satu set tupel. n = 15 selesai secara instan.

Mengujinya pada repl.it .

Dennis
sumber

2

Haskell, 44 byte

0%m=[[]]
n%m=[j:r|j<-[m..n],r<-(n-j)%j]
(%1)

Fungsi bantu n%mmemberikan partisi nmenjadi beberapa bagian ≥m, dengan fungsi utama menggunakan m=1. Ini cabang dari setiap entri pertama jdengan m≤j≤n, recursing pada partisi sisa n-jmenjadi bagian-bagian yang setidaknya j. Kasing dasar n==0hanya memberikan partisi kosong.

Tidak
sumber

1

Pyth, 17 byte

L|{SMs+LVrb0yMb]Y

Menentukan fungsi bernama y. Cobalah online .

Anders Kaseorg
sumber

1

Jelly , 9 byte

b1ŒṖḅ1Ṣ€Q

Cobalah online!

Bagaimana itu bekerja

b1ŒṖḅ1Ṣ€Q  Main link. Argument: n (integer)

b1         Convert n to unary, i.e., a list A of n 1's.
  ŒṖ       Generate all partitions of the list A.
    ḅ1     Convert each flat list from unary to integer.
      Ṣ€   Sort each resulting list.
        Q  Unique; deduplicate the lists.

Dennis
sumber

1

J, 39 byte

[:~.i.<@\:~@(#;.1~"1 0)1,@{@;(<1 0)#~<:

Ini adalah kata kerja monadik yang mengambil integer dan mengembalikan array array kotak. Coba di sini. Pemakaian:

   p =: [:~.i.<@\:~@(#;.1~"1 0)1,@{@;(<1 0)#~<:
   p 3
+-----+---+-+
|1 1 1|2 1|3|
+-----+---+-+

Pada input 15, ini berjalan sekitar satu detik di mesin saya.

Penjelasan

Tantangan ini segera tampak seperti pekerjaan untuk Katalog ( {) dan Cut ( ;.). Garis besar algoritme adalah:

Menghasilkan semua 0-1 array panjang n.
Untuk masing-masing dari mereka, potong narray panjang boneka di sepanjang 1s, dan daftar panjang masing-masing bagian.
Urutkan panjangnya, dan hapus duplikat array dari hasilnya.

Rupanya, Luis Mendo punya ide yang sama juga.

Penjelasan kode:

[:~.i.<@\:~@(#;.1~"1 0)1,@{@;(<1 0)#~<:   Input is n.
                                     <:   n-1
                                   #~     copies of
                             (<1 0)       the boxed array [1 0].
                       1    ;             Prepend the boxed array [1].
                          {@              Catalog: produces all combinations of taking one
                                          item from each box, in a high-dimensional matrix.
                        ,@                Flatten the matrix. This results in a list of all
                                          boxed 0-1 arrays of length n that begin with a 1.
    i.                                    The array A =: 0, 1, ..., n-1.
            (     "1 0)                   For each of the boxed arrays B:
              ;.1~                          cut A along the occurrences of 1s in B,
             #                              take the length of each part,
        \:~@                                sort the lengths,
      <@                                    and put the result in a box.
[:~.                                      Remove duplicate boxes.

Zgarb
sumber

Sangat bagus menggunakan potongan ;.lagi.

mil

1

Brachylog , 33 byte (Tidak bersaing)

:1f:oad.
:1eI,.##lI,.:{.>0}a+?,.=

Ini tidak bersaing karena perbaikan bug.

Ini membutuhkan waktu sekitar 1 detik untuk 15di komputer saya. Untuk 20dan yang lebih besar, ini mogok dengan Out of global stackpengecualian.

Penjelasan

Ini tidak menggunakan partisi bawaan jenis apa pun, dan sebaliknya menggunakan fakta itu + bekerja dua arah melalui kendala propagasi.

Predikat utama:

:1f                       Find the list of all valid outputs of predicate 1
   :oa                    Sort each element of that list
      d.                  Output is that list of sorted lists minus all duplicates

Predikat 1:

:1eI                      I is an integer between Input and 1
    .##lI,                Output is a list of length I
          .:{.>0}a        Elements of Output are integers greater than 0
                  +?,     The sum of the elements of Output is Input
                     .=   Assign values to the elements of Output

Fatalisasi
sumber

1

Mathematica, 62 54 byte

Inner[#2~Table~#&,FrobeniusSolve[r=Range@#,#],r,Join]&

Partisi dari integer n dapat ditemukan dengan memecahkan untuk n -tupel bilangan bulat non-negatif ( c ₁ , c ₂ , ..., c _n ) sedemikian rupa sehingga c ₁ + 2 c ₂ + ... + n c _n = n . FrobeniusSolvemampu menemukan semua solusi untuk persamaan ini yang digunakan untuk membuat banyak salinan dari nilai masing-masing untuk menemukan semua partisi integer dari n .

mil
sumber

... dan bagaimana ini bukan built-in?

Leaky Nun

@ LeakyNun FrobeniusSolvetidak menemukan partisi bilangan bulat, ia menemukan semua solusi bilangan bulat non-negatif x1 ... xN untuk persamaan dari bentuk yang a1 x1 + a2 x2 + ... aN xN = bdiberikan a1 ... aNdan b.

mil

0

JavaScript (Firefox 30-57) 79 ES6, 65 byte

f=(n,m=1,a=[])=>n?m>n?[]:[...f(n-m,m,[...a,m]),...f(n,m+1,a)]:[a]

Port solusi Python @ xnor. (Seandainya saja aku memperhatikan bahwa kamu bisa berulang mjuga n...)

Neil
sumber

Hitung partisi N

Tes IO

Katalog

Jawaban:

Pyth, 10 9 byte

Pyth, 18 byte

MATL , 20 byte

Penjelasan

Haskell, 53 byte

J, 49 42 36 35 32 byte

Pemakaian

Penjelasan

Python, 65 byte

Javascript, 194 byte

Python 3.5, 82 72 byte

Haskell, 44 byte

Pyth, 17 byte

Jelly , 9 byte

Bagaimana itu bekerja

J, 39 byte

Penjelasan

Brachylog , 33 byte (Tidak bersaing)

Penjelasan

Mathematica, 62 54 byte

JavaScript (Firefox 30-57) 79 ES6, 65 byte