Re: Shuffling a linked list

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.


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
    ... )>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, ... the real rand only when it runs out of bits. ...
    (comp.programming)