Services & Resources / Wolfram Forums
-----
 /
MathGroup Archive
2005
*January
*February
*March
*April
*May
*June
*July
*August
*September
*October
*November
*December
*Archive Index
*Ask about this page
*Print this page
*Give us feedback
*Sign up for the Wolfram Insider

MathGroup Archive 2005

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

Search the Archive

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


  • Prev by Date: Re: Computing Complex Series Solution using Mathematica
  • Next by Date: Re: finding roots of 1 + 6*x - 8*x^3
  • Previous by thread: Why are permutations duplicated with LexicographicPermutations? How to avoid this?
  • Next by thread: Re: Why are permutations duplicated with LexicographicPermutations? How to avoid this?