Re: Shuffling a linked list

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.


.

Relevant Pages

  • Re: Shuffling a linked list
    ... )>Richard wrote: ... )>) 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: 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)