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