Send Beginners mailing list submissions to
beginners@haskell.org
To subscribe or unsubscribe via the World Wide Web, visit
http://www.haskell.org/mailman/listinfo/beginners
or, via email, send a message with subject or body 'help' to
beginners-requ...@haskell.org
You can reach the person managing the list at
beginners-ow...@haskell.org
When replying, please edit your Subject line so it is more specific
than "Re: Contents of Beginners digest..."
Today's Topics:
1. slightly scramble list randomly (Dennis Raddle)
2. Re: slightly scramble list randomly (Brent Yorgey)
----------------------------------------------------------------------
Message: 1
Date: Sat, 22 Oct 2011 10:50:29 -0700
From: Dennis Raddle <dennis.rad...@gmail.com>
Subject: [Haskell-beginners] slightly scramble list randomly
To: Haskell Beginners <beginners@haskell.org>
Message-ID:
<CAKxLvorev+DxyH1UZqEi+p5Yi8uikELkQVEsLHW-x=+b8ee...@mail.gmail.com>
Content-Type: text/plain; charset=ISO-8859-1
I want to take a list of size N that starts in ascending order and
"slightly randomly scramble it"--- each element is moved within M
steps of its original position (there can be some tolerance for
slightly over M).
The application is a backtracking algorithm that produces random
solutions but tends to favor certain choices--at each node of the
search tree I can evaluate the goodness of each possible next step,
but I don't want the algorithm to always take the best choice. Just
roughly, much of the time.
Dennis
------------------------------
Message: 2
Date: Sat, 22 Oct 2011 16:43:34 -0400
From: Brent Yorgey <byor...@seas.upenn.edu>
Subject: Re: [Haskell-beginners] slightly scramble list randomly
To: Dennis Raddle <dennis.rad...@gmail.com>
Cc: Haskell Beginners <beginners@haskell.org>
Message-ID: <20111022204334.ga5...@seas.upenn.edu>
Content-Type: text/plain; charset=us-ascii
One approach you might consider is randomly generating a sequence of
N*M or so swaps (i.e. generate an index i between 0 and (N-2), and
swap the elements at positions i and i+1). Of course, this way it is
possible to end up with an element very far away from its original
position, but with only a very small probability. "On average" I
would expect things to end up just moved around a bit like you want.
-Brent
On Sat, Oct 22, 2011 at 10:50:29AM -0700, Dennis Raddle wrote:
> I want to take a list of size N that starts in ascending order and
> "slightly randomly scramble it"--- each element is moved within M
> steps of its original position (there can be some tolerance for
> slightly over M).
>
> The application is a backtracking algorithm that produces random
> solutions but tends to favor certain choices--at each node of the
> search tree I can evaluate the goodness of each possible next step,
> but I don't want the algorithm to always take the best choice. Just
> roughly, much of the time.
>
> Dennis
>
> _______________________________________________
> Beginners mailing list
> Beginners@haskell.org
> http://www.haskell.org/mailman/listinfo/beginners
------------------------------
_______________________________________________
Beginners mailing list
Beginners@haskell.org
http://www.haskell.org/mailman/listinfo/beginners
End of Beginners Digest, Vol 40, Issue 36
*****************************************
