Angenommen, wir haben n Bins, in denen wir k Bälle werfen. Was ist ein Fast (d. H. Mit numpy / scipy anstelle von Python-Code), um alle möglichen Ergebnisse als Matrix zu generieren?
Zum Beispiel, wenn n = 4 und k = 3 , möchten wir das folgende numpy.array :
Entschuldigung, wenn eine Vertauschung verpasst wurde, aber das ist die allgemeine Idee. Die generierten Permutationen müssen nicht in einer bestimmten Reihenfolge sein, aber die obige Liste war praktisch, um sie kategorisch mental zu durchlaufen.
Besser noch, gibt es eine Möglichkeit, jede ganze Zahl von 1 auf die Multiset-Nummer abzubilden (die Kardinalität dieser Liste) direkt zu einer gegebenen Permutation?
Diese Frage bezieht sich auf die folgenden, die in R mit sehr unterschiedlichen Möglichkeiten implementiert sind:
Auch verwandte Referenzen:
Hier ist eine Generator-Lösung mit itertools.combinations_with_replacement , weiß nicht, ob es für Ihre Bedürfnisse geeignet ist.
Die Komplexität dieser Funktion wächst exponentiell, so dass es eine diskrete Grenze zwischen dem, was machbar ist und was nicht, gibt.
Beachten Sie, dass nummerische Arrays zwar ihre Größe bei der Konstruktion kennen müssen, dies jedoch leicht möglich ist, da die Multiset-Nummer leicht gefunden werden kann. Unter könnte eine bessere Methode sein, habe ich keine Zeitpunkte gemacht.
%Vor%Zu Referenzzwecken verwendet der folgende Code Ehrlichs Algorithmus , um alle möglichen Kombinationen eines Multisets in C ++, Javascript zu durchlaufen und Python:
Dies kann mit dieser Methode in das obige Format konvertiert werden. Insbesondere
%Vor% Dies ist immer noch nicht rein numpy, aber kann verwendet werden, um eine vorbelegte numpy.array ziemlich schnell zu füllen.
Hier ist die Lösung, die ich dafür gefunden habe.
%Vor%Hinweis 1: Das [:: - 1] am Ende kehrt nur die Reihenfolge um, damit sie mit Ihrer Beispielausgabe übereinstimmt.
Hinweis 2: Das Auffinden dieser Sequenzen ist äquivalent dazu, alle Möglichkeiten zu finden, n Sterne und k-1 Balken in (um n + k-1 Punkte zu füllen) anzuordnen (siehe Sterne und Bars thm 2 ).
Hinweis 3: Das Argument max_power gibt Ihnen die Option, nur Sequenzen zurückzugeben, bei denen alle ganzen Zahlen kleiner als max.
sindTags und Links python permutation combinatorics numpy scipy
