Ich schreibe ein Programm (in R, falls dies wichtig ist), in dem ich die Anzahl der eindeutigen Permutationen eines Vektors von Elementen berechnen muss, die wiederholte Werte enthalten können. Die mathematische Formel < / a> denn dies ist einfach: die Fakultät der Gesamtzahl der Elemente geteilt durch das Produkt der Fakultäten der Zählungen jedes einzelnen Elements. Eine naive Berechnung des Ergebnisses führt jedoch sehr wahrscheinlich zu Überläufen, selbst wenn die tatsächliche Antwort nicht sehr groß ist. Zum Beispiel:

# x has 200 elements, but 199 of them are identical
x <- c(rep(1, 199), 2)
num_unique_permutations <- factorial(length(x)) / prod(factorial(table(x)))

Wenn dies nicht überlaufen würde, wäre num_unique_permutations 200! / (199! * 1!) = 200. Beide 200! und 199! Überlaufen Sie den Maximalwert eines Double, sodass das tatsächliche Ergebnis NaN ist. Gibt es eine gute Möglichkeit, diese Berechnung durchzuführen, bei der Überläufe (oder Unterläufe) immer vermieden werden, solange die Antwort selbst nicht überläuft? (Oder vielleicht, solange es nicht innerhalb eines Faktors von length(x) des Überlaufens liegt?)


(Beachten Sie, dass R für die meisten numerischen Berechnungen Doubles verwendet, das Problem jedoch nicht für Doubles spezifisch ist. Jeder numerische Typ mit einem Bereich hat das gleiche Problem. Außerdem ist es mir egal, ob ich ein wenig an Genauigkeit für Gleitkomma-Mathematik verliere, da Ich benutze dies nur, um eine grobe Obergrenze für etwas zu erhalten.)

2
Ryan C. Thompson 1 Sept. 2020 im 18:25

2 Antworten

Beste Antwort

Verwenden Sie in Basis R lfactorial, um die Logarithmen des Zählers und des Nenners zu berechnen. Dann potenzieren Sie den entsprechenden Unterschied.

numer <- lfactorial(length(x))
denom <- sum(lfactorial(table(x)))
exp(numer - denom)
#[1] 200

Dies kann leicht als Funktion geschrieben werden.

num_unique_permutations <- function(x){
  numer <- lfactorial(length(x))
  denom <- sum(lfactorial(table(x)))
  exp(numer - denom)
}

num_unique_permutations(x)
#[1] 200
4
Rui Barradas 1 Sept. 2020 im 16:09

Sie können die Bibliothek gmp verwenden.

library(gmp)
factorial(as.bigz(length(x))) / prod(factorial(as.bigz(table(x))))
#[1] 200
2
GKi 1 Sept. 2020 im 15:30