Hier habe ich ganze Zahlen 1:7
für vier verschiedene Partitionen, dh {1}, {2,3,4}, {5,6} und {7}, und diese Partitionen werden in eine Liste geschrieben, dh , list(1,c(2,3,4),c(5,6),7)
. Ich behandle die Partitionen als Mengen, so dass unterschiedliche Permutationen von Elementen innerhalb einer Partition als dieselbe erkannt werden sollten. Zum Beispiel list(1,c(2,3,4),c(5,6),7)
und list(7,1,c(2,3,4),c(6,5))
sind gleichwertig.
Beachten Sie, dass Elemente in der Liste nicht wiederholt werden , z. B. nein list(c(1,2),c(2,1),c(1,2))
, da bei diesem Problem exklusive Partitionen über den gesamten Satz diskutiert werden.
Ich habe einige der verschiedenen Permutationen lst
wie folgt in die Liste aufgenommen
lst <- list(list(1,c(2,3,4),c(5,6),7),
list(c(2,3,4),1,7,c(5,6)),
list(1,c(2,3,4),7,c(6,5)),
list(7,1,c(3,2,4),c(5,6)))
und was ich tun möchte, ist zu überprüfen, ob alle Permutationen gleichwertig sind. Wenn ja, dann erhalten wir Ergebnis TRUE
.
Was ich bisher getan haben , ist die Elemente innerhalb jeder Partition zu sortieren, und verwendet setdiff()
mit interset()
und union()
es zu beurteilen (siehe meinen Code unten)
s <- Map(function(v) Map(sort,v),lst)
equivalent <- length(setdiff(Reduce(union,s),Reduce(intersect,s),))==0
Ich denke jedoch, dass diese Methode langsam ist, wenn die Partitionsgröße vergrößert wird. Gibt es einen schnelleren Ansatz, um es zu schaffen? Im Voraus geschätzt!
- einige Testfälle (kleine Daten)
# should return `TRUE`
lst1 <- list(list(1,c(2,3,4),c(5,6)),
list(c(2,3,4),1,c(5,6)),
list(1,c(2,3,4),c(6,5)))
# should return `TRUE`
lst2 <- list(list(1:2, 3:4), list(3:4, 1:2))
# should return `FALSE`
lst3 <- list(list(1,c(2,3,4),c(5,6)), list(c(2,3,4),1,c(5,6)), list(1,c(2,3,5),c(6,4)))
quelle
Map
Anrufe vermeidenlst_equal = list(list(1:2, 3:4), list(3:4, 1:2))
und einen, bei dem das ErgebnisFALSE
vielleicht sein solltelst_false <- list(list(1,c(2,3,4),c(5,6)), list(c(2,3,4),1,c(5,6)), list(1,c(2,3,5),c(6,4)))
FALSE
. Auf diese Weise ist es einfach zu diagnostizieren, warum eine Antwort auf einige, aber nicht alle Testfälle funktioniert. Wenn es nur ein einziges Beispiel gibt, verlieren Sie Nuancen in den Testergebnissen. Es ist auch schön, neue Beispiele hinzuzufügen, anstatt vorhandene Beispiele unter Personen zu ändern, die bereits daran gearbeitet haben.lst
möglicherweise lang ist, können Sie mit anderen Ansätzen an Effizienz gewinnen. ZB eine erste Überprüfung,length(unique(lengths(lst))) == 1
die sehr schnell zurückkehren würde,FALSE
wenn eine der inneren Listen die falsche Anzahl von Elementen enthält ...lst
, vergleichenlst[[i]]
zulst[[1]]
, und auf diese Weise können Sie so schnell stoppen , wie Sie eine fehlende Übereinstimmung finden, anstatt alle Vergleiche zu tun. Wennlst
es lang ist undFALSE
s üblich sind, könnte dies ein großer Effizienzgewinn sein, aber es lohnt sich wahrscheinlich nicht anders.Antworten:
Ein Beitrag über
R
und jede Variante von Fast ist ohne eine Lösung mit rcpp nicht vollständig .Um die Effizienz zu maximieren, ist die Auswahl der richtigen Datenstruktur von größter Bedeutung. Unsere Datenstruktur muss eindeutige Werte speichern und schnell einfügen / zugreifen können. Genau das verkörpert std :: unordered_set . Wir müssen nur bestimmen, wie wir jeden
vector
von ungeordneten eindeutig identifizieren könnenintegers
.Geben Sie den Fundamentalsatz der Arithmetik ein
Das Freihandelsabkommen besagt, dass jede Zahl (bis zur Reihenfolge der Faktoren) durch das Produkt der Primzahlen eindeutig dargestellt werden kann .
Hier ist ein Beispiel, das zeigt, wie wir das Freihandelsabkommen verwenden können, um schnell zu entschlüsseln, ob zwei Vektoren bis zur Reihenfolge äquivalent sind (Hinweis
P
unten ist eine Liste von Primzahlen ...)(2, 3, 5, 7, 11, etc.)
:Daraus sehen wir , dass
vec1
undvec3
korrekt auf die gleiche Anzahl Karte, währendvec2
auf einen anderen Wert zugeordnet wird.Da unsere tatsächlichen Vektoren bis zu hundert ganze Zahlen unter 1000 enthalten können, ergibt die Anwendung des Freihandelsabkommens extrem große Zahlen. Wir können dies umgehen, indem wir die Produktregel des Logarithmus nutzen:
Mit diesem zur Verfügung stehenden Beispiel können wir ein Beispiel mit viel größeren Zahlen angehen (dies beginnt sich bei extrem großen Beispielen zu verschlechtern).
Zunächst benötigen wir einen einfachen Primzahlengenerator (Hinweis: Wir generieren tatsächlich das Protokoll jeder Primzahl).
Und hier ist die Hauptimplementierung:
Hier sind die Ergebnisse, wenn
lst1, lst2, lst3, & lst (the large one)
sie von @GKi angewendet werden.Und hier sind einige Benchmarks mit dem
units
Parameter eingestellt aufrelative
.Etwa dreimal schneller als die bisher schnellste Lösung im größeren Beispiel.
Für mich spricht dieses Ergebnis für die Schönheit und Effizienz
base R
von @GKi, @ chinsoon12, @Gregor, @ThomasIsCoding und anderen. Wir haben ungefähr 100 sehr spezifische Zeilen geschriebenC++
, um eine moderate Beschleunigung zu erzielen. Um fair zu sein,base R
rufen die Lösungen am Ende hauptsächlich kompilierten Code auf und verwenden am Ende Hash-Tabellen, wie wir es oben getan haben.quelle
Nach dem Sortieren können Sie
duplicated
und verwendenall
.Alternative: In einer Schleife sortieren
Alternative: Während der Schleife sortieren und vorzeitig beenden
oder mit
setequal
oder die Idee von @ chinsoon12 leicht verbessern , die Liste mit einem Vektor auszutauschen!
oder vermeiden Sie die zweite
order
oder Austausch
order
mitmatch
(oderfmatch
)Oder ohne vorzeitigen Ausstieg.
oder in C ++ geschrieben
Vielen Dank an @Gregor für Hinweise zur Verbesserung der Antwort!
quelle
lst <- list(list(1,c(2,3,4),c(5,6),7), list(c(2,3,4),1,7,c(5,6)), list(1,c(2,3,4),7,c(6,5)), list(7,1,c(3,2,4),c(5,6)))
wird beurteilt alsFALSE
min
!Performance:
Bibliotheken:
Funktionen:
Daten:
quelle
length(setdiff(Reduce(union,s),Reduce(intersect,s)))==0
, entschuldige meinen Fehler ...Hoffentlich zum 2. Mal Glück
Testfälle:
prüft:
Timing-Code:
Timings:
quelle