paires d'impression à partir d'une liste dans le schéma

Question

Je suis en train d'imprimer des paires d'une liste un peu comme un sous-ensemble dans le schéma, mais avec deux éléments, tout comme ce

(1 2 3 4 5)

((1 2) (1 3) (1 4) (1 5) (2 3) (2 4) (2 5) (3 4) (3 5) (4 5))

le code que j'ai écrit doesn ' t travail

(define (subset x) 
(if (null? x) x 
    (map cons x (subset (cdr x))))) 

ce juste retourner une liste vide

Answer 1

Je préfère écrire le lambdas explicitement, il est plus facile de comprendre ce que les arguments sont passés:

(define subset 
    (lambda (lst) 
     (if (null? lst) 
      lst 
      (append (map (lambda (el) (cons (car lst) el)) (cdr lst)) 
        (subset (cdr lst))) 
     ))) 

---

(subset '(1 2 3 4 5)) 
=> ((1 . 2) (1 . 3) (1 . 4) (1 . 5) (2 . 3) (2 . 4) (2 . 5) (3 . 4) (3 . 5) (4 . 5)) 

---

EDIT: L'explication sur la carte ci-dessous est seulement valide dans certaines versions du schéma, lisez le commentaire de Sylwester à cette réponse.

map traverse les n listes qui lui sont fournies et applique proc aux n éléments à la même position dans les listes. Cela signifie qu'il peut appliquer proc pas plus de fois que la longueur de la liste la plus courte, mais vous continuez à lui donner une liste vide (à partir du dernier appel récursif).

(BTW ceci est dans la plaine scheme)

Answer 2

En #lang racket qui est très facile puisque nous avons combinations:

(combinations '(1 2 3 4 5) 2) 
; ==> ((1 2) (1 3) (2 3) (1 4) (2 4) (3 4) (1 5) (2 5) (3 5) (4 5)) 

Maintenant, cela n'imprime rien. Pour obtenir imprimer sur le terminal que vous pouvez utiliser displayln:

(displayln (combinations '(1 2 3 4 5) 2)) 
; ==> #<void>, ((1 2) (1 3) (2 3) (1 4) (2 4) (3 4) (1 5) (2 5) (3 5) (4 5)) printed to terminal as side effect 

Answer 3

Si l'ordre des éléments est également important, suivant peut être utilisé:

(define (subsets l) 
    (let loop ((n 0)      ; run a loop for each item 
      (ol '()))     ; start with blank output list 
    (cond 
     [(= n (length l)) (reverse ol)] ; output ol when last item reached; 
     [else 
     (let* ((x (list-ref l n))  ; get one item 
       (jl (for/list ((i l)  ; get remaining list 
          (j (in-naturals)) 
          #:unless (= j n)) 
        i)) 
       (kl (for/list ((i jl)) ; make combinations with each of remaining list 
        (list x i)))) 
     (loop (add1 n) (cons kl ol)))]))) 

Test:

(subsets '(1 2 3 4 5)) 

Sortie:

'(((1 2) (1 3) (1 4) (1 5)) 
    ((2 1) (2 3) (2 4) (2 5)) 
    ((3 1) (3 2) (3 4) (3 5)) 
    ((4 1) (4 2) (4 3) (4 5)) 
    ((5 1) (5 2) (5 3) (5 4)))