22

Ihre Herausforderung ist einfach: Gegeben eine ganze Zahl N , ouput jede Liste von positiven ganzen Zahlen , dass Summen N . Wenn die Eingabe beispielsweise 5 war, sollten Sie sie ausgeben

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

Diese Listen müssen weder in einer bestimmten Reihenfolge ausgegeben werden, noch müssen die Nummern in jeder Liste angegeben werden. Dies wäre beispielsweise auch eine akzeptable Ausgabe für '5':

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

Sie können davon ausgehen, dass die Eingabe eine positive Ganzzahl ist, und Sie können diese Zahl in jedem vernünftigen Format verwenden.

Sie können nicht alle eingebauten Funktionen , die dies tun.

Wenn Ihr Programm entweder fehlschlägt oder für großes N zu lange dauert, ist dies in Ordnung, aber Sie müssen mindestens die richtige Ausgabe für die ersten 15 erzeugen.

Es gelten Standardlücken und die kürzeste Antwort in Bytes gewinnt!

Testen Sie 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]]

Super großer Testfall: 15 sollten dies ausgeben

[[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

Das Stapel-Snippet am Ende dieses Beitrags generiert den Katalog aus den Antworten a) als Liste der kürzesten Lösungen pro Sprache und b) als Gesamt-Bestenliste.

Um sicherzustellen, dass Ihre Antwort angezeigt wird, beginnen Sie Ihre Antwort mit einer Überschrift. Verwenden Sie dazu die folgende Markdown-Vorlage:

## Language Name, N bytes

Wo Nist die Größe Ihres Beitrags? Wenn Sie Ihren Score zu verbessern, Sie können alte Rechnungen in der Überschrift halten, indem man sich durch das Anschlagen. Zum Beispiel:

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

Code-Snippet anzeigen

<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
quelle

1

Siehe auch

DJMcMayhem

2

Könnten Sie klarstellen, was Sie mit Handle meinen ?

Dennis

@flawr Ich bin anderer Meinung - das Finden aller Partitionen unterscheidet sich ausreichend vom Finden strenger Partitionen. Doch dies könnte ein Betrogene Ziel sein.

Mego

Ich denke, nach ungeordneten Partitionen zu suchen und die Anzahl der Teile nicht zu begrenzen, macht dies anders genug.

xnor

Können Sie klarstellen, was Sie mit buitin meinen ?

Undichte Nonne

6

Pyth, 10 9 Bytes

{SMlMM./U

Wir sind uns nicht sicher, ob dies kein Betrug ist, aber die Regeln besagen nur, dass keine Ganzzahlpartition verwendet werden kann (dies ist in der Frage selbst nicht klar angegeben, aber ein Kommentar von OP in der Frage besagt Ganzzahlpartition). Ich verwende eine ~~String-~~ Listen- Partition, die Slices der Liste erstellt, die sich zur "Mutter" -Liste verketten. Ich glaube, ich muss @Maltysen für die Idee danken, Listen anstelle von Strings zu verwenden.

n = 15 dauert auf meinem Computer weniger als eine Sekunde.

Im Datenfluss-Pseudocode:

              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

Probieren Sie es hier online aus.

busukxuan
quelle

{mSlMd./*Nspeichert ein Byte

Leaky Nun

Sie können für 7 Byte gehen, wenn Sie Listenpartitionierung

Maltysen

@LeakyNun Nun, ich habe es tatsächlich versucht und es hat kein Byte gespeichert. Als ich Ihren Kommentar dazu sah, fand ich heraus, dass meine Antwort tatsächlich 10 Bytes betrug, also habe ich tatsächlich falsch gezählt (vergessene gedit-Blöcke beginnen bei 1).

Busukxuan

@Maltysen Sie müssen jede Unterliste sortieren und dann deduplizieren.

Busukxuan

@Maltysen Du hattest Recht, Listen zu verwenden, verkürzt es. Ich habe versucht, sort und deduplicate zu dem Code hinzuzufügen, mit dem Sie verbunden sind, und es hat nicht geholfen, aber es ist alles dank Ihnen, dass ich die Idee hatte, * N durch U zu ersetzen. Danke!

Busukxuan

6

Pyth, 18 Bytes

L?b{SM+R-bsdsyMb]Y

Probieren Sie es online! (Mit dem yam Ende wird die Funktion aufgerufen)

Das geht ziemlich schnell.

Dies verwendet eine Rekursion. Wenn die Eingabe lautet b, generiert meine Methode die Partitionen von 0bis b-1und anschließend die richtigen Partitionen von jeder Partition.

Zum Beispiel, wenn b=4:

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

Dann auf jede Partition in b=0, append 4(um die Summe 4 zu machen); an jede Partition in b=1anhängen 3(um die Summe zu bilden 4); etc.

So funktioniert es hauptsächlich.

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 [[]].

Undichte Nonne
quelle

5

MATL , 20 Bytes

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

Probieren Sie es online!

Für die Eingabe 15benötigt der Online-Compiler ca. 2 Sekunden.

Erläuterung

Dies funktioniert , indem Partition zu erzeugen Punkte und dann auf Partition konvertieren Längen . Was ich damit meine, ist das Folgende. Bei Eingabe von N = 5 ist eine mögliche Partition [2 2 1]. Dies wird durch Teilungspunkte [0 2 4 5] dargestellt, so dass aufeinanderfolgende Differenzen auftreten (oder Längen) der Partitionspunkte die resultierende Partition der eingegebenen Nummer ergeben.

Alle Arrays von Trennstellen beginnen mit 0 und enden mit N . Die Anzahl k der Zwischenpunkte variiert von 0 bis N –1. Für N und k gegeben, können die Zwischenpunkte als eine Kombination der Zahlen [1, 2, ..., N -1] erzeugt werden, die k zu einem Zeitpunkt genommen werden.

Mehrere Arrays von Partitionspunkten können in unterschiedlicher Reihenfolge zum gleichen Ergebnis führen. Beispielsweise würden Partitionspunkte [0 1 3 5] die Partitionslängen [1 2 2] ergeben, dh die gleichen wie die vorherigen [2 2 1], nur in einer anderen Reihenfolge. Dies muss berücksichtigt werden, indem jedes Array von Partitionslängen sortiert und Duplikate entfernt werden .

:        % 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
quelle

1

Nizza, das Konzept der Trennpunkte ist eine sehr clevere Möglichkeit, dies zu lösen.

Nick

@Nick Danke! Und willkommen auf dieser Seite! :-)

Luis Mendo

5

Haskell, 53 Bytes

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

Anders Kaseorg
quelle

5

J, 49 42 36 35 32 Bytes

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

Es ist jetzt stillschweigend!

Erstellt die ganzzahlige Partition von n, indem die ganzzahligen Partitionen von 1 bis n erstellt werden . Berechnet das Ergebnis für n = 15 in einer Millisekunde.

Erstellen Sie ausgehend von der anfänglichen ganzzahligen Partition, [[1]]die n = 1 entspricht, die nächste ganzzahlige Partition, indem Sie die Ergebnisse aus zwei Operationen zusammenfassen: Fügen Sie an jede Partition eine 1 an; Inkrementieren des kleinsten Werts in jeder Partition um 1. Natürlich werden doppelte Partitionen entfernt. Um die ganzzahlige Partition n = 2 und weiter zu erhalten,

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

Verwendung

   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

Erläuterung

Da J keine unregelmäßigen Arrays unterstützt, muss jede Partition in ein Kästchen gesetzt werden, damit sie nicht mit Nullen aufgefüllt werden, wenn sie an andere Partitionen angehängt werden.

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

Meilen
quelle

4

Python, 65 Bytes

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)]

Diese Funktion sammelt eine Partition und druckt die Ausgaben, wobei nach Auswahl verzweigt wird. Es entscheidet, wie viele Einsen in die Partition eingefügt werden, wie viele Zweisen und so weiter. Für jeden Wert iist es entweder

Fügt einen Teil der Größe hinzu iund verringert sich nauf n-ioder
Geht weiter zu i+1

Wenn i>ndann keine Teile mehr hergestellt werden können, so hört es auf. Wenn dies der nFall ist, 0ist die Partition erfolgreich und wird gedruckt.

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:]

Eine rekursive Methode, die eine Liste von Partitionen ausgibt. Wie beim Python 3-Code wird die Teilegröße hochgezählt iund bei jedem Schritt entschieden, ob ein weiterer Teil der Größe hinzugefügt ioder gestoppt werden soll.

Beides geschieht n=15fast augenblicklich.

xnor
quelle

3

Javascript, 194 Bytes

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);

Nicht minimiert

Das Finden von Unikaten durch Sortieren und Vergleichen mit einer Zeichenfolge ist ein ziemlicher Hack, spart jedoch wahrscheinlich Platz.

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
quelle

4

Quite a hack but saves spaceGenau darum geht es auf dieser Website. : D

DJMcMayhem

2

Python 3.5, 82 72 Bytes

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

Gibt eine Menge von Tupeln zurück. n = 15 endet sofort.

Testen Sie es auf repl.it .

Dennis
quelle

2

Haskell, 44 Bytes

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

Die Hilfsfunktion n%mteilt die Partitionen nin Teile auf ≥m, wobei die Hauptfunktion verwendet wird m=1. Es verzweigt sich von jedem ersten Eintrag jmit m≤j≤n, wobei auf der verbleibenden Partition n-jmindestens in Teile zerlegt wird j. Der Basisfall n==0gibt nur die leere Partition an.

xnor
quelle

1

Pyth, 17 Bytes

L|{SMs+LVrb0yMb]Y

Definiert eine Funktion mit dem Namen y. Probieren Sie es online aus .

Anders Kaseorg
quelle

1

Gelee , 9 Bytes

b1ŒṖḅ1Ṣ€Q

Probieren Sie es online!

Wie es funktioniert

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
quelle

1

J, 39 Bytes

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

Dies ist ein monadisches Verb, das eine Ganzzahl annimmt und ein Array von Boxed Arrays zurückgibt. Probieren Sie es hier aus. Verwendung:

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

Bei Eingabe 15 läuft es auf meinem Computer etwa eine Sekunde lang.

Erläuterung

Diese Herausforderung sah sofort wie ein Job für Catalog ( {) und Cut ( ;.) aus. Der Umriss des Algorithmus lautet:

Produziere alle 0-1 Arrays der Länge n.
Schneiden Sie für jeden von ihnen einen Dummyn entlang der Einsen aus und listen Sie die Längen jedes Teils auf.
Sortieren Sie die Längen und entfernen Sie doppelte Arrays aus dem Ergebnis.

Luis Mendo hatte anscheinend die gleiche Idee .

Erklärung des Codes:

[:~.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
quelle

Sehr schöne Verwendung von ;.wieder geschnitten .

Meilen

1

Brachylog , 33 Bytes (nicht konkurrierend)

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

Dies ist aufgrund einer Fehlerbehebung nicht konkurrierend.

Dies dauert 15auf meinem Computer ca. 1 Sekunde . Für 20und größer stürzt dies mit einer Out of global stackAusnahme ab.

Erläuterung

Hierbei wird keine integrierte Partitionierung verwendet. Stattdessen wird die Tatsache verwendet, dass +die Weitergabe von Einschränkungen in beide Richtungen funktioniert.

Hauptprädikat:

: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

Prädikat 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

Tödlich
quelle

1

Mathematica, 62 54 Bytes

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

Die Partitionen einer ganzen Zahl n können gefunden werden, indem nach n- Tupeln nicht negativer ganzer Zahlen ( c ₁ , c ₂ , ..., c _n ) so aufgelöst wird, dass c ₁ + 2 c ₂ + ... + n c _n = n . FrobeniusSolveist in der Lage, alle Lösungen für diese Gleichung zu finden, die verwendet werden, um so viele Kopien ihrer jeweiligen Werte zu erstellen, um alle ganzzahligen Partitionen von n zu finden .

Meilen
quelle

... und wie ist das nicht ein eingebautes?

Undichte Nonne

@LeakyNun FrobeniusSolvefindet keine ganzzahligen Teilungen, es findet alle Lösungen von nicht-negativen ganzen Zahlen x1 ... xN zu Gleichungen der Form a1 x1 + a2 x2 + ... aN xN = bgegeben a1 ... aNund b.

Meilen

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 von @ xnors Python-Lösung. (Wenn ich nur bemerkt hätte, dass man sich genauso mgut wiederkehren könnte wie n...)

Neil
quelle

Berechnen Sie die Partitionen von N

Testen Sie IO

Katalog

Antworten:

Pyth, 10 9 Bytes

Pyth, 18 Bytes

MATL , 20 Bytes

Erläuterung

Haskell, 53 Bytes

J, 49 42 36 35 32 Bytes

Verwendung

Erläuterung

Python, 65 Bytes

Javascript, 194 Bytes

Python 3.5, 82 72 Bytes

Haskell, 44 Bytes

Pyth, 17 Bytes

Gelee , 9 Bytes

Wie es funktioniert

J, 39 Bytes

Erläuterung

Brachylog , 33 Bytes (nicht konkurrierend)

Erläuterung

Mathematica, 62 54 Bytes

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