Wie generiere ich alle Permutationen bestimmter Größe mit Wiederholungen in Scheme?

Question

Ich lerne Schema und ich versuche Permutationen mit Wiederholungen bestimmter Größe zu generieren.

Zum Beispiel, gegeben n = 4 und setzen S = {a, b, c, d, e, f}, möchte ich alle möglichen Permutationen generieren: {a, a, a, a}, { a, a, b}, ..., {a, a, a, f}, {a, a, b, a}, {a, a, b, b}, ..., {a, a, b, f}, ... {f, a, a, a}, {f, a, a, b} ..., {f, a, a, f}, ... {f, f , f, f}.

Das Problem ist, dass ich nicht verstehen kann, wie man 'a' 4 mal wählt, und erinnere mich, dass ich es 4 Mal ausgewählt hatte, dann 'a' 3 mal und 'b' einmal, und erinnere mich an alle das, also wähle ich es nicht wieder.

Ich weiß, dass diese Art von Problemen am besten mit rekursiven Algorithmen gelöst werden, aber es macht nur alles komplizierter, wie, wie erinnere ich mich in der Rekursion, welche Elemente ich ausgewählt habe.

Ich weiß nicht, wie ich dieses Problem überhaupt angehen soll. Ich wäre sehr froh, wenn jemand den Gedanken zur Lösung dieses Problems ausschreiben würde. Ich würde es sehr schätzen!

Bitte helfen Sie mir.

Danke, Boda Cydo.

Answer 1

Es ist gut, von der Benutzeroberfläche der Prozedur und den erwarteten Ergebnissen zu starten. Ihre Prozedur wird (permutations size elements) heißen und es wird erwartet, dass sie eine Liste von Permutationen der Elemente in ELEMENTS zurückgibt, wobei jede Permutation SIZE-Elemente lang ist. Abbildung werden Sie eine "Permutation" als Liste darstellen. Wenn Sie also (permutations 1 '(a b c)) aufrufen, erwarten Sie eine Ausgabe von ((a) (b) (c)).

Also der Trick über rekursive Verfahren, müssen Sie herausfinden, was die Grundbedingung ist, dass Sie leicht beantworten können, und den rekursiven Schritt, den Sie durch die Änderung der Lösung eines einfacheren Problems beantworten können. Für PERMUTATIONEN wird angenommen, dass der rekursive Schritt eine Verringerung der SIZE beinhaltet, so dass der Basisschritt erfolgen wird, wenn SIZE 0 ist, und die Antwort ist eine Liste einer Null-Längen-Permutation, d.h. e. (()).

Um den rekursiven Schritt zu beantworten, müssen Sie herausfinden, was mit dem Ergebnis für die Größe N - 1 zu tun ist, um ein Ergebnis für die Größe N zu erhalten. Dazu kann es hilfreich sein, einige erwartete Ergebnisse für kleine N zu schreiben sehen und wenn Sie ein Muster erkennen kann:

 
ELEMENTS = (a b) 
SIZE (PERMUTATIONS SIZE ELEMENTS) 
0  (()) 
1  ((a) (b)) 
2  ((a a) (a b) (b a) (b b)) 
3  ((a a a) (a a b) (a b a) (a b b) (b a a) ...) 

Also im Grunde, was Sie tun möchten, ist, da R = (permutations n elements), können Sie (permutations (+ n 1) elements) erhalten, indem jede Permutation P in R nehmen, und dann für jedes Element E in ELEMENTS , grenzen E an P an, um eine neue Permutation zu erstellen und eine Liste von ihnen zu sammeln. Und wir können dies tun, mit verschachtelten MAPs:

 
(define (permutations size elements) 
    (if (zero? size) 
     '(()) 
     (flatmap (lambda (p)   ; For each permutation we already have: 
       (map (lambda (e)  ; For each element in the set: 
         (cons e p)) ;  Add the element to the perm'n. 
         elements)) 
       (permutations (- size 1) elements)))) 

Ich verwende FLATMAP für die äußere Mapping, da die innere MAP-Listen neuer Permutationen erzeugt, und wir müssen diese Listen anhängen zusammen, um die eine große Wohnung zu schaffen Liste der Permutationen, die wir wollen.

Natürlich geht das alles davon aus, dass Sie wissen und Sequenzoperationen wie MAP gut im Griff haben. Wenn Sie es nicht tun, wäre es wirklich schwierig, eine elegante Lösung zu finden, wie ich es gerade hier getan habe.

Answer 2

Hinweis: Sie können Parameter für einen rekursiven Aufruf verwenden, um sich zu erinnern, was andere rekursive Aufrufe getan haben. ;)

Answer 3

Hier ist eine andere Version: Ich verwende reduzieren, nicht Flatmap. Ich schrieb es in MIT-scheme.

(define (per s) 

    (define (ins c before after) 
    (if (null? after) 
     (list (append before (list c))) 
     (append (list (append before (list c) after)) 
       (ins c 
        (append before (list (car after))) 
        (cdr after))))) 
    (define (iter l) 
    (cond ((null? l) 
      '(())) 
      (else 
      (let ((rest (iter (cdr l)))) 
      (reduce-left append 
         () 
          (map (lambda (x) (ins (car l)() x)) 
           rest)))))) 
    (iter s)) 

(per '(1 3 2 4))