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?

```

• Prev by Date: Re: Bounds for Trig expression
• Next by Date: Re: finding roots of 1 + 6*x - 8*x^3
• Previous by thread: Re: Why are permutations duplicated with LexicographicPermutations? How to avoid this?
• Next by thread: finding roots of 1 + 6*x - 8*x^3