On Mar 21, 10:58 pm, Ken Tilton <···········@optonline.net> wrote:
> [...]
> This is somewhat distorted, but the labeled fn show-one is what I really
> have to do: given a mask and a list of numbers some of whom have already
> been "used" indicated by (= 1 (bit mask <that number>)), pick a number
> at random from those still unused. Without consing.
> [...]
I don't know if this is any better, but at least it is different:
(let* ((nums (list 0 1 2 3 4 5 6 7))
(used (make-array (length nums)
:element-type 'bit
:initial-element 0)))
(loop for i below (length nums)
do (show-one nums used)))
(defun show-one (list mask)
(let ((position (pick-one mask)))
(when position
(setf (bit mask position) 1)
(print (nth position list)))))
(defun pick-one (mask)
(let ((first (position 0 mask)))
(when first
(let* ((choices (- (length mask) first 1))
(random (+ first
(if (zerop choices) 0 (random choices)))))
(case (random 2)
(0 (or (position 0 mask :start first :end random :from-end
t)
(position 0 mask :start random)))
(1 (or (position 0 mask :start random)
(position 0 mask :start first :end random :from-end
t))))))))
(I hope Google Groups didn't mess that up...)
The CASE is a bit ugly, but this was just a quickie...
Mattias
;;;; Before someone else complains:
(let* ((nums (list 0 1 2 3 4 5 6 7))
(used (make-array (length nums)
:element-type 'bit
:initial-element 0)))
(loop for i below (length nums)
do (show-one nums used)))
(defun show-one (list mask)
(let ((position (pick-one mask)))
(when position
(setf (bit mask position) 1)
(print (nth position list)))))
;;; Slightly improved randomization:
(defun pick-one (mask)
(let ((first (position 0 mask)))
(when first
(let* ((choices (- (length mask) first))
(random (+ first (random choices))))
(case (random 2)
(0 (or (position 0 mask :start first :end random
:from-end t)
(position 0 mask :start random)))
(1 (or (position 0 mask :start random)
(position 0 mask :start first :end random
:from-end t))))))))
;;; Mattias
From: Ken Tilton
Subject: Re: Another From the Trenches Kenny Gotta Be a Better Way Challenge
Date:
Message-ID: <47e50d29$0$25063$607ed4bc@cv.net>
I better make a better example before you all go postal on me. :)
gimme a sec.
k
Mattias Nilsson wrote:
> ;;;; Before someone else complains:
>
> (let* ((nums (list 0 1 2 3 4 5 6 7))
> (used (make-array (length nums)
> :element-type 'bit
> :initial-element 0)))
> (loop for i below (length nums)
> do (show-one nums used)))
>
> (defun show-one (list mask)
> (let ((position (pick-one mask)))
> (when position
> (setf (bit mask position) 1)
> (print (nth position list)))))
>
> ;;; Slightly improved randomization:
>
> (defun pick-one (mask)
> (let ((first (position 0 mask)))
> (when first
> (let* ((choices (- (length mask) first))
> (random (+ first (random choices))))
> (case (random 2)
> (0 (or (position 0 mask :start first :end random
> :from-end t)
> (position 0 mask :start random)))
> (1 (or (position 0 mask :start random)
> (position 0 mask :start first :end random
> :from-end t))))))))
>
>
> ;;; Mattias
--
http://smuglispweeny.blogspot.com/
http://www.theoryyalgebra.com/
"In the morning, hear the Way;
in the evening, die content!"
-- Confucius
From: Ken Tilton
Subject: Re: Another From the Trenches Kenny Gotta Be a Better Way Challenge
Date:
Message-ID: <47e518bc$0$15206$607ed4bc@cv.net>
Ken Tilton wrote:
> I better make a better example before you all go postal on me. :)
(defun test-it ()
(let* ((nums (delete-duplicates
(loop repeat 20
collecting (random 5000))))
(used (make-array 5000 :element-type 'bit :initial-element 0)))
(flet ((unused (n)
(zerop (bit used n))))
(loop while (every #'unused nums)
do (loop for n in nums
do (setf (bit used n) (random 2))))
; pick one
(let ((pick (pick-one nums used))
(*print-length* 20))
(assert (unused pick))
(assert (find pick nums))
(print `(i like ,pick :out-of ,(loop for n in nums
when (unused n)
collect n)))
pick))))
My original (kinda):
(defun pick-one (nums used)
(loop thereis
(loop for n in nums
when (and (zerop (bit used n))
(zerop (random 50)))
return n)))
I'd show Barry's suggestion but he just served me with an NDA.
kenny
--
http://smuglispweeny.blogspot.com/
http://www.theoryyalgebra.com/
"In the morning, hear the Way;
in the evening, die content!"
-- Confucius
On Mar 22, 3:33 pm, Ken Tilton <···········@optonline.net> wrote:
> Ken Tilton wrote:
> > I better make a better example before you all go postal on me. :)
Yes, and I should have read through the problem desrcription three
more times
before posting. :)
> I'd show Barry's suggestion but he just served me with an NDA.
Yes, his idea seems to lead to some nice code.
Mattias
On Mar 23, 4:50 pm, Barry Margolin <······@alum.mit.edu> wrote:
> He said the list of numbers is short, so I don't see a problem
> with the algorithm being O(length(list)).
Okay, I get it. In that case, the bit field is a waste of space.
You can just put the short list in an array and shuffle that.
> The bit array is a required input for the exercise.
> You can't change the parameters of the problem.
I would question them though. Something just doesn't sound right.
Thanks for the explanation.
--Dan
------------------------------------------------
Dan Bensen
http://www.prairienet.org/~dsb/
In article
<····································@m44g2000hsc.googlegroups.com>,
danb <·········@gmail.com> wrote:
> On Mar 23, 4:50 pm, Barry Margolin <······@alum.mit.edu> wrote:
> > He said the list of numbers is short, so I don't see a problem
> > with the algorithm being O(length(list)).
>
> Okay, I get it. In that case, the bit field is a waste of space.
> You can just put the short list in an array and shuffle that.
>
> > The bit array is a required input for the exercise.
> > You can't change the parameters of the problem.
>
> I would question them though. Something just doesn't sound right.
Homework problems are often artificial, to make a specific point, it
doesn't have to "sound right" for a real application.
--
Barry Margolin, ······@alum.mit.edu
Arlington, MA
*** PLEASE don't copy me on replies, I'll read them in the group ***