CODEWITHSUNDEEP
schemeracket
zaig
zaig

Reputation: 411

scheme - Show all the pairs of elements which have the greatest common divisor 1

I started with the algortihm for combinations but when m will become 0 in the recursion, the first y will be '(()) so the program will show only () which will repeat 4*the size of the list times.

(define (pairs-GCD L)
 (define (comb m lst)
  (cond ((= m 0) '(()))
    ((null? lst) '())
    (else (append (map (lambda (y) (cond (equal? (GCD(car lst) y) 1) (cons (car lst) y))) (comb (- m 1) (cdr lst))) (comb m (cdr lst))))))
 (comb 2 L)

) EDIT: Corrected output Input: '(2 5 3 6 11 15) Output: '((2 5) (2 3) (2 11) (2 15) (5 3) (5 6) (5 11) (6 11) (3 11) (6 11) (11 15))

Upvotes: 1

Views: 158

Answers (1)

Óscar López
Óscar López

Reputation: 236004

This is simple to do if we use Racket's built-in procedures - we can easily generate all 2-element combinations, test them for the given condition and output a list with the correct pairs:

(define (pairs-gcd lst)
  (for/list ([pair (in-combinations lst 2)]
             #:when (= (apply gcd pair) 1))
    pair))

For example:

(pairs-gcd '(2 5 3 6 11 15))
=> '((2 5) (2 3) (5 3) (5 6) (2 11) (5 11) (3 11) (6 11) (2 15) (11 15))

Upvotes: 2

Related Questions