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: [mg54659] Re: [mg54628] Why are permutations duplicated with LexicographicPermutations? How to avoid this?
• From: Sseziwa Mukasa <mukasa at jeol.com>
• Date: Fri, 25 Feb 2005 01:19:16 -0500 (EST)
• References: <200502240821.DAA13312@smc.vnet.net>
• Sender: owner-wri-mathgroup at wolfram.com

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?

Because the two elements 0 are treated as distinct.

> 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.

I don't think speed is going to be your biggest problem, you are  
probably going to run out of storage, there are more than 10^16  
distinct permutations of your above list.  Do you really need them all?

> Can this be avoided in Mathematica itself, and how?

You can get the permutations treating the 0s as distinct with  
DistinctPermutations.  The results are in lexicographic order but the  
sorting algorithm used is slightly different from your desired  
ordering.  You can map the elements of your list to different values to  
get your desired ordering.  For example

DistinctPermutations[{1, 2, 3, 3}] /. {1 -> a, 2 -> b, 3 -> 0}

Regards,

Ssezi

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