Berechnen der `Länge` von 'Permutationen xs`

Question

Geben Sie in Haskells GHCi length$ permutations [1..8] ein und es ist sofort verfügbar. Mit length$ permutations [1..16] Sie schauen .. Minuten, Stunden vielleicht? Wenn alles, was wir wollen, ist die tatsächliche Anzahl der Ergebnisse, die permutations xswürde produzieren (dh. Nicht durch sie durchlaufen müssen) gibt es offensichtlich eine einfache billige Formel nur die length von xs kennen.

ich mit der Mathematik leider langsam bin, aber da len = length xs, bemerkte ich, dass die Antwort, indem sie eine positive len zu finden ist:

numofperms 0 = 0 
numofperms 1 = 1 
numofperms ln = ln * (numofperms (ln - 1)) 

Aber während dies ist offensichtlich schneller als die Bewertung alle permutations, warum Rekursiv! Ich bin mir sicher, dass sich dort eine "Formel" versteckt, die ich nicht sofort/intuitiv sehen kann. Wie würde man die obige Logik in eine einfache, nicht rekursive mathematische Berechnung übersetzen? "Etwas mit faktorials" oder so etwas?

Bevor Sie als Duplikat markieren: Ich bin sicher, dass ich einfach „die Antwort, auf die Formel, um die Anzahl der Permutationen gibt“ oder elsewere leicht hier finden kann, aber die eigentliche Frage (wenn auf dieses Format erlaubt) Wie springt man von der intuitiv geschriebenen rekursiven Logik zu billigeren und korrekeren Berechnungen wie in (x * (x+-foo^bar)) --- das kann sicherlich ein pädagogischer Thread in dieser Hinsicht für andere angehende funktionale Programmierer werden, die hier in der Zukunft ankommen!

Answer 1

Dieser ist nicht korrekt:

numofperms 0 = 0 

die Anzahl der Permutationen von 0 Elemente 1 ist (permutations [] == [[]]). In diesem Sinne würde es vielleicht helfen, die Dinge kürzer zu machen:

f(0) = 1 
f(n) = n * f(n - 1) 

Bekannt? Es ist n! - die factorial.