From: Steven Bee
Subject: Go Fish game in Lisp
Date: 
Message-ID: <9172b8d8.0412040806.14c817d2@posting.google.com>
Okay, I am relatively new at Lisp, but have been catching on fairly
quickly. I have designed a simple little game of Go Fish (in
pseudocode). As I started writing it I realized that there HAS to be
code available that already does things like shuffling cards,
organizing a deck, dealing the cards into hands, etc.

Does anybody no where I can get these functions? Any card game will
work since I will adapt it to my design, but I'd even be interested if
there is already a Go Fish that would handle card manipulations so
that I can concentrate on the heuristic of the computer player.

Any help would be GREATLY appreciated.

Thanks.

From: Kenny Tilton
Subject: Re: Go Fish game in Lisp
Date: 
Message-ID: <6jmsd.19785$Yh2.7609309@twister.nyc.rr.com>
Steven Bee wrote:
> Okay, I am relatively new at Lisp, but have been catching on fairly
> quickly. I have designed a simple little game of Go Fish (in
> pseudocode). As I started writing it I realized that there HAS to be
> code available that already does things like shuffling cards,
> organizing a deck, dealing the cards into hands, etc.
> 
> Does anybody no where I can get these functions? Any card game will
> work since I will adapt it to my design, but I'd even be interested if
> there is already a Go Fish that would handle card manipulations so
> that I can concentrate on the heuristic of the computer player.
> 
> Any help would be GREATLY appreciated.

I'll give you some help. Write it yourself. :)

The hidden tip being "Lisp makes this easy" and in fact fun, so I did it 
(largely untested):

(let (deck shuffled (hand-count 4))
   (loop for suit in '(spades hearts diamonds clubs)
       do (loop for value in '(2 3 4 5 6 7 8 9 10 jack queen king ace)
              do (push (cons suit value) deck)))
   (loop while deck
         for next-card = (elt deck (random (length deck)))
         do
         (push next-card shuffled)
         (setf deck (delete next-card deck)))
   (loop with hands = (make-list hand-count :initial-element nil)
         for dealt in shuffled
         for n upto (length shuffled)
         do (push dealt (nth (mod n hand-count) hands))
         finally (return hands)))

kenny


-- 
Cells? Cello? Celtik?: http://www.common-lisp.net/project/cells/
Why Lisp? http://alu.cliki.net/RtL%20Highlight%20Film
From: Jim Newton
Subject: Re: Go Fish game in Lisp
Date: 
Message-ID: <31e8qeF33umk3U1@individual.net>
I have a function for shuffling a list into random order.
I'm not sure if it is really sound though.

(defun rnd-t-nil (a b)
   (declare (ignore a b))
   (zerop (random 2)))

(defun shuffle-list (elements)
   (sort elements #'rnd-t-nil))

CL-USER> (shuffle-list '( 1 2 3 4 5 6 7 8))
(5 4 1 6 2 3 8 7)
CL-USER> (shuffle-list '( 1 2 3 4 5 6 7 8))
(1 8 7 5 3 2 4 6)
CL-USER> (shuffle-list '( 1 2 3 4 5 6 7 8))
(5 8 4 7 3 6 2 1)
CL-USER> (shuffle-list '( 1 2 3 4 5 6 7 8))
(2 3 6 8 7 1 5 4)
CL-USER> (shuffle-list '( 1 2 3 4 5 6 7 8))
(1 2 3 4 5 7 8 6)
CL-USER> (shuffle-list '( 1 2 3 4 5 6 7 8))
(4 3 1 2 6 7 5 8)

It is based on the fact that when the sorting-compare-function asks
if a is less than b, rnd-t-nil randomly chooses to return
t or nil.

Does anyone see a problem with such an approach?  E.g.,
does it assume something about the underlying sort
algorithm?

-jim

Steven Bee wrote:
> Okay, I am relatively new at Lisp, but have been catching on fairly
> quickly. I have designed a simple little game of Go Fish (in
> pseudocode). As I started writing it I realized that there HAS to be
> code available that already does things like shuffling cards,
> organizing a deck, dealing the cards into hands, etc.
> 
> Does anybody no where I can get these functions? Any card game will
> work since I will adapt it to my design, but I'd even be interested if
> there is already a Go Fish that would handle card manipulations so
> that I can concentrate on the heuristic of the computer player.
> 
> Any help would be GREATLY appreciated.
> 
> Thanks.
From: Pascal Bourguignon
Subject: Re: Go Fish game in Lisp
Date: 
Message-ID: <87mzwu7ziq.fsf@thalassa.informatimago.com>
Jim Newton <·····@rdrop.com> writes:

> I have a function for shuffling a list into random order.
> I'm not sure if it is really sound though.
> 
> (defun rnd-t-nil (a b)
>    (declare (ignore a b))
>    (zerop (random 2)))
> 
> (defun shuffle-list (elements)
>    (sort elements #'rnd-t-nil))
> [...]
> It is based on the fact that when the sorting-compare-function asks
> if a is less than b, rnd-t-nil randomly chooses to return
> t or nil.
> 
> Does anyone see a problem with such an approach?  E.g.,
> does it assume something about the underlying sort
> algorithm?

Yes. Quicksort have big problems with non ordered functions.  Better
to attach a random "key" to your data and sort on the key with  a
normal lessp.

(defun shuffle-list (elements)
  (mapcar (function cdr)
     (sort (mapcar (lambda (x) (cons (random) x)) elements) (function <)
           :key (function car))))

        

-- 
__Pascal Bourguignon__                     http://www.informatimago.com/
The world will now reboot; don't bother saving your artefacts.
From: Peter Seibel
Subject: Re: Go Fish game in Lisp
Date: 
Message-ID: <m3pt1pzmqm.fsf@javamonkey.com>
Pascal Bourguignon <····@mouse-potato.com> writes:

> Jim Newton <·····@rdrop.com> writes:
>
>> I have a function for shuffling a list into random order.
>> I'm not sure if it is really sound though.
>> 
>> (defun rnd-t-nil (a b)
>>    (declare (ignore a b))
>>    (zerop (random 2)))
>> 
>> (defun shuffle-list (elements)
>>    (sort elements #'rnd-t-nil))
>> [...]
>> It is based on the fact that when the sorting-compare-function asks
>> if a is less than b, rnd-t-nil randomly chooses to return
>> t or nil.
>> 
>> Does anyone see a problem with such an approach?  E.g.,
>> does it assume something about the underlying sort
>> algorithm?
>
> Yes. Quicksort have big problems with non ordered functions.  Better
> to attach a random "key" to your data and sort on the key with  a
> normal lessp.

However SORT *is* guaranteed to terminate as long as the predicate
does. From the SORT dictionary page:

  If the key and predicate always return, then the sorting operation
  will always terminate, producing a sequence containing the same
  elements as sequence (that is, the result is a permutation of
  sequence). This is guaranteed even if the predicate does not really
  consistently represent a total order (in which case the elements
  will be scrambled in some unpredictable way, but no element will be
  lost).

That said, I'm not sure this is the most efficient way to do it.

-Peter

-- 
Peter Seibel                                      ·····@javamonkey.com

         Lisp is the red pill. -- John Fraser, comp.lang.lisp
From: rif
Subject: Re: Go Fish game in Lisp
Date: 
Message-ID: <wj04qj1v4li.fsf@five-percent-nation.mit.edu>
> That said, I'm not sure this is the most efficient way to do it.
> 
> -Peter

Of course not.  Sorting is O(N log N).  Taking a random permutation is
O(N), and the constant is much better.  The sorting solution is both
slow and wrong (in the sense that it does not sample uniformly at
random from the space of permutations).  See my other post for
efficient code for taking random permutations.

(In the above comparison, I'm assuming an array representation, so
that I can access and swap elements in O(1) time.  Technically, I'm
also of course making the standard computer science assumption that
numbers are bounded and are of O(1) size --- in a "true" asymptotic
implementation, I need log N bits to store a number of size N
(including a "pointer" to address N!), and everything blows up by a
factor of O(N), but I feel this is a reasonable approximation to the
world we work in.)

rif
From: rif
Subject: Re: Go Fish game in Lisp
Date: 
Message-ID: <wj0y8gdige5.fsf@five-percent-nation.mit.edu>
> (In the above comparison, I'm assuming an array representation, so
> that I can access and swap elements in O(1) time.  Technically, I'm
> also of course making the standard computer science assumption that
> numbers are bounded and are of O(1) size --- in a "true" asymptotic
> implementation, I need log N bits to store a number of size N
> (including a "pointer" to address N!), and everything blows up by a
> factor of O(N), but I feel this is a reasonable approximation to the
> world we work in.)

Sorry, I meant everthing blows up by a factor of O(log N), not O(N).

rif
From: Jim Newton
Subject: Re: Go Fish game in Lisp
Date: 
Message-ID: <31f368F3aut37U1@individual.net>
however pascal, you must admit that my solution is very
elegant.  whether it works or not in all cases is a different
question but elegant it is.

-jim

Pascal Bourguignon wrote:
> Jim Newton <·····@rdrop.com> writes:
> 
> 
>>I have a function for shuffling a list into random order.
>>I'm not sure if it is really sound though.
>>
>>(defun rnd-t-nil (a b)
>>   (declare (ignore a b))
>>   (zerop (random 2)))
>>
>>(defun shuffle-list (elements)
>>   (sort elements #'rnd-t-nil))
>>[...]
>>It is based on the fact that when the sorting-compare-function asks
>>if a is less than b, rnd-t-nil randomly chooses to return
>>t or nil.
>>
>>Does anyone see a problem with such an approach?  E.g.,
>>does it assume something about the underlying sort
>>algorithm?
> 
> 
> Yes. Quicksort have big problems with non ordered functions.  Better
> to attach a random "key" to your data and sort on the key with  a
> normal lessp.
> 
> (defun shuffle-list (elements)
>   (mapcar (function cdr)
>      (sort (mapcar (lambda (x) (cons (random) x)) elements) (function <)
>            :key (function car))))
> 
>         
> 
From: Kenny Tilton
Subject: Re: Go Fish game in Lisp
Date: 
Message-ID: <P6tsd.60685$Vk6.48730@twister.nyc.rr.com>
Jim Newton wrote:

> however pascal, you must admit that my solution is very
> elegant.  whether it works or not in all cases is a different
> question but elegant it is.

I think implicit in "elegant" is "works in all case". :) I think "cool" 
or "neat" are not so encumbered.

Anyway, the spec says the sort predicate: "... should return true if and 
only if the first argument is strictly less than the second (in some 
appropriate sense)."

Does a random choice satisfy "strictly less"?

kenny

-- 
Cells? Cello? Celtik?: http://www.common-lisp.net/project/cells/
Why Lisp? http://alu.cliki.net/RtL%20Highlight%20Film
From: David Sletten
Subject: Re: Go Fish game in Lisp
Date: 
Message-ID: <tvtsd.160$hd.129@twister.socal.rr.com>
Kenny Tilton wrote:

> 
> Anyway, the spec says the sort predicate: "... should return true if and 
> only if the first argument is strictly less than the second (in some 
> appropriate sense)."
> 
> Does a random choice satisfy "strictly less"?
> 
> kenny
> 
I guess it depends on what you mean by 'appropriate'...or if you have 
any sense. :)

David Sletten
From: Jim Newton
Subject: Re: Go Fish game in Lisp
Date: 
Message-ID: <31g8enF3a1rrvU1@individual.net>
random choice is completely appropriate if the intent it
to randomize.

> Anyway, the spec says the sort predicate: "... should return true if and 
> only if the first argument is strictly less than the second (in some 
> appropriate sense)."
> 
> Does a random choice satisfy "strictly less"?
> 
> kenny
> 
From: Svein Ove Aas
Subject: Re: Go Fish game in Lisp
Date: 
Message-ID: <cour61$8sf$2@services.kq.no>
Jim Newton wrote:

> random choice is completely appropriate if the intent it
> to randomize.
> 
When was the last time you randomized anything by sorting it, in real life?

Break invariants, and Lisp is free to make demons fly out your nose. (But
not, apparently, to avoid terminating the sort.) Either way, using *sort*
to randomize a list is just completely counterintuitive, and doesn't work
well either.
From: Jim Newton
Subject: Re: Go Fish game in Lisp
Date: 
Message-ID: <31ge4bF3atrhdU1@individual.net>
well to me it is very intutitive.  a sort that uses a
random compare function is a randomizer.  In mind
randomizing is just a special case of sorting.


Svein Ove Aas wrote:
> Jim Newton wrote:
> 
> 
>>random choice is completely appropriate if the intent it
>>to randomize.
>>
> 
> When was the last time you randomized anything by sorting it, in real life?
> 
> Break invariants, and Lisp is free to make demons fly out your nose. (But
> not, apparently, to avoid terminating the sort.) Either way, using *sort*
> to randomize a list is just completely counterintuitive, and doesn't work
> well either.
From: Svein Ove Aas
Subject: Re: Go Fish game in Lisp
Date: 
Message-ID: <cov81v$ns8$2@services.kq.no>
Jim Newton wrote:

> well to me it is very intutitive.  a sort that uses a
> random compare function is a randomizer.  In mind
> randomizing is just a special case of sorting.
> 
The sort function, abstractly, tries to reorder its input according to some
kind of ordering predicate. This requires that the input set is
well-ordered; among other things, that means that the predicate function in
question is functional in the context of a single sort.

A random predicate doesn't qualify. If you fail to understand this, you need
to read up on basic CS. Try Wikipedia.


The actual sorting *algorithm* in use may indeed return a pseudo-random
shuffle of the input list, but that's not on purpose and certainly not
something you can assume. You're just lucky that Ansi Common Lisp specifies
that it will eventually return; some sorters might not.
From: Pascal Bourguignon
Subject: Re: Go Fish game in Lisp
Date: 
Message-ID: <87llcc68bk.fsf@thalassa.informatimago.com>
Jim Newton <·····@rdrop.com> writes:
> Svein Ove Aas wrote:
> > When was the last time you randomized anything by sorting it, in
> > real life?
> > Break invariants, and Lisp is free to make demons fly out your
> > nose. (But
> > not, apparently, to avoid terminating the sort.) Either way, using *sort*
> > to randomize a list is just completely counterintuitive, and doesn't work
> > well either.
>
> well to me it is very intutitive.  a sort that uses a
> random compare function is a randomizer.  In mind
> randomizing is just a special case of sorting.

You're both wrong.  Refer to my shuffle function in this thread. 
(It as the complexity of the SORT function).


When you pass to SORT a predicate that is not an order predicate, you
are not sorting, you are getting ramdom behavior.

-- 
A: Because it messes up the order in which people normally read text.
Q: Why is top-posting such a bad thing?
A: Top-posting.
Q: What is the most annoying thing on usenet and in e-mail?
__Pascal Bourguignon__                     http://www.informatimago.com/
From: lin8080
Subject: Re: Go Fish game in Lisp
Date: 
Message-ID: <41B5B7C0.4A9CB546@freenet.de>
Jim Newton schrieb:

> well to me it is very intutitive.  a sort that uses a
> random compare function is a randomizer.  In mind
> randomizing is just a special case of sorting.

A randomize list is the opposite of a sort list, insn't it?

stefan
From: Svein Ove Aas
Subject: Re: Go Fish game in Lisp
Date: 
Message-ID: <cp1ugu$2c$1@services.kq.no>
lin8080 wrote:

> 
> 
> Jim Newton schrieb:
> 
>> well to me it is very intutitive.  a sort that uses a
>> random compare function is a randomizer.  In mind
>> randomizing is just a special case of sorting.
> 
> A randomize list is the opposite of a sort list, insn't it?
> 
It is, in a way, a special kind of sorting - sorting by a random key, that
is. Only works when you decide the key in advance.

The problem is that the OP didn't want to do that, and using a random key
function breaks the sorter's invariant. Very bad. Very dangerus,
From: Jim Newton
Subject: Re: Go Fish game in Lisp
Date: 
Message-ID: <31jqouF38enpaU1@individual.net>
yes it is only dangerous if you do not know how sort is
implemented.

Svein Ove Aas wrote:
> lin8080 wrote:
> 
> 
>>
>>Jim Newton schrieb:
>>
>>
>>>well to me it is very intutitive.  a sort that uses a
>>>random compare function is a randomizer.  In mind
>>>randomizing is just a special case of sorting.
>>
>>A randomize list is the opposite of a sort list, insn't it?
>>
> 
> It is, in a way, a special kind of sorting - sorting by a random key, that
> is. Only works when you decide the key in advance.
> 
> The problem is that the OP didn't want to do that, and using a random key
> function breaks the sorter's invariant. Very bad. Very dangerus,
From: Steven Bee
Subject: Re: Go Fish game in Lisp
Date: 
Message-ID: <1102362924.044297.8810@z14g2000cwz.googlegroups.com>
WOw, you guys rock! Lots of good ideas for shuffling. Also, thanks to
the guy that posted the solitaire code.

Anyway, I'm pretty far along now and am into the actual AI heuristic
for the computer player. Thanks to everyone for the help. Further, the
discussion that this has sparked has been very interesting and
enlightening.
From: Steven Bee
Subject: Re: Go Fish game in Lisp
Date: 
Message-ID: <1102363227.997622.61170@f14g2000cwb.googlegroups.com>
WOw, you guys rock! Lots of good ideas for shuffling. Also, thanks to
the guy that posted the solitaire code.

Anyway, I'm pretty far along now and am into the actual AI heuristic
for the computer player. Thanks to everyone for the help. Further, the
discussion that this has sparked has been very interesting and
enlightening.
From: Svein Ove Aas
Subject: Re: Go Fish game in Lisp
Date: 
Message-ID: <cp2lr1$i95$3@services.kq.no>
Jim Newton wrote:

> yes it is only dangerous if you do not know how sort is
> implemented.
> 
Even if you know how it's implemented on *one* implementation of CL, you
can't assume anything about the others. Thus, it's nonportable code.

It also happens to be an error, which - as previously mentioned - can cause
nasal demons.
From: Fred Gilham
Subject: Re: Go Fish game in Lisp
Date: 
Message-ID: <u7k6rvkn7s.fsf@snapdragon.csl.sri.com>
> It also happens to be an error, which - as previously mentioned -
> can cause nasal demons.

I don't understand why you are saying this, since the documentation
specifically guarantees two things:

1) the sort will terminate, and
2) no items will be lost.

I don't see the statement "it is an error" anywhere with regard to
this. 

(By the way, I hope I haven't lost context and we are still talking
about the random sort ordering predicate.)

I don't think Jim's idea is particularly elegant, but it is clever in
a hackish kind of way, and it is portable in that the spec guarantees
that it has well-defined properties.  The Lisp system may, for
example, just throw up its hands in disgust and spew out the original
sequence --- see Rev. 3:16 :-) --- but a truly random reordering of a
sequence could do the same thing (though if it did it more than once
or twice in a long set of runs on short sequences I'd start wondering
about it).

-- 
Fred Gilham                                         ······@csl.sri.com
The amazing thing is, back when I was a C++ programmer, I thought that
[Design Patterns] was SUCH a great book.  And I guess it was, in a
way: it made it possible to use C++ and get something done.  In the
long run, of course, that may have been a disservice... - Alain Picard
From: Kenny Tilton
Subject: Re: Go Fish game in Lisp
Date: 
Message-ID: <JkGsd.61031$Vk6.30637@twister.nyc.rr.com>
Jim Newton wrote:

> random choice is completely appropriate if the intent it
> to randomize.

You really want this trick to work, don't you? :)

My concern (obviously) was with the "strictly less" requirement, and 
what happens if one does not satisfy it.

I see elsewhere you are curious about measures of randomness. Clearly a 
numerical resolution is contemplated. Cool. We could have competitions 
for most randomness, fastest algorithm, shortest algorithm, and, yes, 
greatest elegance (as long as we are measuring the immeasurable).

btw, have you ever noticed that computer-generated bridge hands tend to 
have less even distribution amongst the four suits than the hands we see 
when humans are shuffling? Check it out:

  http://www.maa.org/mathland/mathtrek_10_16_00.html

As for the measure of randomness, is that what we want?:

From:  Chaitin, G. 1975. Randomness and Mathematical Proof. Scientific 
American.  232(5): 47-52.

"Tossing a coin 20 times can produce any one of 220 (or a little more 
than a million) binary series, and each of them has exactly the same 
probability. Thus it should be no more surprising to obtain the series 
with an obvious pattern than to obtain one that seems to be random . . . 
. If origin in a probabilistic event were made the sole criterion of 
randomness, then both series would have to be considered random, and 
indeed so would all others . . . . The conclusion is singularly 
unhelpful in distinguishing the random from the orderly."

What we want is disorderliness, with the sequence 0-51 considered 
perfectly orderly.

"A truly random sequence of numbers has an asymptotically flat Walsh 
power spectrum." Yuen, C. 1977. Testing Random Number Generators by 
Walsh Transform. IEEE Transactions on Computers.  C-26(4): 329-333.

This guy likes the spectral test:  Knuth, D. 1981. (1st ed. 1969.) The 
Art of Computer Programming.  Volume 2: Seminumerical Algorithms. 
Addison-Wesley.

Well, we could have a preliminary competition to determine the 
diorderliness of a sequence. We will have someone shuffle a new deck 
seven times (six will not do, someone figured out a while ago) and 
publish the result. Whoever can write the algorithm producing the 
highest value between 0 and 1 (the measure of disorderliness) wins.

My idea would be to measure similarity, giving one point for a pair in 
the same order, an additional two points for a triple, an additional 
eight points for a quad, etc. Not sure what I divide into, tho, to get a 
disorderliness measure. maybe i will just go for the lowest similarity.

An interesting question is whether we take into account the distribution 
  into N hands. A low similarity shuffle producing the exact same hands 
(in this case, each hand all one suit) would be no fun.

More citations here:

  http://www.ciphersbyritter.com/RES/RANDTEST.HTM#vonNeumann63

this one looks promising:

  Marsaglia, G. and A. Zaman. 1993. Monkey Tests for Random Number 
Generators. Computers and Mathematics with Applications.  26(9): 1-10.


kenny

-- 
Cells? Cello? Celtik?: http://www.common-lisp.net/project/cells/
Why Lisp? http://alu.cliki.net/RtL%20Highlight%20Film
From: Jim Newton
Subject: Re: Go Fish game in Lisp
Date: 
Message-ID: <31gvp8F3ahl6dU1@individual.net>
Kenny Tilton wrote:
> You really want this trick to work, don't you? :)
> 
> My concern (obviously) was with the "strictly less" requirement, and 
> what happens if one does not satisfy it.
> 

And it will work with some extra restrictions on the
SORT function which Common Lisp does not guarantee.
However, it is pretty easy to write variant of SORT
which is random-cmp-function-safe.



> I see elsewhere you are curious about measures of randomness. Clearly a 
> numerical resolution is contemplated. Cool. We could have competitions 
> for most randomness, fastest algorithm, shortest algorithm, and, yes, 
> greatest elegance (as long as we are measuring the immeasurable).
> 
> btw, have you ever noticed that computer-generated bridge hands tend to 
> have less even distribution amongst the four suits than the hands we see 
> when humans are shuffling? Check it out:
> 
>  http://www.maa.org/mathland/mathtrek_10_16_00.html

I have definitely heard bridge players (little-old-ladies)
complaining that they don't like to play computer
generated hands.  But i never believed it.  However,
this article does seem to argue in favor of the
little-old-ladies.
From: ········@search26.com
Subject: Re: Go Fish game in Lisp
Date: 
Message-ID: <1102332605.676822.148880@c13g2000cwb.googlegroups.com>
http://www.ardice.com/Games/Video_Games/Developers_and_Publishers/A/Addison-Wesley/
From: Pascal Bourguignon
Subject: Re: Go Fish game in Lisp
Date: 
Message-ID: <878y8d71zw.fsf@thalassa.informatimago.com>
Jim Newton <·····@rdrop.com> writes:

> however pascal, you must admit that my solution is very
> elegant.  whether it works or not in all cases is a different
> question but elegant it is.

While SORT is guaranteed to return when you give the function
returning a random boolean for lessp, SORT is not specified to return
anything useful.

The problem is that it will happen often that you have circles in the
relationship. For example in (sort '(a b c d e f g) 
                                    (lambda (x y) (zerop (random 2))))

you could have:  g<a<b<e<c<d<f<g
Then SORT could decide that '(a b c d e f g) is already sorted because:

    a<b 
    b<e<c  ==> b<c
    c<d
    d<f<g<a<b<e ==> d<e
    e<c<d<f ==> e<f
    f<g

so it'll return the sequence unchanged.


-- 
__Pascal Bourguignon__                     http://www.informatimago.com/
The world will now reboot; don't bother saving your artefacts.
From: Jim Newton
Subject: Re: Go Fish game in Lisp
Date: 
Message-ID: <31gv5vF3b8k5uU1@individual.net>
Hi Pascal, isn't the question you are referring to here
actually whether the transitive property of < is satisfied?

I.e, a < b, and b < c ==> a < c

I'm not sure that is really a problem with my proposal.
If the sort function guarantees that it never compares
an element to itself and that it never compares the
same two elements twice, then i do not think the sort
will ever detect what you call circles.

Granted, the Common Lisp SORT function does not
make this promise. But I can easily write a sort
function that does.

If the sort does not work by partitioning then YES
circles can occur.  The bubble sort for example would
have problems because it would compare a to be then
later compare b to a.

But if the sort that works by partitioning I do not
see how such a problem can occur.  I.e.,
it chooses an element M and partitions the list into
two halves, then ones, A, for which A < M  and the ones
that don't.
It will never discover any B such that

A < M, M < B, but B > A,

why? because it will never compare
B to A after partitioning A and B into separate halves.


Lets look at your example.  You claim that a circle
occurs because.

:    a<b
:    b<e<c  ==> b<c
:    c<d
:    d<f<g<a<b<e ==> d<e
:    e<c<d<f ==> e<f
:    f<g

First sort compares every element to 'b' and partitions
into two lists and a mid-point

==> ( a f ) b ( c d e g)

Next, the sort function will try to sort ( a f) and ( c d e f g)
so it will not try to compare b to c.  Once an element is placed into
some list, it never compares the element to anything outside that list.


(defun jimka-sort (l cmp)
   (when l
     (let ( left right)
       (dolist (x (cdr l))
	(if (funcall cmp (car l) x)
	    (push x left)
	    (push x right)))
       `(,@(jimka-sort left cmp)
	,(car l)
	,@(jimka-sort right cmp)))))
From: Pascal Bourguignon
Subject: Re: Go Fish game in Lisp
Date: 
Message-ID: <871xe45vkq.fsf@thalassa.informatimago.com>
Jim Newton <·····@rdrop.com> writes:

> Hi Pascal, isn't the question you are referring to here
> actually whether the transitive property of < is satisfied?
> 
> I.e, a < b, and b < c ==> a < c
> 
> I'm not sure that is really a problem with my proposal.
> If the sort function guarantees that it never compares
> an element to itself and that it never compares the
> same two elements twice, then i do not think the sort
> will ever detect what you call circles.
> 
> Granted, the Common Lisp SORT function does not
> make this promise. But I can easily write a sort
> function that does.
> 
> If the sort does not work by partitioning then YES
> circles can occur.  The bubble sort for example would
> have problems because it would compare a to be then
> later compare b to a.
> 
> But if the sort that works by partitioning I do not
> see how such a problem can occur.  I.e.,
> it chooses an element M and partitions the list into
> two halves, then ones, A, for which A < M  and the ones
> that don't.

You're right. But while CLHS specifies that SORT terminates, it does
not specifies what kind of algorithm is used.  But it does specifies
that lessp must be an order relation (that is, transitive and
antisymetric and non reflexive).


At first, I wanted to present this counter example:


(defun sort (seq lessp &key (key (function identity)))
  ;; We have a massively parallel quantum computer.
  ;; The following loops are run in O(1) :-)
  (let ((order
         (loop with order = (make-array (list (length seq) (length seq))
                                        :element-type 'boolean
                                        :initial-element nil)
               for i below (length seq) do
               (loop for j below (length seq) do
                     (setf (aref order i j) 
                           (funcall lessp
                                    (funcall key (aref seq i))
                                    (funcall key (aref seq j)))))
               finally return order)))
    ;; reaches here because lessp must terminate.
    (flet ((sorted-p (order seq key)
             (loop for i from 1 below (length seq)
                   always (aref order (aref seq (1- i)) (aref seq i)))))
      (loop for candidate = (some-random-permutation seq)
            ;; since we have a quantum computer, the above function
            ;; returns all the permutations at once, in different universes.
            ;; every time it is called.
            until (sorted-p order seq key)
            finally (return candidate)))))


I canceled my first post because this function does not implement the
CLHS specification for COMMON-LISP:SORT: it does not terminate in all
cases!  One could change the last loop termination to ensure
conformance, but you could not choose any permutation over any other.

(Actually, you just need a parallel computer to get the problem in the
above function).
                                    
> (defun jimka-sort (l cmp)
>    (when l
>      (let ( left right)
>        (dolist (x (cdr l))
> 	(if (funcall cmp (car l) x)
> 	    (push x left)
> 	    (push x right)))
>        `(,@(jimka-sort left cmp)
> 	,(car l)
> 	,@(jimka-sort right cmp)))))

Yes, you should use your own implementation when you want a specific
implementation. CLHS does not specify any specific implementation.
Otherwise you're playing Russian Roulette with the implementations.


-- 
__Pascal Bourguignon__                     http://www.informatimago.com/
The world will now reboot; don't bother saving your artefacts.
From: Jim Newton
Subject: Re: Go Fish game in Lisp
Date: 
Message-ID: <31hb43F3bgcikU1@individual.net>
Pascal Bourguignon wrote:
> 
> But it does specifies
> that lessp must be an order relation (that is, transitive and
> antisymetric and non reflexive).
> 
> 

Hi Pascal, Are you sure the spec specifies that the lessp must be an
order relation?  When I read it it is a bit confusting.


CLHS>  This is guaranteed even if the predicate does not really
CLHS>  consistently represent a total order (in which case the
CLHS>  elements will be scrambled in some unpredictable way,
CLHS>  but no element will be lost).

What do you think it means to say that a predicidate does not
CONSISTENTLY represent a total order?  A predicate that returns
a randomly chosen value would seem to me to be inconsist.  Which
types of inconsistent orders are allowed?  Are random ones
disalowed?

It also says:

CLHS> Predicate should return true if and only if the first
CLHS> argument is strictly less than the second (in some
CLHS> appropriate sense).

If the goal is to get a random ordering, then randomly chosen
less-than-ness does seem like an appropriate sense.

Someone told me the spec had errors that you could not find
on the first or second reading.  I'm beginning to understand
what he meant.

-jim
From: Pascal Bourguignon
Subject: Re: Go Fish game in Lisp
Date: 
Message-ID: <87llcc4ekz.fsf@thalassa.informatimago.com>
Jim Newton <·····@rdrop.com> writes:

> Pascal Bourguignon wrote:
> > But it does specifies
> > that lessp must be an order relation (that is, transitive and
> > antisymetric and non reflexive).
> >
> 
> Hi Pascal, Are you sure the spec specifies that the lessp must be an
> order relation?  When I read it it is a bit confusting.
> 
> 
> CLHS>  This is guaranteed even if the predicate does not really
> CLHS>  consistently represent a total order (in which case the
> CLHS>  elements will be scrambled in some unpredictable way,
> CLHS>  but no element will be lost).

Well, it's a little ambiguous. 

A total order is a relation that is transitive, antisymetric AND reflexive

A strict order is a relation that is transitive and antisymetric and
NOT reflexive.

<= is a total order (on the real numbers).
< is a strict order (on the real numbers) and is not a total order
because x<x is always false.

http://mathworld.wolfram.com/StrictOrder.html
http://mathworld.wolfram.com/TotallyOrderedSet.html


CLHS ask us to give a strict order, not a total order:

    Predicate should return true if and only if the first argument is
    strictly less than the second (in some appropriate sense).


Now, from this strict order, CLHS defines an equality and a total order:

    Elements considered equal by the predicate might or might not stay
    in their original order. The predicate is assumed to consider two
    elements x and y to be equal if (funcall predicate x y) and
    (funcall predicate y x) are both false.

in the discussion about SORT lack of stability and STABLE-SORT.


But what is guaranteed, is that a result will be returned (SORT
terminates) and only that the "result is a permutation of sequence".


> What do you think it means to say that a predicidate does not
> CONSISTENTLY represent a total order?  A predicate that returns
> a randomly chosen value would seem to me to be inconsist.  Which
> types of inconsistent orders are allowed?  Are random ones
> disalowed?

I understand this specification as:

pre-condition: P="lessp is a strict order on the set of key"
               S=sequence, K=key
               
post-condition: result is a permutation of S,
                P ==> for-all i in [0,(length S)[
                        (lessp (funcall key (aref S i))
                               (funcall key (aref S (1+ i))))

That is, if lessp is not a strict order, then the only thing you can
say about the result is that it's a permutation of the input sequence,
nothing else.  It does not imply that result is different from the
sequence.


> It also says:
> 
> CLHS> Predicate should return true if and only if the first
> CLHS> argument is strictly less than the second (in some
> CLHS> appropriate sense).
> 
> If the goal is to get a random ordering, then randomly chosen
> less-than-ness does seem like an appropriate sense.

The specification does not say that the result will be shuffled.

 
> Someone told me the spec had errors that you could not find
> on the first or second reading.  I'm beginning to understand
> what he meant.

In conclusion: one given implementation may be doing what you want,
but another implementation may well do something else, like returning
the input sequence.  If you want to write a conformant Common-Lisp
program, you cannot rely on these implemetation differences and you
must avoid giving non strict order relations to SORT or STABLE-SORT.

-- 
__Pascal Bourguignon__                     http://www.informatimago.com/
The world will now reboot; don't bother saving your artefacts.
From: Jeff
Subject: Re: Go Fish game in Lisp
Date: 
Message-ID: <WJnsd.144957$5K2.105852@attbi_s03>
Jim Newton wrote:

> I have a function for shuffling a list into random order.
> I'm not sure if it is really sound though.
> 
> (defun rnd-t-nil (a b)
>    (declare (ignore a b))
>    (zerop (random 2)))
> 
> (defun shuffle-list (elements)
>    (sort elements #'rnd-t-nil))
>
> Does anyone see a problem with such an approach?

Based on the algorithm used inside of sort (whether it is a version of
quicksort, merge sort, bubble sort, ...) It would seem unlikely that
elements could be moved very far from their original position.

Since shuffling is rarely a task that needs serious speed optimization,
I'd be more apt to just use a ROTATEF:

(defun shuffle (deck &optional (amount 50))
  (let ((size (length deck)))
    (dotimes (i amount)
      (rotatef (nth (random size) deck)
               (nth (random size) deck)))
    deck))

Or even just create a new deck from the original deck using a push/pop
approach:

(defun shuffle-pop (deck)
  (let ((size (length deck)) (new))
    (dotimes (i size)
      (push (pop (nthcdr (random (- size i)) deck)) new))
    new))

Jeff M.

-- 
(a (href "http://www.retrobyte.org/"))
(a (href ···············@gmail.com"))
From: Chris Capel
Subject: Re: Go Fish game in Lisp
Date: 
Message-ID: <10r4ch2mui4j092@corp.supernews.com>
Jeff wrote:

> Since shuffling is rarely a task that needs serious speed optimization,
> I'd be more apt to just use a ROTATEF:
> 
> (defun shuffle (deck &optional (amount 50))
>   (let ((size (length deck)))
>     (dotimes (i amount)
>       (rotatef (nth (random size) deck)
>                (nth (random size) deck)))
>     deck))

This approach leaves an average of 8.2 cards, 15%, in their original
positions, as randomly sampling 100 different cards from the deck are
likely to turn up some of the cards more than once, and some not at all.

(let (avg)
  (dotimes (x 1000)
    (let (deck
          dup)
      (dotimes (x 52)
        (push x deck))
      (setq deck (nreverse deck))
      (shuffle deck) ; as above
      (dotimes (x 52)
        (when (= (nth x deck) x)
          (push x dup)))
      (push (length dup) avg)))
  (float (/ (reduce #'+ avg) 1000)))


Chris Capel
From: Chris Capel
Subject: Re: Go Fish game in Lisp
Date: 
Message-ID: <10r4d51n8hf547f@corp.supernews.com>
Chris Capel wrote:

> This approach leaves an average of 8.2 cards, 15%, in their original
> positions...

With a true random sampling, gotten by modifying your example to read like

(defun shuffle (deck &optional)
  (let ((size (length deck)))
    (dotimes (i size)
      (rotatef (nth i deck)
               ;;; ^^^
               (nth (random size) deck)))
    deck))

only .89 cards, or 2%, are left in their original positions.

A more efficient algorithm might perhaps (I'm not sure) be made by rotating
each card only once, instead of at least once.

Chris Capel
From: Geoffrey Summerhayes
Subject: Re: Go Fish game in Lisp
Date: 
Message-ID: <_aysd.44324$kI6.1947385@news20.bellglobal.com>
"Chris Capel" <······@iba.nktech.net> wrote in message ····················@corp.supernews.com...
>
> A more efficient algorithm might perhaps (I'm not sure) be made by rotating
> each card only once, instead of at least once.
>

Quick comparison:

(defun shuffle-1 (deck &optional (amount 50))
  (let ((size (length deck)))
    (dotimes (i amount)
      (rotatef (nth (random size) deck)
               (nth (random size) deck)))
    deck))

(defun shuffle-2 (deck)
  (let ((size (length deck)))
    (dotimes (i size)
      (rotatef (nth i deck)
               ;;; ^^^
               (nth (random size) deck)))
    deck))

(defun shuffle-3 (list)
  (loop for part on list
        for size from (length list) downto 1
        do (rotatef (car part)
                    (nth (random size) part)))
  list)

(defun run-test(fn)
  (let ((hash (make-hash-table :test #'equal)))
    (dotimes (x 100000)
      (incf (gethash (funcall fn (list 1 2 3)) hash 0)))
    (maphash (lambda (key value)
               (format *standard-output* "~&~A : ~A~%" key value))
             hash)))

*compiled*

CL-USER 64 > (time (run-test #'shuffle-1))
Timing the evaluation of (RUN-TEST (FUNCTION SHUFFLE-1))
(2 3 1) : 16611
(2 1 3) : 16652
(1 2 3) : 16805
(1 3 2) : 16449
(3 2 1) : 16736
(3 1 2) : 16747

user time    =      3.735
system time  =      0.000
Elapsed time =   0:00:04
Allocation   = 4288 bytes standard / 3310065 bytes conses
0 Page faults
NIL

CL-USER 65 > (time (run-test #'shuffle-2))
Timing the evaluation of (RUN-TEST (FUNCTION SHUFFLE-2))
(2 3 1) : 18351
(2 1 3) : 18400
(1 2 3) : 14879
(1 3 2) : 18581
(3 2 1) : 14867
(3 1 2) : 14922

user time    =      0.310
system time  =      0.000
Elapsed time =   0:00:00
Allocation   = 4288 bytes standard / 3310087 bytes conses
0 Page faults
NIL

CL-USER 66 > (time (run-test #'shuffle-3))
Timing the evaluation of (RUN-TEST (FUNCTION SHUFFLE-3))
(2 3 1) : 16652
(2 1 3) : 16707
(1 2 3) : 16450
(1 3 2) : 16818
(3 2 1) : 16885
(3 1 2) : 16488

user time    =      0.290
system time  =      0.000
Elapsed time =   0:00:00
Allocation   = 4176 bytes standard / 3308822 bytes conses
0 Page faults
NIL

Both SHUFFLE-1 and SHUFFLE-2 suffer from distribution problems,
2 is more evident on smaller lists, 1 varies depending on the
size of amount, but probably should be around twice the number
of cards in the deck. 3 is a fairly standard shuffle, Kenny's
post redressed in destructive form.

--
Geoff 
From: Paul Khuong
Subject: Re: Go Fish game in Lisp
Date: 
Message-ID: <a828a711.0412042356.263891a0@posting.google.com>
"Jeff" <·······@gmail.com> wrote in message news:<·······················@attbi_s03>...
[...]
 Since shuffling is rarely a task that needs serious speed
optimization,
> I'd be more apt to just use a ROTATEF:
> 
> (defun shuffle (deck &optional (amount 50))
>   (let ((size (length deck)))
>     (dotimes (i amount)
>       (rotatef (nth (random size) deck)
>                (nth (random size) deck)))
>     deck))
Be careful. While I realise that shuffling a deck of card incorrectly
might only lead to lots of frustration, getting the Right Way posted
seems to be important :) The canonical way of shuffling a vector has
been given before. You simply have to switch the i'th element with a
random one. This shuffle is probably weak tending to leave elements in
their old position.
From: Arthur Lemmens
Subject: Re: Go Fish game in Lisp
Date: 
Message-ID: <opsihwugb5k6vmsw@news.xs4all.nl>
Jim Newton wrote:

> I have a function for shuffling a list into random order.
> I'm not sure if it is really sound though.
>
> (defun rnd-t-nil (a b)
> (declare (ignore a b))
> (zerop (random 2)))
>
> (defun shuffle-list (elements)
> (sort elements #'rnd-t-nil))
>
> Does anyone see a problem with such an approach?

My first instinct was to say that you can't even be sure that this
will terminate, but the Hyperspec says that the sorting operation
will always terminate if the predicate always returns, so at least
you're safe in that respect.

That said, a more efficient (and IMHO cleaner) approach is something
like the following (taken from one of my utility libraries):

(defun random-in-range (low high)
  "Returns a random number between LOW (inclusive) and HIGH (exclusive)."
  (assert (> high low))
  (let ((range (-high low)))
    (+ low (random range))))

(defun randomize-vector (vector &key (start 0) end)
  "Destructively rearranges the elements of a vector in some 'random' order.
START and END are the 'bounding index designators' (see Hyperspec) of the vector
to be rearranged."
  (unless end
    (setq end (length vector)))
  (loop for i from start below end
        for j = (random-in-range i end)
        do (rotatef (aref vector i) (aref vector j)))
  vector)

This will give you a random permutation of a vector in O(n) time, where
N is the number of elements that you want to rearrange.

If you want to randomize a list, you could just coerce the list to a vector
before calling RANDOMIZE-VECTOR and coerce the result back to a list.

 --
Arthur
From: Pascal Bourguignon
Subject: Re: Go Fish game in Lisp
Date: 
Message-ID: <87653h8jwk.fsf@thalassa.informatimago.com>
Arthur Lemmens <········@xs4all.nl> writes:

> Jim Newton wrote:
> 
> > I have a function for shuffling a list into random order.
> > I'm not sure if it is really sound though.
> >
> > (defun rnd-t-nil (a b)
> > (declare (ignore a b))
> > (zerop (random 2)))
> >
> > (defun shuffle-list (elements)
> > (sort elements #'rnd-t-nil))
> >
> > Does anyone see a problem with such an approach?
> 
> My first instinct was to say that you can't even be sure that this
> will terminate, but the Hyperspec says that the sorting operation
> will always terminate if the predicate always returns, so at least
> you're safe in that respect.

Even not.

(defun sort (sequence lessp &key (key (function identity)))
  (let ((mlessp (make-array (list (length sequence) (length sequence))
                            :element-type boolean :initial-element nil)))
    (loop for i from 0 below (length sequence) do
      (loop for j from 0 below (length sequence) do
        (setf (aref mlessp i j)
                  (funcall lessp (funcall key (elt sequence i))
                                 (funcall key (elt sequence i))))))
    ;; the predicate always returns ==> the above loop will finish.
    ;; but if the predicate is not transitive and there are circle 
    ;; in lessp relation of length strictly less than sequence then
    ;; the following will never finish:
    (loop candidate = (some-random-permutation-of sequence) 
          until (is-sorted candidate mlessp :key key)
          finally (return candidate))))


CLHS specifies the following contract for the sort predicate:

    Predicate should return true if and only if the first argument is
    strictly less than the second (in some appropriate sense). If the
    first argument is greater than or equal to the second (in the
    appropriate sense), then the predicate should return false.

If you don't respect the contract, you'll go to jail without passing
by the Go square and without getting the $20,000.

-- 
__Pascal Bourguignon__                     http://www.informatimago.com/
The world will now reboot; don't bother saving your artefacts.
From: Marcin 'Qrczak' Kowalczyk
Subject: Re: Go Fish game in Lisp
Date: 
Message-ID: <87r7m5294m.fsf@qrnik.zagroda>
Jim Newton <·····@rdrop.com> writes:

> I have a function for shuffling a list into random order.
> I'm not sure if it is really sound though.
>
> (defun rnd-t-nil (a b)
>    (declare (ignore a b))
>    (zerop (random 2)))
>
> (defun shuffle-list (elements)
>    (sort elements #'rnd-t-nil))

It doesn't guarantee equal probabilities of all permutations.

For example if sort uses insertion sort, elements would have a high
chance of being left close to their original positions. With other
algorithms it needs not to be fair too.

-- 
   __("<         Marcin Kowalczyk
   \__/       ······@knm.org.pl
    ^^     http://qrnik.knm.org.pl/~qrczak/
From: rif
Subject: Re: Go Fish game in Lisp
Date: 
Message-ID: <wj0llcd6fly.fsf@five-percent-nation.mit.edu>
Marcin 'Qrczak' Kowalczyk <······@knm.org.pl> writes:

> Jim Newton <·····@rdrop.com> writes:
> 
> > I have a function for shuffling a list into random order.
> > I'm not sure if it is really sound though.
> >
> > (defun rnd-t-nil (a b)
> >    (declare (ignore a b))
> >    (zerop (random 2)))
> >
> > (defun shuffle-list (elements)
> >    (sort elements #'rnd-t-nil))
> 
> It doesn't guarantee equal probabilities of all permutations.
> 
> For example if sort uses insertion sort, elements would have a high
> chance of being left close to their original positions. With other
> algorithms it needs not to be fair too.

I use this code for taking random permutations and subsets.  It will
be more efficient to work with vectors rather than lists for this
purpose. 

The basic mathematical idea is that we can randomly permute a vector
of length n by swapping the first element of the vector with a random
(possibly also the first) element.  After this swap, the first element
in the permutation is fixed.  We next swap the second element of the
vector with a random element other than the first element.  And so on.
It is clear that this produces each permutation with equal probability
--- each of the n elements has an equal chance of going in the first
slot, each of the remaining elements will have an equal chance of
going in the second slot, and so on.

Style comments welcome.  Utility macros (I use these in lots of
programs that need to be efficient) are at the end; I normally keep
these in a different package --- make sure they're visible to the
permutation code.  

Cheers,

rif

(defpackage :combinatorics
  (:use :common-lisp)
  (:export :random-subset :random-permutation))

(defmethod random-subset ((n fixnum) k)
  "Chooses a k element subset from 0 through n-1.
Results are in a vector of fixnums.  The subset
is ordered (i.e. you can get (0 4) or (4 1))."
  (labels ((swap-elts (a i1 i2)
             (psetf (aref a i1) (aref a i2)
                    (aref a i2) (aref a i1))))
    (let ((set (0-n-vec n)))
      (fixtimes (i k)
                (swap-elts set i (+ i (random (- n i)))))
      (ct-typed-vector-subset set 0 k fixnum))))

(defmethod random-subset ((v vector) k)
  (indexed-vector-subset v (random-subset (veclen v) k)))

(defmethod random-permutation ((n fixnum))
  (random-subset n n))

(defmethod random-permutation ((v vector))
  (indexed-vector-subset v (random-permutation (veclen v))))

(defun indexed-vector-subset (v inds)
  (declare (type (simple-array * (*)) v)
           (type (simple-array fixnum (*)) inds))
  (let* ((n (veclen inds))
         (result (typed-array n (array-element-type v))))
    (fixtimes (i n)
       (setf (aref result i) (aref v (aref inds i))))
    result))

;;; From my collection of utilities

(defmacro typed-array (size type &rest rest)
  (let ((size-sym (gensym)))
    `(let ((,size-sym ,size))
      (declare (type fixnum ,size-sym))
      (make-array ,size-sym :element-type ,type ,@rest))))

(defmacro fixtimes ((var count &optional (result nil)) &body body)
  (let ((g (gensym "COUNTER")))
    `(let ((,g (the fixnum ,count)))
      (dotimes (,var ,g ,result)
        (declare (type fixnum0+ ,var))
        ,@body))))

(defmacro ct-typed-vector-subset (orig-vector start end type)
  (with-gensyms (start-sym end-sym orig-sym)
    `(let ((,start-sym ,start)
           (,end-sym ,end)
           (,orig-sym ,orig-vector))
      (declare (type fixnum ,start-sym)
               (type fixnum ,end-sym)
               (type (simple-array ,type (*)) ,orig-sym))
      (let ((length (- ,end-sym ,start-sym))         
            (offset ,start-sym))
        (returning (result (typed-array length ',type))
          (fixfor (i 0 length)
            (setf (aref result i) (aref ,orig-sym (+ offset i)))))))))

(defmacro with-gensyms (syms &body body)
  `(let (,@(mapcar (lambda (sy)
                     `(,sy (gensym ,(symbol-name sy))))
                   syms))
    ,@body))
From: Peter Herth
Subject: Re: Go Fish game in Lisp
Date: 
Message-ID: <coulq2$had$1@newsreader2.netcologne.de>
After all this discussion I cannot resist to add my twist to it.
It is very close to the algorithm by Kenny, but runs in O(n).

(defun pick (array n size)
   "get the n-th element of array, which contains size elements"
   (let ((erg (aref array n)))
     (setf (aref array n) (aref array (1- size)))
     erg))

(defun shuffle (n)
   "return a random permutation of the numbers [0..n["
   (let ((a (make-array n))
	(size n)
	(erg nil))
     (dotimes (i n)
       (setf (aref a i) i))
     (dotimes (i n)
       (push (pick a (random size) size) erg)
       (decf size))
     erg))

CL-USER> (shuffle 10)
(6 8 1 7 2 5 4 9 0 3)

Peter

-- 
pet project: http://dawn.netcologne.de
homepage:    http://www.peter-herth.de
lisp stuff:  http://www.peter-herth.de/lisp.html
get Ltk here: http://www.peter-herth.de/ltk/
From: Jim Newton
Subject: Re: Go Fish game in Lisp
Date: 
Message-ID: <31gar6F3aad9gU1@individual.net>
can anyone suggest a way to measure the randomness
of a process?

Peter Herth wrote:
> After all this discussion I cannot resist to add my twist to it.
> It is very close to the algorithm by Kenny, but runs in O(n).
> 
> (defun pick (array n size)
>   "get the n-th element of array, which contains size elements"
>   (let ((erg (aref array n)))
>     (setf (aref array n) (aref array (1- size)))
>     erg))
> 
> (defun shuffle (n)
>   "return a random permutation of the numbers [0..n["
>   (let ((a (make-array n))
>     (size n)
>     (erg nil))
>     (dotimes (i n)
>       (setf (aref a i) i))
>     (dotimes (i n)
>       (push (pick a (random size) size) erg)
>       (decf size))
>     erg))
> 
> CL-USER> (shuffle 10)
> (6 8 1 7 2 5 4 9 0 3)
> 
> Peter
> 
From: Svein Ove Aas
Subject: Re: Go Fish game in Lisp
Date: 
Message-ID: <coutbq$mp8$1@services.kq.no>
Jim Newton wrote:

> can anyone suggest a way to measure the randomness
> of a process?
> 

Randomness is formally defined as being its algorithmic complexity, which is
to say its compressability. One way of measuring the randomness of a
dataset, then, is to run it through gzip; measuring algorithmic complexity
directly is probably impossible, since that would imply using a perfect
compression algorithm.

Measuring the randomness of a process, though, is different. One way of
doing this would be to build a list of all possible outputs of the process.
The process is then random if

(a) All possible outputs are returned equally often for a given input, and
(b) this is also true for all other inputs.


It really depends on what you mean by "random"; the above is too slow to use
for anything but the simplest functions.
From: Paul F. Dietz
Subject: Re: Go Fish game in Lisp
Date: 
Message-ID: <lPadnRHi4t8_ZC_cRVn-2g@dls.net>
Svein Ove Aas wrote:

>  measuring algorithmic complexity
> directly is probably impossible, since that would imply using a perfect
> compression algorithm.

One can show that in any formal system there is some constant C such
that no string of complexity > C can be proved to have that complexity
in that formal system (Chaitin's theorem?).

	Paul
From: Svein Ove Aas
Subject: Re: Go Fish game in Lisp
Date: 
Message-ID: <couup2$2uk$1@services.kq.no>
Paul F. Dietz wrote:

> Svein Ove Aas wrote:
> 
>>  measuring algorithmic complexity
>> directly is probably impossible, since that would imply using a perfect
>> compression algorithm.
> 
> One can show that in any formal system there is some constant C such
> that no string of complexity > C can be proved to have that complexity
> in that formal system (Chaitin's theorem?).
> 
That, too, but I haven't found any way of calculating C. ;)
From: Jim Newton
Subject: Re: Go Fish game in Lisp
Date: 
Message-ID: <31gea2F3atrhdU2@individual.net>
hmm, i disagree with these conditions!
Doesn't a function that simply returns its input (the identity function)
fulfill these two conditions?

> (a) All possible outputs are returned equally often for a given input, and
> (b) this is also true for all other inputs.
> 
> 
From: Svein Ove Aas
Subject: Re: Go Fish game in Lisp
Date: 
Message-ID: <cov7oq$ns8$1@services.kq.no>
Jim Newton wrote:

> hmm, i disagree with these conditions!
> Doesn't a function that simply returns its input (the identity function)
> fulfill these two conditions?
> 

I'm assuming that the set of inputs and the set of outputs have equal
cardinality, which is obviously the case in something like a shuffler
(they're equal), but the sets needn't actually contain the same elements. 

The identity function only returns a single value for a single input, not
one of all possible outputs, and certainly not all possible outputs equally
often. Thus breaking condition a. Never mind b.

I think the point of confusion was that when I say "all possible outputs", I
don't mean all possible outputs for a given input, I mean all possible
outputs for *all* inputs.

>> (a) All possible outputs are returned equally often for a given input,
>> and (b) this is also true for all other inputs.
>> 
From: Jim Newton
Subject: Re: Go Fish game in Lisp
Date: 
Message-ID: <31govaF3b1imjU1@individual.net>
yes i see. you are right.

Svein Ove Aas wrote:
> Jim Newton wrote:
> 
> 
>>hmm, i disagree with these conditions!
>>Doesn't a function that simply returns its input (the identity function)
>>fulfill these two conditions?
>>
> 
> 
> I'm assuming that the set of inputs and the set of outputs have equal
> cardinality, which is obviously the case in something like a shuffler
> (they're equal), but the sets needn't actually contain the same elements. 
> 
> The identity function only returns a single value for a single input, not
> one of all possible outputs, and certainly not all possible outputs equally
> often. Thus breaking condition a. Never mind b.
> 
> I think the point of confusion was that when I say "all possible outputs", I
> don't mean all possible outputs for a given input, I mean all possible
> outputs for *all* inputs.
> 
> 
>>>(a) All possible outputs are returned equally often for a given input,
>>>and (b) this is also true for all other inputs.
>>>
> 
> 
From: Pascal Bourguignon
Subject: Re: Go Fish game in Lisp
Date: 
Message-ID: <87r7m67zpe.fsf@thalassa.informatimago.com>
·········@gmail.com (Steven Bee) writes:

> Okay, I am relatively new at Lisp, but have been catching on fairly
> quickly. I have designed a simple little game of Go Fish (in
> pseudocode). As I started writing it I realized that there HAS to be
> code available that already does things like shuffling cards,
> organizing a deck, dealing the cards into hands, etc.
> 
> Does anybody no where I can get these functions? Any card game will
> work since I will adapt it to my design, but I'd even be interested if
> there is already a Go Fish that would handle card manipulations so
> that I can concentrate on the heuristic of the computer player.

I wrote a solitaire playing program sometimes ago:

http://www.informatimago.com/develop/lisp/small-cl-pgms/
http://www.informatimago.com/develop/lisp/small-cl-pgms/solitaire.lisp
http://informatimago.free.fr/i/develop/lisp/small-cl-pgms/
http://informatimago.free.fr/i/develop/lisp/small-cl-pgms/solitaire.lisp

-- 
__Pascal Bourguignon__                     http://www.informatimago.com/
The world will now reboot; don't bother saving your artefacts.
From: Coby Beck
Subject: Re: Go Fish game in Lisp
Date: 
Message-ID: <Zgusd.301073$9b.225994@edtnps84>
"Steven Bee" <·········@gmail.com> wrote in message 
·································@posting.google.com...
> Okay, I am relatively new at Lisp, but have been catching on fairly
> quickly. I have designed a simple little game of Go Fish (in
> pseudocode). As I started writing it I realized that there HAS to be
> code available that already does things like shuffling cards,
> organizing a deck, dealing the cards into hands, etc.
>
> Does anybody no where I can get these functions? Any card game will
> work since I will adapt it to my design, but I'd even be interested if
> there is already a Go Fish that would handle card manipulations so
> that I can concentrate on the heuristic of the computer player.
>
> Any help would be GREATLY appreciated.

Here's a crack at it to get you going:

(defclass card-deck ()
  ((suits     :initarg  :suits
              :initform (list :spades :hearts :diamonds :clubs)
              :accessor suits)
   (faces     :initarg  :faces
              :initform (list 2 3 4 5 6 7 8 9 10 :jack :queen :king :ace)
              :accessor faces)
   (deck      :initform ()
              :accessor deck)
   (dealt     :initform ()
              :accessor dealt)))

(defmethod initialize-instance :after ((card-deck card-deck) &key suits 
faces)
  (setf (deck card-deck)
        (loop for suit in (suits card-deck) nconcing
              (loop for face in (faces card-deck)
                    collect (cons suit face)))))


(defmethod shuffle ((card-deck card-deck) &key (full t))
  (let (all-cards)
    (if full
      (progn
        (setf all-cards (append (dealt card-deck) (deck card-deck)))
        (setf (dealt card-deck) ())
        (setf (deck card-deck) ()))
      (progn
        (setf all-cards (deck card-deck))
        (setf (deck card-deck) ())))
    (loop until (null all-cards)
          with i = (1+ (length all-cards))
          for next = (nth (random (decf i)) all-cards)
          do
          (push next (deck card-deck))
          (setf all-cards (remove next all-cards)))))

(defmethod get-a-card ((card-deck card-deck) &key (from :top))
  (let ((deck (deck card-deck)))
    (when deck
      (let ((card (ecase from
                    (:top (car deck))
                    (:bottom (car (last deck)))
                    (:random (nth (random (length deck)) deck)))))
        (setf (deck card-deck) (remove card deck :test #'equal))
        (push card (dealt card-deck))))))


-- 
Coby Beck
(remove #\Space "coby 101 @ big pond . com")
From: rydis (Martin Rydstr|m) @CD.Chalmers.SE
Subject: Re: Go Fish game in Lisp
Date: 
Message-ID: <w4c6534fgzo.fsf@boris.cd.chalmers.se>
"Coby Beck" <·····@mercury.bc.ca> writes:
> "Steven Bee" <·········@gmail.com> wrote in message 
> ·································@posting.google.com...
> > Okay, I am relatively new at Lisp, but have been catching on fairly
> > quickly. I have designed a simple little game of Go Fish (in
> > pseudocode). As I started writing it I realized that there HAS to be
> > code available that already does things like shuffling cards,
> > organizing a deck, dealing the cards into hands, etc.
> >
> > Does anybody no where I can get these functions? Any card game will
> > work since I will adapt it to my design, but I'd even be interested if
> > there is already a Go Fish that would handle card manipulations so
> > that I can concentrate on the heuristic of the computer player.
> >
> > Any help would be GREATLY appreciated.
> 
> Here's a crack at it to get you going:
<snip>

I do it like this; any comments appreciated.
(Some more of the code is at
  <URL: http://rydis.no-ip.org:11147/src/texas-holdem.lisp >.)
---
(deftype suite () '(member diamond heart club spade))

(deftype value () '(integer 2 14))

(defclass card ()
  ((suite :initarg :suite :type suite :accessor suite)
   (value :initarg :value :type value :accessor value)))

(defmethod print-object ((card card) stream)
  (print-unreadable-object (card stream :type t)
    (format stream "~A~A"
	    (case (value card)
	      (14 "A")
	      (13 "K")
	      (12 "Q")
	      (11 "J")
	      (10 "T")
	      (t (value card)))
	    (case (suite card)
	      (diamond "d")
	      (heart   "h")
	      (club    "c")
	      (spade   "s")))))

(defun make-deck ()
  (let ((deck (make-array 0 :element-type 'card :fill-pointer 0)))
    (dolist (suite '(diamond club heart spade) deck)
      (loop for n from 2 to 14
	do (vector-push-extend (make-instance 'card :suite suite :value n)
			       deck)))))

(defclass deck ()
  ((contents :initarg :contents
	     :initform (make-deck)
	     :accessor contents)))

(defmethod shuffle ((deck deck))
  (let* ((deck-contents (contents deck))
	 (nr-of-cards (length deck-contents))
	 (new-deck (make-array nr-of-cards
			       :element-type 'card
			       :fill-pointer 0)))
    (loop until (= nr-of-cards 0)
	  for curr = (random nr-of-cards)
	  do (rotatef (aref deck-contents (1- nr-of-cards))
		      (aref deck-contents curr))
	  (vector-push (vector-pop deck-contents) new-deck)
	  (decf nr-of-cards))
    (setf (contents deck) new-deck))
  deck)

;<snip>
(defmethod draw ((game game))
  (vector-pop (contents (deck game))))
;<snip>
---

Regards,

'mr

-- 
[Emacs] is written in Lisp, which is the only computer language that is
beautiful.  -- Neal Stephenson, _In the Beginning was the Command Line_