Re: All permutations of a sequence
- To: mathgroup at smc.vnet.net
- Subject: [mg76321] Re: All permutations of a sequence
- From: Jean-Marc Gulliet <jeanmarc.gulliet at gmail.com>
- Date: Sat, 19 May 2007 04:50:49 -0400 (EDT)
- Organization: The Open University, Milton Keynes, UK
- References: <f2h8t7$v4$1@smc.vnet.net> <f2jupj$d3m$1@smc.vnet.net>
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