MathGroup Archive 2007

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

Search the Archive

Re: Cyclic permutations

  • To: mathgroup at smc.vnet.net
  • Subject: [mg79411] Re: Cyclic permutations
  • From: Peter Pein <petsie at dordos.net>
  • Date: Thu, 26 Jul 2007 05:30:43 -0400 (EDT)
  • References: <f7pon7$prc$1@smc.vnet.net><f7sgu2$ss8$1@smc.vnet.net> <f84juv$qpq$1@smc.vnet.net> <200707250614.CAA23554@smc.vnet.net> <f8754d$pkk$1@smc.vnet.net>

King, Peter R schrieb:
> I have a set of permutations eg.
> 
> {a,b,c,d}, {a,c,b,d} {b,c,d,a}
> 
> Some of which are just cyclic variations of others (ie. {b,c,d,a} is a 
> cyclic variant of {a,b,c,d}). Is there a simple way of getting rid of 
> these, so that the above set just becomes
> 
> {a,b,c,d}, {a,c,b,d}
> 
> I am quite happy to select the cyclic variant to be kept arbitrarily (or 
> using lexical ordering, I'm not particularly concerned).
> 
> Thanks in advance for your help.
> 
> Peter King
> 
> (by the way I am still using version 5.1 so V6 specific methods wouldn't 
> help I'm afraid)
> 
> 

Hi Peter,


Union[] together with an appropriate SelfTest works fine:

In[1]:=
permset = {{a, b, c, d}, {a, c, b, d}, {b, c, d, a}};

Union[permset, SameTest -> (MemberQ[Partition[Join[#1, #1], Length[#1],
1], #2] & )]

Out[2]=
{{a, b, c, d}, {a, c, b, d}}

In[3]:=
Union[permset, SameTest ->
   (MemberQ[Function[x, (RotateLeft[x, #1] & ) /@ Range[Length[x] -
1]][#1],
     #2] & )]

Out[3]=
{{a, b, c, d}, {a, c, b, d}}

but it is a bit slow.

The fastest I have found is ~10 times faster than the Partition[] method
above and ~20 times faster than the RotateLeft[] version and probably at
least 10 times slower than any solution by Carl Woll ;-) :


removeRotations[permset_] :=
 First /@ Rest[NestWhileList[
  Block[{nr1 = #1[[2,1]]},
   {nr1,
    DeleteCases[Rest[#1[[2]]],
     Alternatives @@ NestList[RotateLeft, nr1, Length[nr1] - 1], {1}]
   }] & ,
 {{}, permset}, #1[[2]] =!= {} & ]]


Regards,
Peter


  • Prev by Date: Re: Cyclic permutations
  • Next by Date: Re: Searching list for closest match to p
  • Previous by thread: Re: Cyclic permutations
  • Next by thread: Re: Cyclic permutations