Get numbers for the lottery

问题:

As part of learning Lisp I'm currently trying to write a function that helps me fill out my lottery ticket. I want that function to return

• a list
• of six numbers,
• where each number is between 1 and 49,
• without duplicate numbers,
• and being the list ordered in an ascending way.

So far, I'm done with four of the five requirements. This is my current code:

(defun lottery ()
  (sort (loop repeat 6 collect (1+ (random 49))) #'<))

When I run this function I get something such as:

(lottery)
;; => (3 10 23 29 41 43)

Basically, everything's fine - except that sometimes I have the very same number twice within the list. And here it starts to get puzzling. My problem is that I'm not too sure on how to solve this in a Lisp way. There are multiple options I can think of:

• Run remove-duplicates on the result, then use length to check whether the list has less than six elements, and if so, run lottery a second time, append it to the first result, use subseqto only get the first six elements, and repeat. This works, but is not very elegant, especially as it involves sorting & co. multiple times.
• Start with an empty list, create a single random number using (1+ (random 49)), and call pushnew. Now call lottery recursively with the list until length returns six. I like this approach way more, but I'm still not too convinced, as this way I'd need two functions: An outer one, lottery, and an inner one, that is called recursively and handles the list as parameter.
• Start with a hash-table, use the numbers from 1 to 49 as keys, and set the keys' value to nil. Then, inside a loop, get a random number between 1 and 49, and change the value of the appropriate key to t. Return once six elements of the hash-table have t as value. IMHO this is the worst approach so far, as it wastes memory quite a lot and doesn't scale well.

What do you think of those options, and are there other ways of implementing this? How would an advanced Lisp developer solve this?

Any hints?

回答1:

Create a list of all the numbers from 1 to 49, shuffle, take 6, sort.

=> (sort (take 6 (shuffle (range 1 50))))
; (8 14 16 23 34 39)

Addition by original poster:

Just to show the final implementation, I'm adding it here:

(defun shuffle (list)
  (let ((len (length list)))
    (loop repeat len
      do
        (rotatef
          (nth (random len) list)
          (nth (random len) list))
      finally
        (return list))))

(defun lottery ()
  (sort (subseq (shuffle (loop for i from 1 to 49 collect i)) 0 6) #'<))

(lottery)
;; => (5 6 17 21 35 37)

回答2:

(defun lotto ()
  (labels ((lot (acc)  
             (if (= 6 (length acc)) 
                 acc 
                (lot (adjoin (1+ (random 49)) acc)))))
    (sort (lot nil) #'<)))

回答3:

Using an accumulator fed by recursion:

(defun lottery ()
  (setf grid (loop for i from 1 to 49 collect i))
  (labels ((choose (source num)
    (if (or (null source) (zerop num))
      nil
      (let ((elem (nth (random (length source)) source)))
        (cons elem (choose (remove elem source) (1- num)))))))
    (sort (choose grid 6) #'<)))

The lottery function is first generating a list of numbers put into the grid variable. Then we define an internal choose local function. This function gets one random number in the list it is provided inside the interface and calls itself on the list minus the chosen element. The last step is to sort the resulting list.