[Prev][Next][Index][Thread]
Re: Quick permutations! ith permutation?
oodl wrote:
> This runs in under 0.5 seconds on a 450Mhz, Pentium III. If anyone
> wants to improve the code, please go ahead.
[snip code]
*Wow* comparison output:
1. permut:
0 seconds 364102 microseconds
number of permutations = 40320
2. permutations:
2 seconds 723672 milliseconds
number of permutations = 40320
3. permut:
0 seconds 372668 milliseconds
number of permutations = 80640
oodl's implementation (1) is much faster than the SICP implementation
(2). One thing to be sure of this that one must reset the *perms-list*
after using the permutations. Otherwise (3) occurs: a new set is
appended to the old set.
oodl wins the "Quickest Computation of Permutations" recognition award.
----
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.
Why? permut(0, 8, as(<vector>, range(from: 1, to: 9)) take 4+ seconds
with 9! elements (362880); time I could use to perform calculations
using the first set of elements from the permutation ... even so, this
is much better than SICP's implementation which takes 54+ seconds
(ugh!). But, permut over a 10-element vector causes FD to exit because
of not enough memory on a 128 meg Windows NT box. I'm hoping a
stream-like solution will solve both the wait time and the memory issue.
Thank you, again, oodl -- great solution!
Sincerely,
Doug Auclair
Sent via Deja.com
http://www.deja.com/
Follow-Ups:
References: