Services & ResourcesWolfram ForumsMathGroup Archive

[Date Index] [Thread Index] [Author Index]

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>