15! permutations
in [Mathematica]
|
From: Robert Knighten on 26 Mar 2010 06:36 bn77 <nayantara.bhatnagar(a)gmail.com> writes: > Hi, > > 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? > > TIA, > bn77 What does compare mean? How are the permutations available for comparison? You certainly need some way of answering the question for vast blocks at once. (15!)^2 / 2 is about 8.6 x 10^23. If a comparison could be done in 10^(-10) seconds (faster than any currently available PC can do *ANY* compare), then it would still take more than a million years to do that many comparisons one by one. So you need some vast algorithmic improvement over simple comparison of the permutations a pair at a time. -- Bob
From: DrMajorBob on 27 Mar 2010 06:09 10^4 seconds is less than three hours. 10^4/60/60. 2.77778 In case you had your numbers switched, 10^9 seconds is less than 32 years: 10^9/60/60/24/364.25 31.7751 However... you shouldn't have used 9 orders of magnitude for one number and 4 for the other, so maybe you meant: (15!)^2/2/60/60/24/364.25/10^9 // Round 27167891 About 2.7 million years. Bobby On Fri, 26 Mar 2010 05:35:23 -0500, Nicola Mingotti <n-no-mingotti(a)g-spam-mail.com> wrote: > On 2010-03-25 12:11:52 +0100, bn77 said: > >> Hi, >> >> 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? >> >> TIA, >> bn77 > > The number of permutations is then : > N[((15!)^2)/2] => 8.55006*10^23 > > Supposing you can compare 10^9 objects per second > you would need 10^4 seconds that is 3.171 milion years > according to Wolfram Alpha conversion. > > So, no ! If you really need to cycle through all these objects > it's impossible. Brute force here fails, you need to find a smarter > way to solve it. > > bye > > Nicola. > -- DrMajorBob(a)yahoo.com
From: Nicola Mingotti on 27 Mar 2010 06:09 There is a typo, of course it's 10^14 seconds ! bye n. On 2010-03-26 11:35:09 +0100, Nicola Mingotti said: > On 2010-03-25 12:11:52 +0100, bn77 said: > >> Hi, >> >> 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? >> >> TIA, >> bn77 > > The number of permutations is then : > N[((15!)^2)/2] => 8.55006*10^23 > > Supposing you can compare 10^9 objects per second > you would need 10^4 seconds that is 3.171 milion years > according to Wolfram Alpha conversion. > > So, no ! If you really need to cycle through all these objects > it's impossible. Brute force here fails, you need to find a smarter > way to solve it. > > bye > > Nicola.
From: János Löbb on 27 Mar 2010 06:12 On Mar 26, 2010, at 6:35 AM, Nicola Mingotti wrote: > On 2010-03-25 12:11:52 +0100, bn77 said: > >> Hi, >> >> 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? >> >> TIA, >> bn77 > > The number of permutations is then : > N[((15!)^2)/2] ==> 8.55006*10^23 > > Supposing you can compare 10^9 objects per second > you would need 10^4 seconds that is 3.171 milion years > according to Wolfram Alpha conversion. That means 1 second == 317.1 year. Looks to me like Star Trek. Its is no wonder why Wolfram calls this Alfa :-) I am waiting for B=E9ta. J=E1nos
From: Mark McClure on 27 Mar 2010 06:12 On Thu, Mar 25, 2010 at 7:11 AM, bn77 <nayantara.bhatnagar(a)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
First
|
Prev
|
Pages: 1 2 Prev: Fourier transform of exponential function Next: Mathematica starts badly 1 time over 5 in OSX |