random predicate function

random predicate function

[Tyler Smith]

Hi,

I'm trying to write a function that will randomly sort the paragraphs in
a region. It seems to work ok, except that it doesn't seem very random.
I think the function I'm using to randomly generate true and false
values is sub-optimal. It often generates long strings of 't' or nil,
such that either the paragraph order doesn't change at all for multiple calls
to the function, or it simply reverses the order each time I call it.

Any suggestions welcome! Thanks.

Tyler

Here is the function:

(defun randomize-paragraphs (beg end)
  "Sort paragraphs in region randomly.
Called from a program, there are two arguments:
BEG and END (region to sort)."
  (interactive "r")
  (save-excursion
    (save-restriction
      (narrow-to-region beg end)
      (goto-char (point-min))
      (sort-subr nil
		 (function
		  (lambda ()
		    (while (and (not (eobp)) (looking-at paragraph-separate))
		      (forward-line 1))))
		 'forward-paragraph
		 nil
		 nil
		 (lambda (tmp1 tmp2) (if (eq (mod (random) 2) 0)
					 t
				       nil))))))

Re: random predicate function

[Pascal J. Bourguignon]

Tyler Smith <tyler.smith@eku.edu> writes:

> Hi,
>
> I'm trying to write a function that will randomly sort the paragraphs in
> a region. It seems to work ok, except that it doesn't seem very random.
> I think the function I'm using to randomly generate true and false
> values is sub-optimal. It often generates long strings of 't' or nil,
> such that either the paragraph order doesn't change at all for multiple calls
> to the function, or it simply reverses the order each time I call it.
>
> Any suggestions welcome! Thanks.
>
> Tyler
>
> Here is the function:

You shoud not use sort to randomize, because it's suboptimal
[ O(n*log(n)) at best instead of O(n) ].

And foremost, you should not use a predicate that is not a total order
because this usually gives invalid results.

Google for: shuffle algorithm.


You could instead put your paragraphs in a vector and use:

(defun shuffle (vector)
  "Re-orders randomly the vector."
  (loop
      for i from (1-  (length vector)) downto 1
      do (rotatef (aref vector i) (aref vector (random i)))))

to shuffle them and then re-insert them.


-- 
__Pascal Bourguignon__                     http://www.informatimago.com/
A bad day in () is better than a good day in {}.

Re: random predicate function

[Gary]

Tyler Smith wrote:

> 		 (lambda (tmp1 tmp2) (if (eq (mod (random) 2) 0)
> 					 t
> 				       nil))))))

I'm by no means an expert, but you should perhaps first once call
  (random t)
Have a look at
http://www.gnu.org/software/emacs/elisp/html_node/Random-Numbers.html

-- 
Gary        Please do NOT send me 'courtesy' replies off-list.
GNU Emacs 23.2.1
emacsclient 23.2

Re: random predicate function

[Tyler Smith]

Gary <help-gnu-emacs@garydjones.name> writes:

> Tyler Smith wrote:
>
>> 		 (lambda (tmp1 tmp2) (if (eq (mod (random) 2) 0)
>> 					 t
>> 				       nil))))))
>
> I'm by no means an expert, but you should perhaps first once call
>   (random t)
> Have a look at
> http://www.gnu.org/software/emacs/elisp/html_node/Random-Numbers.html

Thanks, Gary. I found that after I sent the first message. I've added in
a call to (random t). I still get some 'non-random' looking sorts. It's
hard to be sure, I'll have to run some sort of systematic check to see
if the results are consistent over large numbers of calls.

Cheers,

Tyler

Re: random predicate function

[Erik Iverson]

Obligatory Dilbert:

http://www.random.org/analysis/dilbert.jpg

Tyler Smith wrote:
> Gary <help-gnu-emacs@garydjones.name> writes:
> 
>> Tyler Smith wrote:
>>
>>> 		 (lambda (tmp1 tmp2) (if (eq (mod (random) 2) 0)
>>> 					 t
>>> 				       nil))))))
>> I'm by no means an expert, but you should perhaps first once call
>>   (random t)
>> Have a look at
>> http://www.gnu.org/software/emacs/elisp/html_node/Random-Numbers.html
> 
> Thanks, Gary. I found that after I sent the first message. I've added in
> a call to (random t). I still get some 'non-random' looking sorts. It's
> hard to be sure, I'll have to run some sort of systematic check to see
> if the results are consistent over large numbers of calls.
> 
> Cheers,
> 
> Tyler
> 
> 

Re: random predicate function

[Tyler Smith]

Erik Iverson <eriki@ccbr.umn.edu> writes:

> Obligatory Dilbert:
>
> http://www.random.org/analysis/dilbert.jpg

I think that's the answer. I set out a long set of ordered paragraphs,
and sorted them with my function. No detectable pattern emerged. So my
earlier problem is most likely attributable to $DEITY messing with my
head. Happens a lot.

Cheers,

Tyler

Re: random predicate function

[Ted Zlatanov]

On Mon, 13 Dec 2010 16:26:03 +0100 "Pascal J. Bourguignon" <pjb@informatimago.com> wrote: 

PJB> You could instead put your paragraphs in a vector and use:

PJB> (defun shuffle (vector)
PJB>   "Re-orders randomly the vector."
PJB>   (loop
PJB>       for i from (1-  (length vector)) downto 1
PJB>       do (rotatef (aref vector i) (aref vector (random i)))))

PJB> to shuffle them and then re-insert them.

I noticed this function in lisp/play/cookie1.el which doesn't require
CL:

; Thanks to Ian G Batten <BattenIG@CS.BHAM.AC.UK>
; [of the University of Birmingham Computer Science Department]
; for the iterative version of this shuffle.
;
;;;###autoload
(defun shuffle-vector (vector)
  "Randomly permute the elements of VECTOR (all permutations equally likely)."
  (let ((i 0)
	j
	temp
	(len (length vector)))
    (while (< i len)
      (setq j (+ i (random (- len i))))
      (setq temp (aref vector i))
      (aset vector i (aref vector j))
      (aset vector j temp)
      (setq i (1+ i))))
  vector)

I wonder if it should be moved out of cookie1.el.

Ted

Re: random predicate function

[Pascal J. Bourguignon]

Ted Zlatanov <tzz@lifelogs.com> writes:

> On Mon, 13 Dec 2010 16:26:03 +0100 "Pascal J. Bourguignon" <pjb@informatimago.com> wrote: 
>
> PJB> You could instead put your paragraphs in a vector and use:
>
> PJB> (defun shuffle (vector)
> PJB>   "Re-orders randomly the vector."
> PJB>   (loop
> PJB>       for i from (1-  (length vector)) downto 1
> PJB>       do (rotatef (aref vector i) (aref vector (random i)))))
>
> PJB> to shuffle them and then re-insert them.
>
> I noticed this function in lisp/play/cookie1.el which doesn't require
> CL:
>
> ; Thanks to Ian G Batten <BattenIG@CS.BHAM.AC.UK>
> ; [of the University of Birmingham Computer Science Department]
> ; for the iterative version of this shuffle.
> ;
> ;;;###autoload
> (defun shuffle-vector (vector)
>   "Randomly permute the elements of VECTOR (all permutations equally likely)."
>   (let ((i 0)
> 	j
> 	temp
> 	(len (length vector)))
>     (while (< i len)
>       (setq j (+ i (random (- len i))))
>       (setq temp (aref vector i))
>       (aset vector i (aref vector j))
>       (aset vector j temp)
>       (setq i (1+ i))))
>   vector)

This is a clear demonstration of the power of macros, and the goodness
of Common Lisp which includes a more powerful set of predefined macros
than any other remaining lisp.


> I wonder if it should be moved out of cookie1.el.



-- 
__Pascal Bourguignon__                     http://www.informatimago.com/
A bad day in () is better than a good day in {}.

Re: random predicate function

[Tyler Smith]

"Pascal J. Bourguignon" <pjb@informatimago.com> writes:

>
> You shoud not use sort to randomize, because it's suboptimal
> [ O(n*log(n)) at best instead of O(n) ].
>
> And foremost, you should not use a predicate that is not a total order
> because this usually gives invalid results.

I don't know what a 'total order' means. Is the result of the predicate
invalid or the actual sorting?

>
> Google for: shuffle algorithm.

Thanks. I knew there must be a name for what I was trying to do.

> You could instead put your paragraphs in a vector and use:
>
> (defun shuffle (vector)
>   "Re-orders randomly the vector."
>   (loop
>       for i from (1-  (length vector)) downto 1
>       do (rotatef (aref vector i) (aref vector (random i)))))
>
> to shuffle them and then re-insert them.

Thanks for this! Very helpful.

Tyler

Re: random predicate function

[Pascal J. Bourguignon]

Tyler Smith <tyler.smith@eku.edu> writes:

> "Pascal J. Bourguignon" <pjb@informatimago.com> writes:
>
>>
>> You shoud not use sort to randomize, because it's suboptimal
>> [ O(n*log(n)) at best instead of O(n) ].
>>
>> And foremost, you should not use a predicate that is not a total order
>> because this usually gives invalid results.
>
> I don't know what a 'total order' means. Is the result of the predicate
> invalid or the actual sorting?

http://en.wikipedia.org/wiki/Total_order

Actually, it should even be a strict total order, that is, it must be a <
operator, not a <= operator.


If you have cycles such as:   a < b < a
then some sort algorithms may not terminate.
When sorting lists, some algorithms could truncate the result.


-- 
__Pascal Bourguignon__                     http://www.informatimago.com/
A bad day in () is better than a good day in {}.

Re: random predicate function

[Tyler Smith]

"Pascal J. Bourguignon" <pjb@informatimago.com> writes:

> Tyler Smith <tyler.smith@eku.edu> writes:
>
>> "Pascal J. Bourguignon" <pjb@informatimago.com> writes:
>>
>>>
>>> You shoud not use sort to randomize, because it's suboptimal
>>> [ O(n*log(n)) at best instead of O(n) ].
>>>
>>> And foremost, you should not use a predicate that is not a total order
>>> because this usually gives invalid results.
>>
>> I don't know what a 'total order' means. Is the result of the predicate
>> invalid or the actual sorting?
>
> http://en.wikipedia.org/wiki/Total_order
>
> Actually, it should even be a strict total order, that is, it must be a <
> operator, not a <= operator.
>
>
> If you have cycles such as:   a < b < a
> then some sort algorithms may not terminate.
> When sorting lists, some algorithms could truncate the result.

Ah, thanks. Makes perfect sense now that I think about it.

Tyler

Re: random predicate function

[Ted Zlatanov]

On Mon, 13 Dec 2010 18:48:19 +0100 "Pascal J. Bourguignon" <pjb@informatimago.com> wrote: 

PJB> Ted Zlatanov <tzz@lifelogs.com> writes:
>> On Mon, 13 Dec 2010 16:26:03 +0100 "Pascal J. Bourguignon" <pjb@informatimago.com> wrote: 
>> 
PJB> You could instead put your paragraphs in a vector and use:
>> 
PJB> (defun shuffle (vector)
PJB> "Re-orders randomly the vector."
PJB> (loop
PJB> for i from (1-  (length vector)) downto 1
PJB> do (rotatef (aref vector i) (aref vector (random i)))))
>> 
PJB> to shuffle them and then re-insert them.
>> 
>> I noticed this function in lisp/play/cookie1.el which doesn't require
>> CL:
>> 
>> ; Thanks to Ian G Batten <BattenIG@CS.BHAM.AC.UK>
>> ; [of the University of Birmingham Computer Science Department]
>> ; for the iterative version of this shuffle.
>> ;
>> ;;;###autoload
>> (defun shuffle-vector (vector)
>> "Randomly permute the elements of VECTOR (all permutations equally likely)."
>> (let ((i 0)
>> j
>> temp
>> (len (length vector)))
>> (while (< i len)
>> (setq j (+ i (random (- len i))))
>> (setq temp (aref vector i))
>> (aset vector i (aref vector j))
>> (aset vector j temp)
>> (setq i (1+ i))))
>> vector)

PJB> This is a clear demonstration of the power of macros, and the goodness
PJB> of Common Lisp which includes a more powerful set of predefined macros
PJB> than any other remaining lisp.

I agree the CL macros are nicer, but the non-macro version is much
easier to debug *in GNU Emacs* and it's already installed.  So they both
have benefits.

Can your `shuffle' be part of cl-extra.el in Emacs?  I like the brevity
of it, and it's a good example of how to use `loop' properly.

Ted

Re: random predicate function

[Pascal J. Bourguignon]

Ted Zlatanov <tzz@lifelogs.com> writes:

> I agree the CL macros are nicer, but the non-macro version is much
> easier to debug *in GNU Emacs* and it's already installed.  So they both
> have benefits.

I don't see how code without macros is easier to debug, there are so
many macros in lisp code.


> Can your `shuffle' be part of cl-extra.el in Emacs?  I like the brevity
> of it, and it's a good example of how to use `loop' properly.

shuffle is not a Common Lisp function, so it should not be added to
cl-extra, but it could be included in an emacs lisp library.

-- 
__Pascal Bourguignon__                     http://www.informatimago.com/
A bad day in () is better than a good day in {}.

Re: random predicate function

[Ted Zlatanov]

On Wed, 15 Dec 2010 16:20:05 +0100 "Pascal J. Bourguignon" <pjb@informatimago.com> wrote: 

PJB> Ted Zlatanov <tzz@lifelogs.com> writes:
>> I agree the CL macros are nicer, but the non-macro version is much
>> easier to debug *in GNU Emacs* and it's already installed.  So they both
>> have benefits.

PJB> I don't see how code without macros is easier to debug, there are so
PJB> many macros in lisp code.

We're talking about GNU Emacs specifically.  Have you debugged macros
there?  They are definitely not as intuitive as functions in the debugger.

>> Can your `shuffle' be part of cl-extra.el in Emacs?  I like the brevity
>> of it, and it's a good example of how to use `loop' properly.

PJB> shuffle is not a Common Lisp function, so it should not be added to
PJB> cl-extra, but it could be included in an emacs lisp library.

OK, thanks.

Ted

Re: random predicate function

[Pascal J. Bourguignon]

Ted Zlatanov <tzz@lifelogs.com> writes:

> On Wed, 15 Dec 2010 16:20:05 +0100 "Pascal J. Bourguignon" <pjb@informatimago.com> wrote: 
>
> PJB> Ted Zlatanov <tzz@lifelogs.com> writes:
>>> I agree the CL macros are nicer, but the non-macro version is much
>>> easier to debug *in GNU Emacs* and it's already installed.  So they both
>>> have benefits.
>
> PJB> I don't see how code without macros is easier to debug, there are so
> PJB> many macros in lisp code.
>
> We're talking about GNU Emacs specifically.  Have you debugged macros
> there?  They are definitely not as intuitive as functions in the debugger.

Only if you don't understand that lisp macros are exactly the same as
lisp functions.

For any macro (defmacro m (args...) body...)
you can write a function (defun m* (args...) body...)
and replace the macro by (defmacro m (args...) (m* args...))
Such a macro is trivial to debug: it just calls a single function!

Therefore macros are as easy as functions to debug.


So, no, I'm sorry, but I never observed any difference between debugging
of macros or functions.


-- 
__Pascal Bourguignon__                     http://www.informatimago.com/
A bad day in () is better than a good day in {}.

RE: random predicate function

[Drew Adams]

> We're talking about GNU Emacs specifically.  Have you debugged macros
> there?  They are definitely not as intuitive as functions in 
> the debugger.

Debug macros using `macroexpand', not the debugger.  (Just a suggestion.)

In the Emacs debugger (`debug', not `edebug'), assuming that a macro does not
itself need to be debugged, I typically hit `c' (instead of `d') to skip over
the details of its expansion.

In fact, I would prefer it if `d' did the same thing as `c' for a macro, and a
new key were available to do what `d' does now for macros.

A typical example is `dolist' in the debugger.  I hit `c' as soon as I see `#['
instead of a function name.  For `dolist' you need to do that twice: once for
`dolist' and once for its `block'.

Re: random predicate function

[Ted Zlatanov]

On Wed, 15 Dec 2010 18:28:33 +0100 "Pascal J. Bourguignon" <pjb@informatimago.com> wrote: 

PJB> Ted Zlatanov <tzz@lifelogs.com> writes:
>> On Wed, 15 Dec 2010 16:20:05 +0100 "Pascal J. Bourguignon" <pjb@informatimago.com> wrote: 
>> 
PJB> Ted Zlatanov <tzz@lifelogs.com> writes:
>> We're talking about GNU Emacs specifically.  Have you debugged macros
>> there?  They are definitely not as intuitive as functions in the debugger.

PJB> Only if you don't understand that lisp macros are exactly the same as
PJB> lisp functions.

You should really clarify if you are talking about Lisp in general or
about GNU Emacs and its Lisp implementation.  I don't know enough about
Lisp in general to say if you're right or not.  But for Emacs Lisp, I'm
positive that macros are not the same as functions, especially in the
debugger (which is where a user would see them).  See Drew's response
for practical advice on how to deal with that.

Ted