Generating permutations 
Author Message
 Generating permutations

Please allow me to interrupt this discussion about the best
way to generate permutations before it goes any further...

I don't know if anyone on this newsgroup also reads comp.theory,
but the folks over there have just wrapped up a long and rather
tedious discussion about precisely this topic, complete with
mistakes, corrections, counter-mistakes, and pseudo-code galore.
I suggest that looking at those articles could save a lot of
bandwidth here.

                        Jon



Wed, 02 Aug 1995 04:05:59 GMT  
 Generating permutations
Jon W. Freeman:
   I don't know if anyone on this newsgroup also reads comp.theory,
   but the folks over there have just wrapped up a long and rather
   tedious discussion about precisely this topic [generating
   permutations], complete with mistakes, corrections,
   counter-mistakes, and pseudo-code galore.  I suggest that looking
   at those articles could save a lot of bandwidth here.

Sounds fun, but my news feed expires after 3 days.  Could you
summarize the thread?

As a side note: dealing with n distinct integers requires n log n
space (n integers x log n bits).  Assuming that these numbers have to
go through some sort of serial bottleneck, that means the minimum time
to process these numbers is also n log n.

Of course, the time/space requirements to represent an individual
integer is usually ignored -- usually with the justification that only
a finite set of integers is being dealt with.  What I find amusing is
that this puts a constant bound on even NP hard problems.

Of course, that constant bound is traditionally ignored.

On the other hand, ignoring your constant bounds isn't always a good
idea.

[Meanwhile, back at the ranch, using gradeup on a set of random
integers introduces a significant bias only when you're dealing with a
very short list of integers.  The "practical" reason for using gradeup
instead of a series of swaps seems to be the serial bottleneck of the
series of swaps.  Though I'm not sure that there is any real
"theoretical advantage" to using gradeup.]

Raul



Wed, 02 Aug 1995 08:13:01 GMT  
 
 [ 2 post ] 

 Relevant Pages 

1. generating permutations :-)

2. Efficient way to generate permutations?

3. generating a random permutation

4. code for generating random permutation of an int array

5. Generating a permutation of a given list

6. Q: tail-recursive procedure to generate all permutations of a list

7. all-permutations is faster than permutation

8. A permutation on permutations

9. Open generated HTML in browser (was - Generate HTML in GUI app)

10. OT: Function to generate a psuedo-random permutation of integers < N

11. Finding permutations

12. All Permutations

 

 
Powered by phpBB® Forum Software