AuK/Durchläufe durch Graphen SS12

Wiki-Quelltext dieser Seite.

<language>Scheme</language>
== Test: Tiefensuche ==

<code id="4f68b0ac368e7" hidden>(import debugging) (define amb-fail '*) (define initialize-amb-fail (lambda () (set! amb-fail (lambda () (error "amb" "It fails"))))) 
(initialize-amb-fail) (define-syntax amb (syntax-rules () ((amb alt ...) (let ((+prev-amb-fail amb-fail)) (call/cc (lambda (+sk) (call/cc 
(lambda (+fk) (set! amb-fail (lambda () (set! amb-fail +prev-amb-fail) (+fk 'fail))) (+sk alt))) ... (+prev-amb-fail))))))) (define-syntax 
bag-of (syntax-rules () ((bag-of e) (let ((+prev-amb-fail amb-fail) (+results '())) (if (call/cc (lambda (+k) (set! amb-fail (lambda () (+k 
#f))) (let ((+v e)) (set! +results (cons +v +results)) (+k #t)))) (amb-fail)) (set! amb-fail +prev-amb-fail) (reverse! +results))))) (define 
choice (lambda (ls) (eval (cons 'amb (map (lambda (x) (list 'quote x)) ls))))) (define multichoice (lambda (ls n) (if (= n 0) '() (let ((item 
(choice ls))) (cons item (multichoice (delete item ls) (- n 1))))))) (define delete (lambda (item ls) (cond ((null? ls) '()) ((eqv? (car ls) 
item) (cdr ls)) (else (cons (car ls) (delete item (cdr ls))))))) (define randomchoice (lambda (n) (letrec ((enumerate (lambda (i) (if (= i 0) 
'() (cons i (enumerate (- i 1))))))) (let ((numberlist (enumerate n))) (choice numberlist)))))</code>

<code id="4f68afe40f6c1">
(define tiefensuche (lambda (knoten besucht)
              (cond
                [(null? knoten) besucht]
                [else
                 (tiefensuche (cdr knoten) (cons (car knoten) besucht))
                 (tiefensuche (cdr knoten) besucht)])))

;(trace 'tiefensuche)
</code>

<run id="4f68afe40f72f">(tiefensuche '(1 2 3) '())</run>

== Test 2: Tiefensuche ==

<code id="4f68cd9f6c7bc">
(define tiefensuche2 (lambda (ls)
                       (cond
                         [(null? ls) '(())]
                         [else (append (powerset_alt (cdr ls))
                                       (map (lambda (x) (cons (car ls) x))
                                            (tiefensuche2 (cdr ls))))])))

</code>

<run id="4f68cd9f6c839">(tiefensuche2 '(1 2 3))</run>