Come posso generare tutte le permutazioni di determinate dimensioni con ripetizioni in Scheme?

Question

Sto imparando lo schema e sto cercando di generare permutazioni con ripetizioni di determinate dimensioni.

Ad esempio, dato n = 4 e impostato S = {a, b, c, d, e, f}, mi piacerebbe generare tutte le permutazioni possibili: {a, 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}.

Il guaio è che non riesco a capire come scegliere 'a' 4 volte, e ricordare che l'ho scelto 4 volte, quindi selezionare 'a' 3 volte, e 'b' una volta, e ricorda tutto questo, quindi non lo prendo di nuovo.

So che questi tipi di problemi si risolvono meglio con algoritmi ricorsivi, ma rende tutto più complicato, come, come ricordo nella ricorsione, quali elementi ho scelto.

Non so come affrontare questo problema. Sarei molto felice se qualcuno scrisse il processo di pensiero per risolvere questo problema. Lo apprezzerei molto!

Per favore aiutatemi.

Grazie, Boda Cydo.

Answer 1

È consigliabile iniziare dall'interfaccia della procedura e dai risultati previsti. La tua procedura verrà chiamata (permutations size elements) e si prevede che restituisca un elenco di permutazioni degli elementi in ELEMENTS, ogni permutazione essendo di lunghezza SIZE articoli. La figura rappresenterà una "permutazione" come una lista. Quindi se hai chiamato (permutations 1 '(a b c)) ti aspetteresti una produzione di ((a) (b) (c)).

Quindi, il trucco delle procedure ricorsive, è che devi capire quale sia la condizione base a cui puoi rispondere facilmente e il passo ricorsivo a cui puoi rispondere modificando la soluzione di un problema più semplice. Per PERMUTAZIONI, la figura del passaggio ricorsivo coinvolgerà SIZE in diminuzione, quindi il passo base sarà quando SIZE è 0, e la risposta è una lista di una permutazione a lunghezza zero, i. e. (()).

Per rispondere al passaggio ricorsivo, è necessario capire cosa fare al risultato per la dimensione N-1 per ottenere un risultato per la dimensione N. Per fare ciò, può aiutare a scrivere alcuni risultati attesi per il piccolo N e vedere se è possibile scorgere un modello:

 
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) ...) 

quindi, in pratica ciò che si vuole fare è, dato R = (permutations n elements), si può ottenere (permutations (+ n 1) elements) prendendo ogni permutazione P in R, e quindi per ogni elemento e in eLEMENTI , confinare con E a P per creare una nuova permutazione e collezionarne una lista. E possiamo farlo con le mappe nidificate:

 
(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)))) 

sto usando FLATMAP per la mappatura esterno, perché la mappa interiore crea liste di nuove permutazioni, e dobbiamo aggiungere quelle liste insieme per creare quella grande appartamento lista di permutazioni che vogliamo

Naturalmente, questo è tutto presupponendo che tu sappia e abbia un buon controllo sulle operazioni di sequenza come MAP. Se non lo fai, sarebbe davvero difficile trovare una soluzione elegante come ho appena fatto qui.

Answer 2

Suggerimento: è possibile utilizzare i parametri per una chiamata ricorsiva per "ricordare" le altre chiamate ricorsive effettuate. ;)

Answer 3

Ecco un'altra versione: ho usato riduci, non flatmap. L'ho scritto in MIT-scheme.