Re: Shuffling a linked list

Richard wrote:
) On Fri, 29 Dec 2006 20:45:01 +0000 (UTC), Willem <willem@xxxxxxxx>
) wrote:
)
)>Richard wrote:
)>) May I refine the challenge as follows: Given a singly linked list of
)>) length n, randomly shuffle it using O(n) calls to rand, O(n log n) data
)>) moves, and O(1) extra space.
)>
)>Assuming that rand() returns at least log n bits of randomness, you can
)>easily write a wrapper for rand() that returns one bit each time, and calls
)>the real rand only when it runs out of bits.
)
) That's still a factor of log n.

Can you explain why ? As I see it, the number of calls to rand()
will be O(n) if the number of calls to the wrapper is O(n log n).


SaSW, Willem
--
Disclaimer: I am in no way responsible for any of the statements
made in the above text. For all I know I might be
drugged or something..
No I'm not paranoid. You all think I'm paranoid, don't you !
#EOT
.

Relevant Pages

  • Re: Shuffling a linked list
    ... May I refine the challenge as follows: Given a singly linked list of ... length n, randomly shuffle it using Ocalls to rand, Odata ... Assuming that rand() returns at least log n bits of randomness, ... You all think I'm paranoid, ...
    (comp.programming)
  • Re: Drucken: Letztes Blatt leer
    ... Richard Fonfara schrieb: ... Der obere Rand beträgt in Wirklichkeit 4 ... IE-Vorgaben keine Rolle spielen. ... Gruß ...
    (microsoft.public.de.german.inetexplorer.ie6)
  • Re: Shuffling a linked list
    ... May I refine the challenge as follows: Given a singly linked list of ... length n, randomly shuffle it using Ocalls to rand, Odata ... Assuming that rand() returns at least log n bits of randomness, ... the real rand only when it runs out of bits. ...
    (comp.programming)
  • Re: Random, Random Numbers
    ... Richard wrote: ... I understand using the function rand gives a random number within the range of 0 to 1. ... However I need MATLAB to generate different random numbers each time it starts. ...
    (comp.soft-sys.matlab)
  • Re: Learn Multiplicatin Program
    ... ramsonra@excite.com (Richard) writes: ... You're calling srand() once for each call to rand. ... Keith Thompson kst-u@mib.org ...
    (comp.lang.c)