Ich versuche meinem Sohn zu zeigen, wie Codierung verwendet werden kann, um ein von einem Spiel aufgeworfenes Problem zu lösen, und wie R mit Big Data umgeht. Das fragliche Spiel heißt "Lucky 26". In diesem Spiel werden Zahlen (1-12 ohne Duplikate) auf 12 Punkten auf einem Davidstern (6 Scheitelpunkte, 6 Schnittpunkte) positioniert und die 6 Linien mit 4 Zahlen müssen alle zu 26 addieren. Von den ungefähr 479 Millionen Möglichkeiten (12P12) ) Es gibt anscheinend 144 Lösungen. Ich habe versucht, dies in R wie folgt zu codieren, aber der Speicher scheint ein Problem zu sein. Ich würde mich über jeden Rat sehr freuen, die Antwort voranzutreiben, wenn die Mitglieder Zeit haben. Vielen Dank an die Mitglieder im Voraus.
library(gtools)
x=c()
elements <- 12
for (i in 1:elements)
{
x[i]<-i
}
soln=c()
y<-permutations(n=elements,r=elements,v=x)
j<-nrow(y)
for (i in 1:j)
{
L1 <- y[i,1] + y[i,3] + y[i,6] + y[i,8]
L2 <- y[i,1] + y[i,4] + y[i,7] + y[i,11]
L3 <- y[i,8] + y[i,9] + y[i,10] + y[i,11]
L4 <- y[i,2] + y[i,3] + y[i,4] + y[i,5]
L5 <- y[i,2] + y[i,6] + y[i,9] + y[i,12]
L6 <- y[i,5] + y[i,7] + y[i,10] + y[i,12]
soln[i] <- (L1 == 26)&(L2 == 26)&(L3 == 26)&(L4 == 26)&(L5 == 26)&(L6 == 26)
}
z<-which(soln)
z
r
bigdata
permutation
DesertProject
quelle
quelle
x<- 1:elements
und was noch wichtiger istL1 <- y[,1] + y[,3] + y[,6] + y[,8]
. Dies würde Ihrem Speicherproblem nicht wirklich helfen, so dass Sie immer in rcpprm(list=ls())
Ihre MRE ein. Wenn jemand in eine aktive Sitzung kopiert, kann er seine eigenen Daten verlieren.Antworten:
Hier ist ein anderer Ansatz. Es basiert auf einem MathWorks-Blogbeitrag von Cleve Moler , dem Autor des ersten MATLAB.
Um Speicherplatz zu sparen, permutiert der Autor im Blog-Beitrag nur 10 Elemente, wobei das erste Element als Apex-Element und das 7. als Basiselement beibehalten werden. Daher müssen nur
10! == 3628800
Permutationen getestet werden.Im folgenden Code
1
zu10
. Es gibt insgesamt10! == 3628800
von ihnen.11
als Apex-Element und halten Sie es fest. Es ist wirklich egal, wo die Aufgaben beginnen, die anderen Elemente befinden sich an den richtigen relativen Positionen.for
Schleife der 2. Position, 3. Position usw. zu .Dies sollte die meisten Lösungen erzeugen, Rotationen und Reflexionen geben oder nehmen. Es garantiert jedoch nicht, dass die Lösungen einzigartig sind. Es ist auch ziemlich schnell.
quelle
Es gibt tatsächlich 960 Lösungen. Im Folgenden verwenden wir
Rcpp
,RcppAlgos
* und dasparallel
Paket, um die Lösung in etwas mehr als6 seconds
4 Kernen zu erhalten. Selbst wenn Sie sich für einen Single-Threaded-Ansatz mit Basis-Rs entscheidenlapply
, wird die Lösung in etwa 25 Sekunden zurückgegeben.Zunächst schreiben wir einen einfachen Algorithmus
C++
, der eine bestimmte Permutation überprüft. Sie werden feststellen, dass wir ein Array verwenden, um alle sechs Zeilen zu speichern. Dies dient der Leistung, da wir den Cache-Speicher effektiver nutzen als 6 einzelne Arrays. Sie müssen auch berücksichtigen, dass eineC++
auf Null basierende Indizierung verwendet wird.Nun wird die Verwendung
lower
undupper
in ArgumentepermuteGeneral
können wir Stücke von Permutationen erzeugen und diese einzeln testen Speicher in Schach zu halten. Im Folgenden habe ich beschlossen, ungefähr 4,7 Millionen Permutationen gleichzeitig zu testen. Die Ausgabe gibt die lexikografischen Indizes der Permutationen von 12 an! so dass die Lucky 26-Bedingung erfüllt ist.Jetzt überprüfen wir die Verwendung
permuteSample
und das ArgumentsampleVec
, mit dem Sie bestimmte Permutationen generieren können (z. B. wenn Sie 1 übergeben, erhalten Sie die erste Permutation (dh1:12
)).Schließlich verifizieren wir unsere Lösung mit Basis R
rowSums
:* Ich bin der Autor von
RcppAlgos
quelle
Für Permutationen ist rcppalgos großartig. Leider gibt es 479 Millionen Möglichkeiten mit 12 Feldern, was bedeutet, dass die meisten Menschen zu viel Speicherplatz beanspruchen:
Es gibt einige Alternativen.
Nehmen Sie eine Probe der Permutationen. Das heißt, nur 1 Million statt 479 Millionen. Dazu können Sie verwenden
permuteSample(12, 12, n = 1e6)
. Siehe @ JosephWoods Antwort für einen etwas ähnlichen Ansatz, außer dass er 479 Millionen Permutationen abtastet;)Erstellen Sie eine Schleife in rcpp , um die Permutation bei der Erstellung auszuwerten. Dies spart Speicher, da Sie am Ende die Funktion erstellen würden, um nur die richtigen Ergebnisse zurückzugeben.
Gehen Sie das Problem mit einem anderen Algorithmus an. Ich werde mich auf diese Option konzentrieren.
Neuer Algorithmus mit Einschränkungen
Segmente sollten 26 sein
Wir wissen, dass jedes Liniensegment im obigen Stern bis zu 26 addieren muss. Wir können diese Einschränkung zur Erzeugung unserer Permutationen hinzufügen - geben Sie nur Kombinationen an, die bis zu 26 addieren:
ABCD und EFGH Gruppen
Im obigen Stern habe ich drei Gruppen unterschiedlich gefärbt: ABCD , EFGH und IJLK . Die ersten beiden Gruppen haben ebenfalls keine gemeinsamen Punkte und sind auch auf interessierenden Liniensegmenten. Daher können wir eine weitere Einschränkung hinzufügen: Für Kombinationen, die sich zu 26 addieren, müssen wir sicherstellen, dass ABCD und EFGH keine Zahlenüberlappung aufweisen. IJLK werden die restlichen 4 Nummern zugewiesen.
Permute durch die Gruppen
Wir müssen alle Permutationen jeder Gruppe finden. Das heißt, wir haben nur Kombinationen, die sich zu 26 addieren. Zum Beispiel müssen wir nehmen
1, 2, 11, 12
und machen1, 2, 12, 11; 1, 12, 2, 11; ...
.Endgültige Berechnungen
Der letzte Schritt ist die Mathematik. Ich benutze
lapply()
undReduce()
hier, um mehr funktionale Programmierung zu machen - sonst würde viel Code sechsmal eingegeben. In der ursprünglichen Lösung finden Sie eine ausführlichere Erläuterung des mathematischen Codes.Swapping ABCD und EFGH
Am Ende des obigen Codes habe ich den Vorteil genutzt, dass wir tauschen
ABCD
undEFGH
die verbleibenden Permutationen erhalten können. Hier ist der Code, um zu bestätigen, dass wir die beiden Gruppen austauschen und korrekt sein können:Performance
Am Ende haben wir nur 1,3 Millionen der 479 Permutationen ausgewertet und nur 550 MB RAM gemischt. Die Ausführung dauert ca. 0,7 Sekunden
quelle
Hier ist die Lösung für den kleinen Kerl:
quelle