[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

Re: not enough real programmers?

[followups set to afc].

Volker Hetzer <volker.hetzer@abg1.siemens.de> writes:

> Everett M. Greene wrote:
> 
> > > 4.  "Write a program to perform a "perfect shuffle" on an array of 52
> > > numbers."
> > 
> > Anybody with a good answer to question 4 doesn't need to be interviewing
> > for a job.  There are any number of companies, academic institutions,
> > etc. who would like a definitive answer to that problem.
> If perfect means "all permutations are equally likely", then Knuth has an answer.
> Without having read it, I'd simply use a random number generator to put cards
> from one array into the other (modulo the remaining cards, etc.). It should give
> a shuffle as good as the random number generator.

This isn't Knuth's answer, though.  That solution is in-place and runs
in O(n), while your requires an extra array and O(n^2) time.

-- 
Ariel Scolnicov        |"GCAAGAATTGAACTGTAG"            |ariels@compugen.co.il
Compugen Ltd.          |Tel: +972-2-6795059 (Jerusalem)	\  NEW IMPROVED URL!
72 Pinhas Rosen St.    |Tel: +972-3-7658520 (Main office)`--------------------
Tel-Aviv 69512, ISRAEL |Fax: +972-3-7658555  http://3w.compugen.co.il/~ariels