MathGroup Archive 2007

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

Search the Archive

Re: All permutations of a sequence


digrpat wrote:

> "Virgil Stokes" <vs at it.uu.se> wrote in message 
> news:f2h8t7$v4$1 at smc.vnet.net...
>> I would like to get all unique permutations of a sequence (e.g.
>> {1,2,3,4,5,6,7,8,9,10,11,12,13}) with the constraint that all sequences
>> that have an opposite ordering are not included (e.g. {13, 12,
>> 11,10,9,8,6,5,4,3,2,1}) would not be included.
>>
>> Are there some Mathematica commands that can be used to efficiently
>> generate these permutations?
>>
>> --V. Stokes
 >
 > permutationlist = {1, 2, 3, 4, 5, 6,}
 >
 > allpermutations[list_List] := Drop[Permutations[list], -Length[list]!/2]
 >
 > allpermutations[permutationlist]

Hi,

I am afraid that the solution is not that simple (at least with 
Mathematica version 5.2). Although he above code works fine for a list 
of length 2 or 3, it does not return a correct result for a list of 4 or 
more elements.

For instance, as you can see in the example below, none of the 
permutations of the forms {3, _, _, 4} or {4, _, _, 3} are present in 
the first half of the permuted list.

In[1]:=
lst = {1, 2, 3, 4};
perm = Permutations[lst]
lower = Drop[perm, -Length[lst]!/2]
upper = Drop[perm, Length[lst]!/2]
upper == Sort[Reverse /@ lower]
Complement[upper, Reverse /@ lower]

Out[2]=
{{1, 2, 3, 4}, {1, 2, 4, 3}, {1, 3, 2, 4},
   {1, 3, 4, 2}, {1, 4, 2, 3}, {1, 4, 3, 2},
   {2, 1, 3, 4}, {2, 1, 4, 3}, {2, 3, 1, 4},
   {2, 3, 4, 1}, {2, 4, 1, 3}, {2, 4, 3, 1},
   {3, 1, 2, 4}, {3, 1, 4, 2}, {3, 2, 1, 4},
   {3, 2, 4, 1}, {3, 4, 1, 2}, {3, 4, 2, 1},
   {4, 1, 2, 3}, {4, 1, 3, 2}, {4, 2, 1, 3},
   {4, 2, 3, 1}, {4, 3, 1, 2}, {4, 3, 2, 1}}

Out[3]=
{{1, 2, 3, 4}, {1, 2, 4, 3}, {1, 3, 2, 4},
   {1, 3, 4, 2}, {1, 4, 2, 3}, {1, 4, 3, 2},
   {2, 1, 3, 4}, {2, 1, 4, 3}, {2, 3, 1, 4},
   {2, 3, 4, 1}, {2, 4, 1, 3}, {2, 4, 3, 1}}

Out[4]=
{{3, 1, 2, 4}, {3, 1, 4, 2}, {3, 2, 1, 4},
   {3, 2, 4, 1}, {3, 4, 1, 2}, {3, 4, 2, 1},
   {4, 1, 2, 3}, {4, 1, 3, 2}, {4, 2, 1, 3},
   {4, 2, 3, 1}, {4, 3, 1, 2}, {4, 3, 2, 1}}

Out[5]=
False

Out[6]=
{{3, 1, 2, 4}, {3, 2, 1, 4}, {4, 1, 2, 3},
   {4, 2, 1, 3}}

In[7]:=
$Version

Out[7]=
"5.2 for Microsoft Windows (June 20, 2005)"

Regards,
Jean-Marc


  • Prev by Date: Re: Re: Residue Function
  • Next by Date: Re: A harmless and amusing bug
  • Previous by thread: Re: All permutations of a sequence
  • Next by thread: Re: All permutations of a sequence