Eine Funktion schreiben, um alle Teilsequenzen der Größe n in Haskell zu erhalten?

Question

Ich habe versucht, eine Funktion zu schreiben, um alle Teilsequenzen einer Liste zu erhalten, die die Größe n haben, aber ich bin nicht sicher, wie ich vorgehen soll.

Ich dachte, dass ich wahrscheinlich die eingebaute Data.List.subsequences verwenden könnte und nur die Listen herausfiltern, die nicht der Größe n sind, aber es scheint wie eine eher umständliche und ineffiziente Art und Weise zu tun, und ich möchte lieber nicht tun, dass, wenn ich es vermeiden kann, so dass ich frage mich, wenn Sie irgendwelche Ideen haben?

Ich möchte, dass es so etwas wie diese Art ist

subseqofsize :: Int -> [a] -> [[a]]

Zur weiteren Verdeutlichung hier ein Beispiel für das, wonach ich suche:

subseqofsize 2 [1,2,3,3]
[[1,2],[1,3],[2,3],[1,3],[2,3],[3,3]]

Außerdem ist mir die Reihenfolge völlig egal.

Answer 1

Ich gehe davon aus, dass es sich um eine Hausaufgabe handelt, oder dass Sie dies als Übung machen, um zu lernen, also werde ich Ihnen einen Überblick geben, wie die Lösung aussieht, anstatt Ihnen die richtige Antwort vorzuschreiben.

Wie auch immer, dies ist eine Frage der Rekursion.

Es gibt zwei Basisfälle:

sublistofsize 0 _        = ...
sublistofsize _ []       = ...

Dann gibt es zwei rekursive Schritte:

sublistofsize n (x : xs) = sublistsThatStartWithX ++ sublistsThatDon'tStartWithX
  where sublistsThatStartWithX = ...
        sublistsThatDon'tStartWithX = ...

Denken Sie daran, dass die Definitionen der Basisfälle mit den Definitionen in den rekursiven Fällen übereinstimmen müssen. Denken Sie sorgfältig nach: Nehmen Sie nicht einfach an, dass die Basisfälle beide zu einer leeren Liste führen.

Ist das hilfreich?

Answer 2

Sie können sich das mathematisch vorstellen: Um die Unterlisten der Größe k können wir uns ein Element ansehen x der Liste; entweder enthalten die Unterlisten x oder sie tun es nicht. Im ersten Fall besteht die Teilliste aus x y luego k -1 Elemente, die aus den übrigen Elementen ausgewählt werden. Im letzteren Fall bestehen die Teillisten aus k Elemente, die aus den Elementen ausgewählt werden, die nicht x . Dies bietet sich für eine (relativ) einfache rekursive Definition an.

(Es gibt sehr starke Ähnlichkeiten mit dem Rekursive Formel für Binomialkoeffizienten was zu erwarten ist.)

(Edit: Code entfernt, aus den Gründen von dave4420 :) )