Hi,
First of all, this is not a homework assignment. For some work in
philosophy (modern philosophy, I guess) I need to generate all
preorders from a given list up to a reasonable size of n=8. I didn't
find any general algorithm for it, so I made up my own that
unfortunately doesn't work correctly, and I can't find the error. I
haven't studied CS and this is a bit above my head. :/
The number of preorders is given by the Fubini numbers (A000670 in
OEIS): 1, 1, 3, 13, 75, 541, 4683, 47293, 545835, ... The code below
works for n=3, but for n=4 already gives only 73 instead of 75 results.
Input is a non-empty list, output is a list of lists each of which
contains simple elements or sets of equivalent elements.
Does anybody have an idea how to do this correctly? Any help would be
greatly appreciated!
Best,
Erich
; ---- Start of program
#lang racket
(define (list-subtract l1 l2)
(let loop ((x l2)
(result l1))
(cond
((null? x) result)
(else (loop (cdr x) (remove (car x) result))))))
(define (non-empty-sublists li result)
(cond
((null? li) result)
(else (non-empty-sublists (cdr li) (cons li result)))))
(define (generate-from-sublists li)
(for*/fold [(result '())]
([x (in-list (non-empty-sublists (cdr li) '()))])
(let* ((y (list-subtract li x)))
(cons (list (setify x) (setify y)) result))))
(define (preorders li)
(cons (apply set li)
(for/fold ([result '()])
([p (in-permutations li)])
(append (generate-from-sublists p) result))))
(define (singleton? x)
(and (list? x)
(null? (cdr x))))
(define (setify x)
(if (singleton? x) (car x) (apply set x)))
; The following is just for displaying
(define (display-equivalences s)
(define li (set->list s))
(display (car li))
(for ([elem (in-list (cdr li))])
(display "~")
(display elem)))
(define (display-aux elem)
(cond
((set? elem)
(display-equivalences elem))
(else (display elem))))
(define (display-preorder li)
(cond
((set? li)
(display-equivalences li))
(else
(display-aux (car li))
(for ([elem (in-list (cdr li))])
(display ">")
(display-aux elem)))))
(define (display-preorders li)
(define orders (preorders li))
(for ([elem (in-list orders)])
(display-preorder elem)(newline)))
; Example that works - but for '(1 2 3 4) it already misses 2 cases :(
(display-preorders '(1 2 3))
--
You received this message because you are subscribed to the Google Groups
"Racket Users" group.
To unsubscribe from this group and stop receiving emails from it, send an email
to racket-users+unsubscr...@googlegroups.com.
For more options, visit https://groups.google.com/d/optout.
