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.
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
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.
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.
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
> 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
> (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
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))))
>
>
>
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
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
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
>
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.
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.
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.
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/
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
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,
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,
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.
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.
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.
> 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
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
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.
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.
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)))))
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.
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
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.
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"))
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
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
"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.
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
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.
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/
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))
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/
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
>
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.
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
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. ;)
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.
>
>
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.
>>
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.
>>>
>
>
·········@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.
"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")
"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_