Gibt es eine effiziente Möglichkeit, eine zufällige Kombination von N ganzen Zahlen zu generieren, so dass:
- jede ganze Zahl liegt im Intervall [
min
,max
], - Die ganzen Zahlen haben eine Summe von
sum
, - Die Ganzzahlen können in beliebiger Reihenfolge (z. B. in zufälliger Reihenfolge) und angezeigt werden
- Die Kombination wird gleichmäßig zufällig aus allen Kombinationen ausgewählt, die die anderen Anforderungen erfüllen.
Gibt es einen ähnlichen Algorithmus für zufällige Kombinationen, bei dem die Ganzzahlen in sortierter Reihenfolge nach ihren Werten (und nicht in beliebiger Reihenfolge) angezeigt werden müssen?
(Die Auswahl einer geeigneten Kombination mit einem Mittelwert von mean
ist ein Sonderfall, wenn sum = N * mean
. Dieses Problem entspricht der Erzeugung einer einheitlichen zufälligen Aufteilung sum
in N Teile, die sich jeweils im Intervall [ min
, max
] befinden und in beliebiger Reihenfolge oder in sortierter Reihenfolge nach ihrer Anzahl angezeigt werden Werte, je nach Fall.)
Mir ist bekannt, dass dieses Problem für Kombinationen, die in zufälliger Reihenfolge erscheinen, folgendermaßen gelöst werden kann (EDIT [27. April]: Algorithmus geändert.):
Wenn
N * max < sum
oderN * min > sum
, gibt es keine Lösung.Wenn ja
N * max == sum
, gibt es nur eine Lösung, bei der alleN
Zahlen gleich sindmax
. Wenn jaN * min == sum
, gibt es nur eine Lösung, bei der alleN
Zahlen gleich sindmin
.Verwenden Sie den in Smith und Tromble angegebenen Algorithmus ("Sampling from the Unit Simplex", 2004), um N zufällige nicht negative Ganzzahlen mit der Summe zu generieren
sum - N * min
.Fügen Sie
min
zu jeder auf diese Weise generierten Zahl hinzu.Wenn eine Zahl größer als ist
max
, fahren Sie mit Schritt 3 fort.
Dieser Algorithmus ist jedoch langsam, wenn er max
viel kleiner als ist sum
. Zum Beispiel mean
lehnt der Algorithmus nach meinen Tests (mit einer Implementierung des oben genannten Sonderfalls ) im Durchschnitt ab -
- etwa 1,6 Proben wenn
N = 7, min = 3, max = 10, sum = 42
, aber - ca. 30,6 Proben wenn
N = 20, min = 3, max = 10, sum = 120
.
Gibt es eine Möglichkeit, diesen Algorithmus so zu ändern, dass er für große N effizient ist und gleichzeitig die oben genannten Anforderungen erfüllt?
BEARBEITEN:
Als Alternative, die in den Kommentaren vorgeschlagen wird, ist eine effiziente Methode zur Erstellung einer gültigen Zufallskombination (die alle bis auf die letzte Anforderung erfüllt):
- Berechnen Sie
X
die Anzahl der gültigen Kombinationen möglich gegebenensum
,min
undmax
. - Wählen Sie
Y
eine einheitliche zufällige Ganzzahl in[0, X)
. - Konvertieren ("unrank")
Y
in eine gültige Kombination.
Gibt es jedoch eine Formel zur Berechnung der Anzahl gültiger Kombinationen (oder Permutationen) und gibt es eine Möglichkeit, eine Ganzzahl in eine gültige Kombination umzuwandeln? [EDIT (28. April): Gleiches gilt für Permutationen und nicht für Kombinationen].
EDIT (27. April):
Nachdem ich Devroyes Non-Uniform Random Variate Generation (1986) gelesen habe , kann ich bestätigen, dass dies ein Problem beim Generieren einer zufälligen Partition ist. Auch Übung 2 (insbesondere Teil E) auf Seite 661 ist für diese Frage relevant.
EDIT (28. April):
Wie sich herausstellte, ist der von mir angegebene Algorithmus einheitlich, wobei die beteiligten Ganzzahlen in zufälliger Reihenfolge angegeben werden , im Gegensatz zur sortierten Reihenfolge nach ihren Werten . Da beide Probleme von allgemeinem Interesse sind, habe ich diese Frage geändert, um eine kanonische Antwort auf beide Probleme zu finden.
Der folgende Ruby-Code kann verwendet werden, um mögliche Lösungen für die Einheitlichkeit zu überprüfen (wo algorithm(...)
ist der Kandidatenalgorithmus):
combos={}
permus={}
mn=0
mx=6
sum=12
for x in mn..mx
for y in mn..mx
for z in mn..mx
if x+y+z==sum
permus[[x,y,z]]=0
end
if x+y+z==sum and x<=y and y<=z
combos[[x,y,z]]=0
end
end
end
end
3000.times {|x|
f=algorithm(3,sum,mn,mx)
combos[f.sort]+=1
permus[f]+=1
}
p combos
p permus
BEARBEITEN (29. April): Ruby-Code der aktuellen Implementierung wurde erneut hinzugefügt.
Das folgende Codebeispiel ist in Ruby angegeben, aber meine Frage ist unabhängig von der Programmiersprache:
def posintwithsum(n, total)
raise if n <= 0 or total <=0
ls = [0]
ret = []
while ls.length < n
c = 1+rand(total-1)
found = false
for j in 1...ls.length
if ls[j] == c
found = true
break
end
end
if found == false;ls.push(c);end
end
ls.sort!
ls.push(total)
for i in 1...ls.length
ret.push(ls[i] - ls[i - 1])
end
return ret
end
def integersWithSum(n, total)
raise if n <= 0 or total <=0
ret = posintwithsum(n, total + n)
for i in 0...ret.length
ret[i] = ret[i] - 1
end
return ret
end
# Generate 100 valid samples
mn=3
mx=10
sum=42
n=7
100.times {
while true
pp=integersWithSum(n,sum-n*mn).map{|x| x+mn }
if !pp.find{|x| x>mx }
p pp; break # Output the sample and break
end
end
}
quelle
sum
undN
praktisch unbegrenzt (im Rahmen der Vernunft). Ich suche eine kanonische Antwort, weil das zugrunde liegende Problem in vielen Fragen zum Stapelüberlauf auftaucht, einschließlich dieser und dieser . @ גלעדברקןAntworten:
Hier ist meine Lösung in Java. Es ist voll funktionsfähig und enthält zwei Generatoren:
PermutationPartitionGenerator
für unsortierte Partitionen undCombinationPartitionGenerator
für sortierte Partitionen. Ihr Generator istSmithTromblePartitionGenerator
zum Vergleich auch in der Klasse implementiert . Die KlasseSequentialEnumerator
listet alle möglichen Partitionen (je nach Parameter unsortiert oder sortiert) in sequentieller Reihenfolge auf. Ich habe für alle diese Generatoren gründliche Tests (einschließlich Ihrer Testfälle) hinzugefügt. Die Implementierung ist größtenteils selbsterklärend. Wenn Sie Fragen haben, werde ich diese in ein paar Tagen beantworten.Sie können dies auf Ideone versuchen .
quelle
Hier ist der Algorithmus von John McClanes PermutationPartitionGenerator in einer anderen Antwort auf dieser Seite. Es hat zwei Phasen, nämlich eine Einrichtungsphase und eine Abtastphase, und generiert
n
Zufallszahlen in [min
,max
] mit der Summesum
, wobei die Zahlen in zufälliger Reihenfolge aufgelistet sind.Einrichtungsphase: Zunächst wird eine Lösungstabelle mit den folgenden Formeln erstellt (
t(y, x)
wobeiy
in [0,n
] undx
in [0,sum - n * min
] steht):Hier speichert t (y, x) die relative Wahrscheinlichkeit, dass die Summe der
y
Zahlen (im entsprechenden Bereich) gleich istx
. Diese Wahrscheinlichkeit ist relativ zu allen t (y, x) mit derselbeny
.Abtastphase: Hier erzeugen wir eine Stichprobe von
n
Zahlen. Stellen Sies
aufsum - n * min
, dann für jede Positioni
, beginnend mitn - 1
und arbeitet nach hinten zum 0:v
[0, t (i + 1, s)) auf eine zufällige Ganzzahl setzen.r
zumin
.v
.v
0 oder größer bleibt, subtrahieren Sie t (i, s-1) vonv
, addieren Sie 1 zur
und subtrahieren Sie 1 vons
.i
in der Probe ist auf eingestelltr
.BEARBEITEN:
Es scheint, dass es bei geringfügigen Änderungen des obigen Algorithmus möglich ist, dass jede Zufallszahl einen separaten Bereich verwendet, anstatt für alle denselben Bereich zu verwenden:
Jede Zufallszahl an den Positionen
i
∈ [0,n
) hat einen Minimalwert min (i) und einen Maximalwert max (i).Sei
adjsum
=sum
- Σmin (i).Einrichtungsphase: Zunächst wird eine Lösungstabelle mit den folgenden Formeln erstellt (
t(y, x)
wobeiy
in [0,n
] undx
in [0,adjsum
] steht):Die Abtastphase ist dann genau die gleiche wie zuvor, außer dass wir
s
aufadjsum
(anstattsum - n * min
) undr
auf min (i) (anstattmin
) setzen.BEARBEITEN:
Für John McClanes CombinationPartitionGenerator sind die Setup- und Sampling-Phasen wie folgt.
Einrichtungsphase: Zuerst wird eine Lösungstabelle mit den folgenden Formeln erstellt (
t(z, y, x)
wobeiz
in [0,n
],y
in [0,max - min
] undx
in [0,sum - n * min
]):Abtastphase: Hier erzeugen wir eine Stichprobe von
n
Zahlen. Stellen Sies
aufsum - n * min
undmrange
aufmax - min
, dann für jede Positioni
, beginnend mitn - 1
und rückwärts bis 0:v
[0, t (i + 1, mrange, s)) auf eine zufällige ganze Zahl setzen.mrange
min (mrange
,s
) setzenmrange
vons
.r
zumin + mrange
.i
,mrange
,s
) ausv
.v
Reste 0 oder größer, 1 hinzufügens
subtrahieren 1 ausr
und von 1mrange
, dann Subtrahieren - t (i
,mrange
,s
) ausv
.i
in der Probe ist auf eingestelltr
.quelle
Ich habe dies nicht getestet, daher ist es keine wirkliche Antwort, sondern nur etwas zum Ausprobieren, das zu lang ist, um in einen Kommentar zu passen. Beginnen Sie mit einem Array, das die ersten beiden Kriterien erfüllt, und spielen Sie damit, damit es immer noch die ersten beiden Kriterien erfüllt, aber viel zufälliger ist.
Wenn der Mittelwert eine Ganzzahl ist, kann Ihr anfängliches Array [4, 4, 4, ... 4] oder vielleicht [3, 4, 5, 3, 4, 5, ... 5, 8, 0] oder sein so etwas einfaches. Versuchen Sie für einen Mittelwert von 4,5 [4, 5, 4, 5, ... 4, 5].
Wählen Sie als Nächstes ein Zahlenpaar
num1
undnum2
im Array aus. Wahrscheinlich sollte die erste Nummer in der richtigen Reihenfolge genommen werden, da beim Fisher-Yates-Shuffle die zweite Nummer zufällig ausgewählt werden sollte. Wenn Sie die erste Nummer der Reihe nach nehmen, wird sichergestellt, dass jede Nummer mindestens einmal ausgewählt wird.Berechnen Sie nun
max-num1
undnum2-min
. Das sind die Abstände zwischen den beiden Zahlenmax
und denmin
Grenzen. Stellen Sielimit
den kleineren der beiden Abstände ein. Dies ist die maximal zulässige Änderung, bei der die eine oder andere Zahl nicht außerhalb der zulässigen Grenzen liegt. Wennlimit
Null ist, überspringen Sie dieses Paar.Wählen Sie eine zufällige Ganzzahl im Bereich [1,
limit
]: Rufen Sie sie aufchange
. Ich lasse 0 aus dem auswählbaren Bereich weg, da dies keine Auswirkung hat. Tests können zeigen, dass Sie eine bessere Zufälligkeit erhalten, wenn Sie sie einbeziehen. Ich bin mir nicht sicher.Jetzt setzen
num1 <- num1 + change
undnum2 <- num2 - change
. Dies hat keinen Einfluss auf den Mittelwert und alle Elemente des Arrays befinden sich noch innerhalb der erforderlichen Grenzen.Sie müssen das gesamte Array mindestens einmal durchlaufen. Tests sollten zeigen, ob Sie es mehr als einmal durchlaufen müssen, um etwas ausreichend Zufälliges zu erhalten.
ETA: Pseudocode einschließen
quelle
Wie das OP hervorhebt, ist die Fähigkeit, effizient zu ranken, sehr mächtig. Wenn wir dazu in der Lage sind, kann die Erzeugung einer gleichmäßigen Verteilung der Partitionen in drei Schritten erfolgen (wobei erneut dargelegt wird, was das OP in der Frage dargelegt hat):
sum
so, dass die Teile im Bereich [min
,max
] liegen.[1, M]
.Im Folgenden konzentrieren wir uns nur auf die Generierung der n- ten Partition, da es eine Vielzahl von Informationen zum Generieren einer gleichmäßigen Verteilung von Ganzzahlen in einem bestimmten Bereich gibt. Hier ist ein einfacher
C++
Algorithmus ohne Rangfolge, der leicht in andere Sprachen zu übersetzen sein sollte.Die Arbeitspferdfunktion
pCount
ist gegeben durch:Diese Funktion basiert auf der hervorragenden Antwort auf Gibt es einen effizienten Algorithmus für die Ganzzahlpartitionierung mit begrenzter Anzahl von Teilen? vom Benutzer @ m69_snarky_and_unwelcoming. Der oben angegebene ist eine geringfügige Modifikation des einfachen Algorithmus (der ohne Memoisierung). Dies kann leicht modifiziert werden, um Memoisierung für mehr Effizienz einzubeziehen. Wir werden dies vorerst weglassen und uns auf den unranking Teil konzentrieren.
Erklärung von
unRank
Wir stellen zunächst fest, dass es eine Eins-zu-Eins-Zuordnung von den Partitionen der Länge N der Nummer gibt,
sum
so dass die Teile im Bereich [min
,max
] liegen, zu den eingeschränkten Partitionen der Länge N der Nummersum - m * (min - 1)
mit Teilen in [1
,max - (min - 1)
].Als kleines Beispiel betrachten wir die Partitionen von
50
der Länge ,4
so dass dasmin = 10
und dasmax = 15
. Dies hat die gleiche Struktur wie die eingeschränkten Partitionen50 - 4 * (10 - 1) = 14
der Länge,4
wobei der maximale Teil gleich ist15 - (10 - 1) = 6
.In diesem Sinne könnten wir, um leicht zählen zu können, einen Schritt 1a hinzufügen, um das Problem in den Fall "Einheit" zu übersetzen, wenn Sie so wollen.
Jetzt haben wir einfach ein Zählproblem. Wie @ m69 brillant anzeigt, kann das Zählen von Partitionen leicht erreicht werden, indem das Problem in kleinere Probleme aufgeteilt wird. Die Funktion @ m69 bietet uns 90% des Weges. Wir müssen nur herausfinden, was mit der zusätzlichen Einschränkung zu tun ist, dass es eine Obergrenze gibt. Hier bekommen wir:
Wir müssen auch bedenken, dass dies im
myMax
Laufe der Zeit abnehmen wird. Dies macht Sinn , wenn wir uns die aussehen 6 th Partition oben:Um die Anzahl der Partitionen von hier an zu zählen, müssen wir die Übersetzung weiterhin auf den Fall "Einheit" anwenden. Das sieht so aus:
Wo wir wie vorher ein Maximum hatten
6
, betrachten wir jetzt nur noch ein Maximum von5
.In diesem Sinne unterscheidet sich das Aufheben der Rangfolge der Partition nicht vom Auflisten einer Standardpermutation oder -kombination. Wir müssen in der Lage sein, die Anzahl der Partitionen in einem bestimmten Abschnitt zu zählen. Um beispielsweise die Anzahl der Partitionen zu zählen, die
10
oben beginnen, entfernen wir lediglich die10
in der ersten Spalte:Übersetzen Sie in den Einheitsfall:
und rufen Sie an
pCount
:Bei einer zufälligen Ganzzahl bis zum Unrank berechnen wir die Anzahl der Partitionen in immer kleineren Abschnitten (wie oben beschrieben) weiter, bis wir unseren Indexvektor gefüllt haben.
Beispiele
In Anbetracht
min = 3
,max = 10
,n = 7
, undsum = 42
, hier ist eine ideone Demo , die 20 zufällige Partitionen erzeugt.quelle