Re: Why are permutations duplicated with LexicographicPermutations? How to avoid this?

*To*: mathgroup at smc.vnet.net*Subject*: [mg54667] Re: [mg54628] Why are permutations duplicated with LexicographicPermutations? How to avoid this?*From*: János <janos.lobb at yale.edu>*Date*: Fri, 25 Feb 2005 01:19:31 -0500 (EST)*References*: <200502240821.DAA13312@smc.vnet.net>*Sender*: owner-wri-mathgroup at wolfram.com

In the Help of Union you will find UnsortedUnion. In[4]:= UnsortedUnion[x_] := Module[{f}, f[y_] := (f[y] = Sequence[ ]; y); f /@ x] With that in place: In[5]:= UnsortedUnion[ LexicographicPermutations[ {a, b, 0, 0}]] Out[5]= {{a, b, 0, 0}, {a, 0, b, 0}, {a, 0, 0, b}, {b, a, 0, 0}, {b, 0, a, 0}, {b, 0, 0, a}, {0, a, b, 0}, {0, a, 0, b}, {0, b, a, 0}, {0, b, 0, a}, {0, 0, a, b}, {0, 0, b, a}} cuts it to half. 4!/2!. However trying it in your real example Mathematica reports some errors which leads to me believe that there is a bug in LexicographicPermutations. Even more if I try just: In[2]:= Union[ LexicographicPermutations[ {"0", "C", "D", "0", "G", "H", "J", "0", "0", "P", "0", "0"}]]; the kernel immediately commits suicide without a try !! It probably calculates that the needed storage is out of the 4GB Mathematica can handle on a 32-bit OS. From In[2]:= No more memory available. Mathematica kernel has shut down. Try quitting other applications and then retry. Well, top still reports that there is 1.45GB memory available. If I take out one more argument, then the command runs and eats up all the memory and shuts down the kernel because the needed storage is more than the 2G allowed for one expression. With 10 arguments it finally finishes and gives back the result. Well, 10!/4! times 10 bytes is about 1.5GB. In[9]:= $Version Out[9]= "5.1 for Mac OS X (October \ 25, 2004)" For your case the number of permutations are 24!/11! that is about 15000 trillions, with 24bytes each for storage, so that is a nice size problem to handle even for a 64-bit machine. János On Feb 24, 2005, at 3:21 AM, Valentina Mikel wrote: > When I enter > LexicographicPermutations[{a, b, 0, 0}] > the result is following: > {{a, b, 0, 0}, {a, b, 0, 0}, {a, 0, b, 0}, {a, 0, 0, b}, { > a, 0, b, 0}, {a, 0, 0, b}, {b, a, 0, 0}, {b, a, 0, 0}, { > b, 0, a, 0}, {b, 0, 0, a}, {b, 0, a, 0}, {b, 0, 0, a}, { > 0, a, b, 0}, {0, a, 0, b}, {0, b, a, 0}, {0, b, 0, a}, { > 0, 0, a, b}, {0, 0, b, a}, {0, a, b, 0}, {0, a, 0, b}, { > 0, b, a, 0}, {0, b, 0, a}, {0, 0, a, b}, {0, 0, b, a}} > Why does the result repeat duplicate cases? > In my case I must perform exact functionality of > LexicographicPermutations[{0,C,D,0,G,H,J,0,0,P,0,0,T,V,0,X,Y, > 0,0,4,0,7,8,0}]; > since there are lots of duplicates I'm trying to implement this in C++ > for maximum speed. > Can this be avoided in Mathematica itself, and how?

**References**:**Why are permutations duplicated with LexicographicPermutations? How to avoid this?***From:*Valentina Mikel <valentina.mikel@po.htnet.hr>