Menu

Show posts

This section allows you to view all posts made by this member. Note that you can only see posts made in areas you currently have access to.

Show posts Menu

Messages - rickyboy

Pages 1 ... 39 40 41
#601
Anything else we might add? /
April 15, 2005, 10:34:36 PM
He, he, he.  Of course, you may use the code in "Tips and Tricks"!  I'm just sorry I can't contribute code on the order that others have -- I just flat out don't have the time.  :-(



BTW, there is a subtle bug in the newLISP version of 'make-k-permutations'.  Say you have a multiset M given by
Code Select
(setq M '(93 4 42 93 5 7 8 10 8 8 10 42 4))
Then, when you compute the 2-permutations of M, your first pivot p will be 93.  In this case, if you then remove all 93s from M (thereby yielding 'sub-multiset') and compute the (k-1)-permutations of 'sub-multiset' (which are all singletons in this case), you'll never get back the singleton '(93)' which you would expect because of the second occurrence of 93 in M.  Which means that the final answer won't have the 2-permutation '(93 93)', namely.



The answer is to remove only one occurrence of any pivot in the multiset yielding 'sub-multiset' and indeed this is why the Common Lisp version has the call to 'remove' with the ':count 1' keyword argument.  We would need to mimick this behavior, as in the following.
Code Select
(define (make-k-permutations k multiset)
  (let ((pivots (unique multiset)))
    (if (= k 1)
        (map list pivots)
        (let ((acc '()))
          (dolist (p pivots)
            (let ((sub-multiset (remove1 p multiset)))
              (dolist (sub-perm
                       (make-k-permutations (- k 1) sub-multiset))
                (push (cons p sub-perm) acc))))
          acc))))

(define (remove1 elt lst)
  (let ((elt-pos (find elt lst)))
    (if elt-pos (pop lst elt-pos))
    lst))
#602
Anything else we might add? /
April 15, 2005, 10:41:16 AM
Hello Jeremy,



This reply is a little dated since I really only just joined this group recently.



How about some code for k-permutations of a multi-set?  It's in Common Lisp, not newLISP (but you could translate it).
Code Select
;;
;; Warren-Hanson algorithm for generating permutations of
;; multisets.
;;
> (defun make-k-permutations (k multiset)
    (let ((pivots (remove-duplicates multiset)))
      (if (= k 1)
          (mapcar #'list pivots)
          (let ((acc '()))
            (dolist (p pivots acc)
              (let ((sub-multiset (remove p multiset :count 1)))
                (dolist (sub-perm (make-k-permutations
                                   (1- k)
                                   sub-multiset))
                  (push (cons p sub-perm) acc))))))))
MAKE-K-PERMUTATIONS
> (setq M1 '(93 4 42 93 5 7 8 10 8 8 10 42 4))
(93 4 42 93 5 7 8 10 8 8 10 42 4)
> (make-k-permutations 2 M1)
((4 4) (4 42) (4 10) (4 8) (4 7) (4 5) (4 93) (42 4) (42 42)
 (42 10) (42 8) (42 7) (42 5) (42 93) (10 4) (10 42) (10 10)
 (10 8) (10 7) (10 5) (10 93) (8 4) (8 42) (8 10) (8 8) (8 7)
 (8 5) (8 93) (7 4) (7 42) (7 10) (7 8) (7 5) (7 93) (5 4) (5 42)
 (5 10) (5 8) (5 7) (5 93) (93 4) (93 42) (93 10) (93 8) (93 7)
 (93 5) (93 93))


How this works is you first make a list of pivots which are just the unique entries in the given multiset.  For each pivot p, remove p from the original multiset, yielding a multiset like the original except minus one occurrence of p.  Then recursively, compute the (k-1)-permutations of this new multiset.  Now, cons the pivot p onto each of these (k-1)-permutations, accumulating them in 'acc'.  After you do this for every pivot p, you have the answer!



I hope this helps.  Sorry for the delay (you may already have had an answer!).  If you've found a better solution, please let me (us) know.



Regards,  --Ricky



P.S. -- The function 'make-k-permutations' is not really formally known as the Warren-Hanson algorithm.  :-)  This is a joke -- my friend John Warren and I collaborated on its development, hence the endearing name.
#603
Whither newLISP? /
April 15, 2005, 06:10:54 AM
Thanks Lutz!
#604
Whither newLISP? / Is newLISP "prejudiced" against recursive function
April 14, 2005, 08:55:14 PM
Hello everyone,



Consider this function which adjoins one element 'x' to a set 'S', non-destructively.
Code Select
(define (adjoin1 S x)
  (if (or (= x nil) (= S nil) (member x S))
      S
      (cons x S)))
> (define L '(1 2 3))
(1 2 3)
> (adjoin1 L 0)
(0 1 2 3)

Now to adjoin more than one element (at a time), it seems natural to then say
Code Select
(define (adjoin S)
  (if (empty? (args))
      S
      (apply adjoin
             (cons (adjoin1 S (first (args)))
                   (rest (args))))))
but this does not work --- it fails on a 'call stack overflow'.



Now, yes, I know that the alternative definition
Code Select
(define (adjoin S)
  (if (empty? (args))
      S
      (let ((result S))
        (dolist (x (args))
          (set! result (adjoin1 result x))))))
works and indeed, there are other ways also, for instance:
Code Select
(define (adjoin S) (unique (append S (args))))

However, why doesn't the first (recursive) definition of 'adjoin' work?  (I like the last definition, but I may need to define a recursive function in the future and so still need to figure out what is going on with the first definition.)



Thanks!  --Ricky
#605
newLISP newS / Makefile change: uninstall target
April 14, 2005, 08:07:43 PM
Hello Lutz,



This would be a small change to 'Makefile' in the distro, but I recommend to change the 'uninstall' section according to this 'diff' output:


Code Select
204,208c204,208
<       -rm  /usr/bin/newlisp
<       -rm  /usr/bin/newlisp-tk
<       -rm  -rf /usr/share/newlisp
<       -rm  /usr/share/man/man1/newlisp.1
<       -rm  /usr/share/man/man1/newlisp-tk.1
---
>       -rm  $(bindir)/newlisp
>       -rm  $(bindir)/newlisp-tk
>       -rm  -rf $(datadir)/newlisp
>       -rm  $(mandir)/man1/newlisp.1
>       -rm  $(mandir)/man1/newlisp-tk.1


Cheers,  --Ricky
#606
newLISP in the real world / How to deconstruct a list into spreadsheet
April 13, 2005, 12:17:39 PM
Hello everyone,



I have a question regarding the use of expressions returned from newlisp.dll to an Excel spreadsheet (thanks BTW for providing the Excel VBA "glue code" to newlisp.dll).  Everything seems to work great, until I need to assign newlisp list components to cells of a spreadsheet.  Is that possible?  If so, then how?



For instance, say I have defined a function in newlisp called 'my-list-maker'.  Then if I put in cell A1 '(my-list-maker <args>)' and the function call '=newlispeval(A1)' in another cell, I get the printed representation of the list in this cell (which can be rather long, as in my particular application).  It would be nice to be able to say instead '=newlisp_destruct_value_vertically(A1)' and the list components could be put one-by-one in a vertical column starting with the cell containing the function call.  This would be useful, say when one wants to use Excel to graph a list of numbers coming from newlisp.



I wonder if this is possible and I admit much ignorance regarding Excel -- perhaps this is why the solution eludes me.  Thanks for any help!  --Rick
Pages 1 ... 39 40 41