Also: for building enumerations, check out the data/enumerate library. On Tuesday, September 22, 2015, Vincent St-Amour < stamo...@eecs.northwestern.edu> wrote:
> Hi Erich, > > I haven't looked at your code in detail, but found a few potentially > relevant bits of info on Wikipedia. > > First, it looks like Fubini numbers actually give you the number of > *total* preorders for a set of size n. Is this what you're looking for? > The number of preorders is instead: https://oeis.org/A000798 > > The Wikipedia article on preorders[1] suggests a possible enumeration > strategy. It mentions that there is a 1-1 correspondence between > preorders and pairs (partition, partial order). Enumerating those > separately then taking the cartesian product (and then combining those > into a preorder representation) may be easier than generating preorders > directly. And if you're interested in total preorders, then testing > the generating preorders for totality would achieve that. > > Hope that helps! > > Vincent > > > [1] https://en.wikipedia.org/wiki/Preorder > > > > On Tue, 22 Sep 2015 11:30:14 -0500, > Erich Rast wrote: > > > > 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 <javascript:;>. > > For more options, visit https://groups.google.com/d/optout. > > -- > 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 <javascript:;>. > For more options, visit https://groups.google.com/d/optout. > -- 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.
