Lisp newbie: deck of cards in Lisp

Discussion of Common Lisp
Destruct1
Posts: 20
Joined: Wed Jan 20, 2010 1:40 am

Re: Lisp newbie: deck of cards in Lisp

Post by Destruct1 » Tue Feb 16, 2010 2:16 am

gugamilare wrote:
Destruct1 wrote:Here is a basic framework (/ snippet of code):

http://rosettacode.org/wiki/Playing_cards#Common_Lisp

What I find a neat trick for shuffling is using a sort applicative operator with
a random function as key.
That is what I did above :)
Good job :D

I am not sure if I remember correctly but I think there is another way which makes the sorting more comfortable.
Instead of passing a comparison lambda (lambda (x y) (which-is-greater-x-or-y)) there is a sorting algorythm that takes a "fitness
function" which maps any object/string to a numerical value and then sorts the list by their fitness integer.

Like this:
fitness function: (lambda (d) (return-a-numerical-value))
shuffle with fitness function: (mysterious-sort #'(lambda (d) (random)) cardlist)

gugamilare
Posts: 406
Joined: Sat Mar 07, 2009 6:17 pm
Location: Brazil
Contact:

Re: Lisp newbie: deck of cards in Lisp

Post by gugamilare » Tue Feb 16, 2010 5:38 am

Destruct1 wrote:Good job :D
Thanks!
Destruct1 wrote:I am not sure if I remember correctly but I think there is another way which makes the sorting more comfortable.
Instead of passing a comparison lambda (lambda (x y) (which-is-greater-x-or-y)) there is a sorting algorythm that takes a "fitness
function" which maps any object/string to a numerical value and then sorts the list by their fitness integer.

Like this:
fitness function: (lambda (d) (return-a-numerical-value))
shuffle with fitness function: (mysterious-sort #'(lambda (d) (random)) cardlist)
The problem would be sorting the same number twice. For instance, the position sorted for the 2 of spades would be the same that the position for the ace of clubs, then the algorithm would replace the 2 of spades by the ace of clubs, leaving the deck with no 2 of spades.

You could maintain a list with all possible position and remove the random elements from it:

Code: Select all

(defun misterious-sort (pos-function vector)
  (let ((new-vector (copy-sequence 'vector vector))
        (size (length vector)))
    (dotimes (i size)
      (let ((elt (aref vector i)))
        (setf (aref new-vector (funcall pos-function i elt))
              elt)))
    new-vector))

(defun shuffle (deck)
  (let* ((size (length deck))
         (list-of-positions (loop for i from 0 below size
                               collect i)))
    (misterious-sort
     #'(lambda (old-pos elt)
         (declare (ignore old-pos elt))
         (let* ((aux (random (length list-of-positions)))
                (new-pos (elt list-of-positions aux)))
           (setf list-of-positions
                 (delete new-pos list-of-positions))
           new-pos))
     deck)))
It is more complicated and slower, it is O(n^2). A way to leave this faster would be to substitute the list with a binary tree, leaving the algorithm O(n logn). But the algorithm that uses sort is already O(n logn), so nothing faster will be obtained.

Can you think of an algorithm O(n)? I know can't.

nuntius
Posts: 538
Joined: Sat Aug 09, 2008 10:44 am
Location: Newton, MA

Re: Lisp newbie: deck of cards in Lisp

Post by nuntius » Tue Feb 16, 2010 9:05 am

gugamilare wrote:Can you think of an algorithm O(n)? I know can't.
To sort or to shuffle? Durstenfeld's variation of Fisher-Yates is O(n).
http://en.wikipedia.org/wiki/Fisher-Yates_shuffle

gugamilare
Posts: 406
Joined: Sat Mar 07, 2009 6:17 pm
Location: Brazil
Contact:

Re: Lisp newbie: deck of cards in Lisp

Post by gugamilare » Tue Feb 16, 2010 1:29 pm

nuntius wrote:
gugamilare wrote:Can you think of an algorithm O(n)? I know can't.
To sort or to shuffle? Durstenfeld's variation of Fisher-Yates is O(n).
http://en.wikipedia.org/wiki/Fisher-Yates_shuffle
Shame on me, it is just to maintain an array (instead of a list) and exchange the the sorted number with the last number of the array. :oops:

Destruct1
Posts: 20
Joined: Wed Jan 20, 2010 1:40 am

Re: Lisp newbie: deck of cards in Lisp

Post by Destruct1 » Wed Feb 17, 2010 3:19 am

I meant something else:

Code: Select all

;; first I take a list and a function and create a returnlist of the kind lst = ((x1 f(x1)) (x2 f(x2)) (x3 f(x3)) etc... )
(defun mapcarzip (func lst)
  (mapcar #'(lambda (d) (list d (funcall func d))) lst)

;; then I sort the list by the second number in each sublist (so by f(xi))
(defun sortsecondnum (tuplelist)
  (sort tuplelist #'(lambda (x y) (> (second x) (second y)))))

;; now I splice the first element of the list
(defun splicefirst (tuplelist)
  (mapcar #'(lambda (d) (first d)) tuplelist))

and here is mysterious sort:
(defun mysterious-sort (fitnessfunc lst)
  (splicefirst (sortsecondnum (mapcarzip fitnessfunc lst))))
I think this sort function is way more convinient than the compare x with y approach.

Some examples:

Code: Select all

(mysterious-sort #'(lambda (d) (+ (first d) (second d))) '(examplelist))
sort the list ((x1 y1) (x2 y2) ...) by the sum of x and y

(mysterious-sort #'(lambda (d) (random 1000)) examplelist)
shuffles the list

(mysterious-sort #'(lambda (d) (slot-value 'priority)) classlist)
sort a list of classinstaces and put the one with the highest priority to the front of the list.






gugamilare
Posts: 406
Joined: Sat Mar 07, 2009 6:17 pm
Location: Brazil
Contact:

Re: Lisp newbie: deck of cards in Lisp

Post by gugamilare » Wed Feb 17, 2010 1:05 pm

Destruct1 wrote:I think this sort function is way more convinient than the compare x with y approach.
Well, I get it, but, to be honest, I don't find it very convenient. You need to form the tuples, sort them and undo the tuples. The other version is faster and more intuitive. Not to mention that this one has a problem with collisions. Well, it is intuitive in my mind at least :)

Anyway, each person has its own way of thinking, so it may be different with you.

BTW, you can use :key to simplify the call to sort:

Code: Select all

(defun sortsecondnum (tuplelist)
  (sort tuplelist #'> :key #'second))

Destruct1
Posts: 20
Joined: Wed Jan 20, 2010 1:40 am

Re: Lisp newbie: deck of cards in Lisp

Post by Destruct1 » Mon Feb 22, 2010 6:03 am

gugamilare wrote:
Destruct1 wrote:I think this sort function is way more convinient than the compare x with y approach.
Well, I get it, but, to be honest, I don't find it very convenient. You need to form the tuples, sort them and undo the tuples. The other version is faster and more intuitive. Not to mention that this one has a problem with collisions. Well, it is intuitive in my mind at least :)

Anyway, each person has its own way of thinking, so it may be different with you.
I think it is at least a good alternative to the default. In Python the "sort with the compare method" has been removed after nobody could show a decent example why it needs to stay. Fitness functions are now the only way to sort.

The compare strtegy has several disadvantages:
a) You might get not transitive comparisions, like a>b and b>c and c>a. These are difficult to solve and I hate thinking about crap like that.
b) When two elements have the same function result the order is not easy to determine.But it doesnt matter. Simply say that the order of the original list will be preserved or that it is implementation specific (like in the Lisp Set functions). If you care enough as a programmer make sure your fitness function is unambigious.
c) I think it is slower. The computer is very efficient in comparing numerical values but a complex comparision function kills the sort algorythm. Even if you have a matrix which caches the compare (a,b) result, a NxN matrix is needed. With bubble sort you need the whole matrix filled and with merge sort a good part of it must be computed. The fitness function needs a O(n) mapcar and thats it.

gugamilare
Posts: 406
Joined: Sat Mar 07, 2009 6:17 pm
Location: Brazil
Contact:

Re: Lisp newbie: deck of cards in Lisp

Post by gugamilare » Mon Feb 22, 2010 7:51 am

Destruct1 wrote:I think it is at least a good alternative to the default. In Python the "sort with the compare method" has been removed after nobody could show a decent example why it needs to stay. Fitness functions are now the only way to sort.

The compare strtegy has several disadvantages:
a) You might get not transitive comparisions, like a>b and b>c and c>a. These are difficult to solve and I hate thinking about crap like that.
b) When two elements have the same function result the order is not easy to determine.But it doesnt matter. Simply say that the order of the original list will be preserved or that it is implementation specific (like in the Lisp Set functions). If you care enough as a programmer make sure your fitness function is unambigious.
c) I think it is slower. The computer is very efficient in comparing numerical values but a complex comparision function kills the sort algorythm. Even if you have a matrix which caches the compare (a,b) result, a NxN matrix is needed. With bubble sort you need the whole matrix filled and with merge sort a good part of it must be computed. The fitness function needs a O(n) mapcar and thats it.
a) In the case presented, that is not a problem. In other cases, the transitivity would be your concern as much as creating a good fitness function that preserves your ordering.
b) Note that in Common Lisp you need to use stable-sort to preserve the order of the original list. And, in the case presented, collisions are a problem because they make the shuffling less effective. They will be less of a problem if you use a big number in your random function, though.
c) Again, in the example given, this method will actually be slower, since it also needs a function to make the comparison, even if it is the function #'<. In Common Lisp's implementation, the only case where sorting with numbers is faster is to inline the sort function, maybe not even in that case. If you need a comparison function, you will probably need to create a good correspondence between you values and numbers, which would be tiresome, and its computation could consume more time than the sorting itself. Your method would also need to cons a list of tuples and restore the original list, which creates a lot of garbage.

In any case, I understand you point, you could gain little to lots of time of your sorting with a fitness function, but I still believe that in many cases it won't be faster. I'll make some tests here and see if I am right or not.

Post Reply