Re: 15! permutations
- To: mathgroup at smc.vnet.net
- Subject: [mg108695] Re: 15! permutations
- From: Mark McClure <mcmcclur at unca.edu>
- Date: Sat, 27 Mar 2010 05:12:55 -0500 (EST)
On Thu, Mar 25, 2010 at 7:11 AM, bn77 <nayantara.bhatnagar at gmail.com> wrote: > I'm trying to write a program in mathematica that compares > roughly (15!)^2 / 2 pairs of permutations of length 15. Can > mathematica do this in a reasonable time? Any experience > of this sort? Of course, you can't generate all the permutations but, since there are explicit techniques to enumerate all permutations, you might not have to. One such technique is encapsulated in Combinatorica's NthPermutation function. For example: Needs["Combinatorica`"]; Permutations[Range[5]] == Table[NthPermutation[k, Range[5]], {k, 0, 5! - 1}] True Thus, rather than taking s[[k]], for s=Permutations[n], where n is too large, we might simply compute NthPermutation[i-1,Range[n]]. Now, if you have a clever algorithm that relies on the lexicographic ordering of the permutations, then you might not really need to do all pairwise comparisons. Such an example was recently discussed in the pi day thread: http://groups.google.com/group/comp.soft-sys.math.mathematica/browse_thread/thread/6cbd8ecb4608ae52 In that example, n=9 so it really wasn't necessary to pull this trick but for large n, it certainly could have been done. Mark McClure