Re: Quick permutations! ith permutation?

To: info-dylan@ai.mit.edu
Subject: Re: Quick permutations! ith permutation?
From: Jochen Schmidt <jsc@dataheaven.de>
Date: Fri, 9 Feb 2001 14:00:03 -0500 (EST)
Organization: Dataheaven
References: <94ac3d$6j9$1@nnrp1.deja.com> <94ibji$cne$1@nnrp1.deja.com> <94kj3o$8vl$1@nnrp1.deja.com>
User-Agent: KNode/0.4beta4
Xref: traf.lcs.mit.edu comp.lang.dylan:13061

dauclair@hotmail.com wrote:


> Okay, so is there an efficient way to compute only the ith permutation?
> What I mean here is that I don't want to pay for the entire computation
> up front -- I'm willing to pay for computation of the ith element as I
> go.  Also, I don't want the entire permutation list in memory, just the
> ith element (or, say, less than 100 elements, at any rate).  The stream
> protocol would be lovely but is not necessary.  Constant retrieval over
> 0 <= i < n is important.

Look for the Fisher-Yates algorithm.

Jochen

References:

Quick permutations

From: dauclair@hotmail.com

Re: Quick permutations

From: oodl@my-deja.com

Re: Quick permutations! ith permutation?

From: dauclair@hotmail.com