Clearly, you can do a perfect shuffle in O(N) time using mutable arrays,
using the standard imperative algorithm. You can also do it in O(N)
expected time using *immutable* arrays, using Haskell's bulk array
operations.
1. Start with a list of length N. If N 2, stop.
2. Pair each element with
Marcin 'Qrczak' Kowalczyk wrote:
Henning Thielemann [EMAIL PROTECTED] writes:
I did some shuffling based on mergesort [...]
I think it doesn't guarantee equal probabilities of all permutations.
It doesn't (proof: it has a bounded runtime, which can't be true of a
perfect shuffling algorithm
Scott Turner wrote:
Analogous to quicksort's bad behavior in the worst case, an invocation of
'partition' is not guaranteed to make any progress with the shuffling,
because one of the output lists might receive all of the input items.
It's worse than quicksort, because there's no guarantee that
Hi,
I want to implement linear list shuffle in Haskell
(http://c2.com/cgi/wiki?LinearShuffle) and I invented code:
shuffle :: [a] - IO [a]
shuffle [] = return []
shuffle x = do
r - randomRIO (0::Int,length x - 1)
s - shuffle (take r x ++ drop (r+1) x)
return ((x!!r) : s)
This
Gracjan Polak [EMAIL PROTECTED] writes:
shuffle :: [a] - IO [a]
shuffle [] = return []
shuffle x = do
r - randomRIO (0::Int,length x - 1)
s - shuffle (take r x ++ drop (r+1) x)
return ((x!!r) : s)
This algorithm seems not effective, length, take, drop and (!!) are
costly.
Gracjan Polak wrote:
This algorithm seems not effective, length, take, drop and (!!) are
costly. Is there any better way to implement shuffle?
Here is an algorithm known as a perfect-shuffle... I am not too sure of
the efficiency compared to the example you gave, but it builds a tree to
enable
Tomasz Zielonka [EMAIL PROTECTED] writes:
On Fri, Jan 14, 2005 at 09:17:41AM +0100, Gracjan Polak wrote:
This algorithm seems not effective, length, take, drop and (!!) are
costly. Is there any better way to implement shuffle?
You can use mutable arrays (modules Data.Array.MArray,
On Fri, Jan 14, 2005 at 10:17:27AM +0100, Ketil Malde wrote:
Tomasz Zielonka [EMAIL PROTECTED] writes:
On Fri, Jan 14, 2005 at 09:17:41AM +0100, Gracjan Polak wrote:
This algorithm seems not effective, length, take, drop and (!!) are
costly. Is there any better way to implement shuffle?
On Fri, 14 Jan 2005, Gracjan Polak wrote:
I want to implement linear list shuffle in Haskell
(http://c2.com/cgi/wiki?LinearShuffle) and I invented code:
shuffle :: [a] - IO [a]
shuffle [] = return []
shuffle x = do
r - randomRIO (0::Int,length x - 1)
s - shuffle (take r x ++
Please see: http://okmij.org/ftp/Haskell/perfect-shuffle.txt
For an explanation of the algorithm.
Keean.
Ketil Malde wrote:
Tomasz Zielonka [EMAIL PROTECTED] writes:
On Fri, Jan 14, 2005 at 09:17:41AM +0100, Gracjan Polak wrote:
This algorithm seems not effective, length, take, drop and
On Fri, Jan 14, 2005 at 09:17:41AM +0100, Gracjan Polak wrote:
This algorithm seems not effective, length, take, drop and (!!) are
costly. Is there any better way to implement shuffle?
Oleg wrote a great article on implementing the perfect shuffle. with
some sample code.
Tomasz Zielonka [EMAIL PROTECTED] writes:
But is that better, really? IIUC, you will now need to shift the first
part of the string to the right, so it's still a linear operation for
each shuffle.
Perhaps I don't know this particular algorithm, but you can shuffle the
array with linear
Keean Schupke [EMAIL PROTECTED] writes:
Please see: http://okmij.org/ftp/Haskell/perfect-shuffle.txt
For an explanation of the algorithm.
Right. I was commenting based on the source posted by Gracjan.
(And http://c2.com/cgi/wiki?LinearShuffle contains a variety of
shuffling algorithms).
Henning Thielemann wrote:
Is it a good idea to use IO monad for this plain computation?
It is needed as random number supply.
--
Gracjan
___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
John Meacham wrote:
Oleg wrote a great article on implementing the perfect shuffle. with
some sample code.
http://okmij.org/ftp/Haskell/misc.html#perfect-shuffle
Thats the kind of answer I was hoping to get :) Thanks.
shuffle could be useful in standard library. At least Python has it. I
Am Freitag, 14. Januar 2005 09:50 schrieb Ketil Malde:
Gracjan Polak [EMAIL PROTECTED] writes:
shuffle :: [a] - IO [a]
shuffle [] = return []
shuffle x = do
r - randomRIO (0::Int,length x - 1)
s - shuffle (take r x ++ drop (r+1) x)
return ((x!!r) : s)
This algorithm
On Fri, 14 Jan 2005, Scott Turner wrote:
The shuffling algorithms mentioned so far are comparable to
insertion/selection sort. I had come up with a shuffler that relates to
quicksort, in that it partitions the input randomly into lists and works
recursively from there. It looks efficient
Henning Thielemann [EMAIL PROTECTED] writes:
I did some shuffling based on mergesort, that is a list is randomly split
(unzipped) into two lists and the parts are concatenated afterwards. You
must repeat this some times. It even works for infinite lists.
I think it doesn't guarantee equal
Gracjan Polak [EMAIL PROTECTED] wrote:
John Meacham wrote:
Oleg wrote a great article on implementing the perfect
shuffle. with
some sample code.
http://okmij.org/ftp/Haskell/misc.html#perfect-shuffle
Thats the kind of answer I was hoping to get :) Thanks.
shuffle could
19 matches
Mail list logo
